一種針對(duì)多處理器片上系統(tǒng)的靜態(tài)任務(wù)分配方法

吉 慧，周 磊

(揚(yáng)州大學(xué) 信息工程學(xué)院， 江蘇 揚(yáng)州 225000)

一種針對(duì)多處理器片上系統(tǒng)的靜態(tài)任務(wù)分配方法

吉 慧，周 磊

(揚(yáng)州大學(xué) 信息工程學(xué)院， 江蘇 揚(yáng)州 225000)

隨著集成技術(shù)的快速發(fā)展，使得單個(gè)芯片上集成IP核數(shù)目越來(lái)越多。然而，晶體管密度和處理器工作頻率的不斷提升，使得功耗密度持續(xù)增加，導(dǎo)致芯片熱量的不斷上升。因此，MPSoCs面臨不可避免的散熱問(wèn)題。提出了一種基于處理器核區(qū)域均溫(Regional Mean Temperature，RMT)的初始任務(wù)分配策略，該方法充分考慮到處理器核區(qū)域溫度。通過(guò)向量距離計(jì)算處理器核溫度梯度，使用遺傳算法進(jìn)行初始任務(wù)分配。實(shí)驗(yàn)結(jié)果表明，該策略相比于隨機(jī)任務(wù)分配策略，峰值溫度降低率、熱點(diǎn)降低率和溫度梯度降低率最高分別達(dá)到4.69%、42.31%和77.49%。

多處理器片上系統(tǒng)(MPSoCs)；任務(wù)分配；區(qū)域均溫；遺傳算法

Abstract With the rapid development of integration technology,more and more IP cores are integrated on a single chip.However,the improvement of the transistor density and processor working frequency results in increasing power density and heat generation.So MPSoCs are facing inevitable heat dissipation problems.In this paper,a task allocation method based on the Regional Mean Temperature(RMT) of the processor core is proposed.The method fully considers the regional temperature of processor cores by using vector distance to calculate temperature gradient and adopting genetic algorithm to assign the initial task.Experiment results indicate that,compared with the random task allocation strategy,the peak temperature reduction,hotspot reduction and temperature gradient reduction in RMT strategy can reach the maximum values of 4.69%,42.31% and 77.49%,respectively.

Key words Multiprocessor System-on-Chip(MPSoC);task allocation;regional mean temperature;genetic algorithm

0 引言

隨著集成電路工藝技術(shù)的發(fā)展，芯片內(nèi)部可集成的IP核數(shù)目不斷增加，出于對(duì)可擴(kuò)展性、連線延時(shí)和功耗等因素的考慮，片上網(wǎng)絡(luò)(Network on Chip，NoC)逐漸成為多核間通信的主流方式[1-3]。傳統(tǒng)全局互連方式(總線互連)已無(wú)法適應(yīng)當(dāng)前多處理器片上系統(tǒng)(MPSoCs)的通信需求。因此，結(jié)合片上網(wǎng)絡(luò)(NoC)結(jié)構(gòu)設(shè)計(jì)的新興MPSoCs 隨之涌現(xiàn)。然而，較大的晶體管密度及不斷提高的處理器工作頻率使芯片內(nèi)功耗加大，導(dǎo)致 MPSoCs中處理器過(guò)熱。過(guò)熱的處理器溫度，不僅降低系統(tǒng)的性能，同時(shí)縮短了元器件的壽命[4-6]。因此，熱量分布和溫度控制是設(shè)計(jì)MPSoCs的關(guān)鍵。

然而，系統(tǒng)初始運(yùn)行狀態(tài)下的任務(wù)初始分配對(duì)之后的熱量分布和溫度控制至關(guān)重要。目前，基于軟件方法的散熱研究分為靜態(tài)任務(wù)分配和動(dòng)態(tài)任務(wù)調(diào)度2種。靜態(tài)任務(wù)分配又分為離線(off-line)算法和在線算法。離線算法是在系統(tǒng)運(yùn)行前通過(guò)外部的計(jì)算，對(duì)任務(wù)進(jìn)行優(yōu)化分配。在線算法指在系統(tǒng)運(yùn)行時(shí)由芯片內(nèi)部處理器計(jì)算任務(wù)初始分配方法。由于在線算法可以根據(jù)下載的任務(wù)，在系統(tǒng)內(nèi)部對(duì)任務(wù)進(jìn)行自動(dòng)分配處理器資源需要消耗系統(tǒng)本身的計(jì)算資源，因此算法的復(fù)雜性受到限制，相比于在線算法，離線算法可以充分利用外部計(jì)算資源實(shí)現(xiàn)復(fù)雜算法以獲得更好的初始任務(wù)分配。因此，本文選擇以離線算法為技術(shù)基礎(chǔ)設(shè)計(jì)任務(wù)分配方法。

系統(tǒng)中的熱量由2部分產(chǎn)生：處理器功耗和通信功耗。當(dāng)系統(tǒng)中待分配的任務(wù)確定，系統(tǒng)中處理器功耗就已經(jīng)確定。通信功耗與待分配任務(wù)被分配的位置有關(guān)。即使通信任務(wù)已經(jīng)確定，然而在不同分配結(jié)果下，通信功耗也存在巨大差異。但該要求與系統(tǒng)熱量分布要求相互矛盾：由于任務(wù)間通信量較大的任務(wù)往往要消耗更多的處理器功耗來(lái)獲得足夠的計(jì)算能力，因此，從熱量分布的角度來(lái)看，任務(wù)間通信量較大的將會(huì)被分在相距較遠(yuǎn)區(qū)域，以防功率密度升高區(qū)域溫度上升，產(chǎn)生熱點(diǎn)。而這種分配策略卻導(dǎo)致通信功耗上升，加劇系統(tǒng)過(guò)熱風(fēng)險(xiǎn)。因此，均衡通信功耗與熱量分布之間的關(guān)系至關(guān)重要。文獻(xiàn)[7]中，Zhu C 等人根據(jù)離線功耗均衡算法對(duì)任務(wù)進(jìn)行初始分配，該方法使用 HotSpot軟件進(jìn)行仿真，對(duì)任務(wù)進(jìn)行分布和調(diào)整，從而降低芯片的峰值溫度，提高系統(tǒng)可靠性。文獻(xiàn)[8]中，Han Wang等人提出一種熱管理策略，通過(guò)溫度控制器管理溫度，實(shí)現(xiàn)性能提升。文獻(xiàn)[9]中，Lung C L 等人考慮到未分配任務(wù)對(duì)全局處理器核溫度分布影響，提出熱量感知在線任務(wù)分配策略，從而降低任務(wù)分配復(fù)雜度并且實(shí)現(xiàn)任務(wù)快速分配。文獻(xiàn)[10]中，Cui Y和 Zhang W提出了一種有效熱量感知任務(wù)圖調(diào)度算法——自下而上機(jī)制。該方法首先將任務(wù)映射到3D NoC底層，然后選擇調(diào)整一些任務(wù)到頂層，從而降低系統(tǒng)的峰值溫度，減少了執(zhí)行時(shí)間。

以上現(xiàn)有的分配策略只考慮了峰值溫度，沒(méi)有考慮到處理器核與其區(qū)域溫度差對(duì)初始任務(wù)分配帶來(lái)的影響?；谏鲜鰡?wèn)題，本文提出一種基于處理器核區(qū)域均溫的靜態(tài)任務(wù)分配方法，該方法通過(guò)向量距離計(jì)算溫度梯度，并基于遺傳算法實(shí)現(xiàn)初始任務(wù)分配的優(yōu)化，以降低系統(tǒng)的峰值溫度，減小熱點(diǎn)產(chǎn)生的幾率，減小溫度梯度，均勻全局熱量分布。

1 區(qū)域均溫方法設(shè)計(jì)

1.1 區(qū)域向量距離變化對(duì)處理核溫度影響

在簡(jiǎn)化熱傳導(dǎo)模型中，根據(jù)溫度與熱阻、功耗之間的關(guān)系,IP核在穩(wěn)定狀態(tài)下的熱量模型如下[11]：

(1)

式中，Thi,j,k為IP核在3D NoC中(i,j,k)處的溫度；TAmb為環(huán)境溫度；Ri,j,m為IP核在(i,j,m)處的熱阻；A為IP核的面積；Pi,j,s和PRi,j,s分別為(i,j,s)處IP核平均功耗和路由平均功耗?？芍狪P核功耗對(duì)處理核的溫度有一定的影響。

如式(2)所示，tcij表示根據(jù)向量距離選擇區(qū)域某個(gè)處理器核，并且通過(guò)功耗變化后Cij的溫度；σ為處理器核Cij溫度增長(zhǎng)率。4*4的mesh網(wǎng)絡(luò)如圖1所示，圖1對(duì)應(yīng)的向量圖如圖2所示。選擇Bpred_0進(jìn)行研究，選擇區(qū)域處理器核向量距離為1、2和3處理器核，分別為DTB_1、Bpred_2和FPReg_1。當(dāng)DTB_1、Bpred_2和FPReg_1的功耗分別都增加30 W，代入式(2)，如圖3所示，Bpred_0溫度上升分別為5.631%、4.360%和4.135%?？梢?jiàn)σ與向量距離形成負(fù)相關(guān)關(guān)系。本文選擇影響最大的向量距離為1的處理器核作為區(qū)域處理器，并且研究處理器核與其區(qū)域溫度差，使得最后達(dá)到均勻全局的熱量分布的效果。

(2)

圖1 4*4 mesh網(wǎng)絡(luò)

圖2 向量距離

1.2 區(qū)域均溫分配方法

在 2D MPSoC 中，考慮各層之間的散熱能力及分配完成后的處理器核運(yùn)行溫度的均衡性，將相應(yīng)的任務(wù)各自分配至不同層上不同位置的處理器核中是一個(gè)十分復(fù)雜的問(wèn)題，假設(shè)mesh結(jié)構(gòu)為N*M，對(duì)于每個(gè)核Cij(i=1,2,3……,N；j=1,2,3，…,M)，同層與之向量距離為1的節(jié)點(diǎn)為A(i-1)j、A(i+1)j、Ai(j-1)和Ai(j+1)，并且A(i-1)j、A(i+1)j、Ai(j-1)和Ai(j+1)值為0或1，根據(jù)處理器核位置的不同分別定義A(i-1)j、A(i+1)j、Ai(j-1)和Ai(j+1)的值。例如：對(duì)于FPAdd_1的A(i-1)j、A(i+1)j、Ai(j-1)和Ai(j+1)分別為0、1、0和1；對(duì)于DTB_1的A(i-1)j、A(i+1)j、Ai(j-1)和Ai(j+1)分別為1、1、1和1，如圖4所示。

圖3 區(qū)域向量距離變化對(duì)處理核溫度影響

圖4 處理器核區(qū)域模型

Cij對(duì)應(yīng)處理核溫度為T(mén)Cij與之最相鄰的節(jié)點(diǎn)對(duì)應(yīng)溫度為T(mén)(i-1)j、T(i+1)j、Ti(j-1)和Ti(j+1)。假設(shè)基于區(qū)域均溫的處理器核溫度為T(mén)ij，Tavg為T(mén)(i-1)j、T(i+1)j、Ti(j-1)和Ti(j+1)的均溫，ΔTij為T(mén)Cij與Tavg的差值,ΔTij的均值表示為ΔTavg，ΔTij的方差表示為μ，作為溫度梯度。

(3)

ΔTij=TCij-Tavg，

(4)

(5)

(6)

適應(yīng)度決定染色體個(gè)體的生存機(jī)會(huì)，與算法的優(yōu)化目標(biāo)相關(guān)。本文適應(yīng)度函數(shù)定義如下：

f=min{μ}。

(7)

映射屬于NP完全問(wèn)題，為了優(yōu)化溫度梯度，遺傳算法可以有效地解決該類(lèi)優(yōu)化問(wèn)題，進(jìn)行溫度梯度的優(yōu)化，方法如下：

① 產(chǎn)生n個(gè)染色體組成的初始種群。每個(gè)染色體用整數(shù)編碼，染色體的基因與任務(wù)序號(hào)相對(duì)應(yīng)，將任務(wù)分配到IP核上。其長(zhǎng)度等于任務(wù)圖中的任務(wù)數(shù)。染色體中的每個(gè)基因表示一個(gè)任務(wù)，生成初始種群時(shí)，基因值對(duì)應(yīng)任務(wù)圖中隨機(jī)選取的頂點(diǎn)標(biāo)號(hào)。

② 評(píng)估種群中每個(gè)染色體的適應(yīng)度，采用式(7)，保留最小μ，存入μ′中。

③ 應(yīng)用3個(gè)遺傳算子(選擇、交換和變異)生成新一代種群。交叉操作如圖5所示。根據(jù)適應(yīng)度，從種群中選擇2個(gè)父?jìng)€(gè)體(適應(yīng)度越大，被選中的機(jī)會(huì)越大)進(jìn)行交叉，然后放入種群中，計(jì)算適應(yīng)度，選擇最小μ，并且與μ′比較，把最優(yōu)值存入μ′。交叉操作后選擇最優(yōu)的染色體進(jìn)行變異操作，如圖6所示，將處理器核溫度最高的點(diǎn)(任務(wù)2)與處理器核溫度最低的點(diǎn)(任務(wù)9)進(jìn)行位置交換。再次將染色體放入種群中，計(jì)算適應(yīng)度，選擇最小μ，并且與μ′比較，把最優(yōu)值存入μ′。

圖5 交叉操作

圖6 變異操作

④ 重復(fù)步驟②和步驟③，直到達(dá)到最大迭代次數(shù)(1 500)或每代優(yōu)化的溫度梯度不再變化。如此，便得到了任務(wù)分配到IP核上的優(yōu)化布局。

根據(jù)上述原則，在算法中設(shè)置種群大小為100，交換率為0.9，變異率為0.01，最大進(jìn)化代數(shù)為1 500，染色體的長(zhǎng)度等于IP核的類(lèi)型數(shù)目。通過(guò)遺傳算法，選擇最優(yōu)結(jié)果，將任務(wù)分配到相應(yīng)的IP核。

2 實(shí)驗(yàn)結(jié)果分析

2.1 實(shí)驗(yàn)環(huán)境

為了驗(yàn)證RMT策略的有效性，采用 4*4mesh、4*6mesh、6*6mesh、6*8mesh和8*8mesh這5種拓?fù)浣Y(jié)構(gòu)進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)中的任務(wù)分配將基于E3S[12]基準(zhǔn)進(jìn)行實(shí)現(xiàn)，E3S基準(zhǔn)中包括來(lái)自EEMBC基準(zhǔn)的automation/industrial，officeautomation，networking，telecommunication和consumer-electronic這5個(gè)基準(zhǔn)組。每個(gè)基準(zhǔn)程序由一個(gè)任務(wù)圖和預(yù)定的通信模式組成，E3S基準(zhǔn)的詳細(xì)信息如表1所示。

表1 E3S基準(zhǔn)規(guī)范

2.2 實(shí)驗(yàn)結(jié)果

為了保證系統(tǒng)運(yùn)行的可靠性，通常情況下處理器核的峰值溫度應(yīng)該保持在85 ～110 ℃，處理核溫度高于85 ℃的為熱點(diǎn)。處理器核峰值溫度較高，則會(huì)導(dǎo)致系統(tǒng)運(yùn)行可靠性和有效性降低。下面將區(qū)域均溫分配策略與隨機(jī)任務(wù)分配策略相比。用熱點(diǎn)減少率(Hotspot reduction)、峰值降低率(Peak temperature reduction)和溫度差降低率(Temperaure gradient reduction)這3個(gè)參數(shù)來(lái)計(jì)算比較RMT方案和隨機(jī)任務(wù)分配(Random)方案的性能，可以分別用如下3個(gè)等式來(lái)表示。

Peaktemperaturereduction=

式中，Hotspotreduction為熱點(diǎn)降低率；Hotspotrandom為隨機(jī)分布熱點(diǎn)平均個(gè)數(shù)；HotspotRMT為RMT分布熱點(diǎn)個(gè)數(shù)；Peaktemperaturereduction為峰值降低率；Peaktemperaturerandom為隨機(jī)分布峰值平均值；PeaktemperatureRMT為RMT峰值；Temperauregradientreduction為溫度梯度降低率；μRMT為RMT任務(wù)分配處理器溫度梯度；μrandom為隨機(jī)任務(wù)分配處理器溫度梯度。

如圖7、圖8和圖9所示，實(shí)驗(yàn)選取4*4 mesh、4*6 mesh、6*6 mesh、6*8 mesh和8*8 mesh的網(wǎng)絡(luò)，將2種任務(wù)分配策略進(jìn)行比較，峰值溫度降低率分別為3.66%、4.69%、3.51%、4.19%和2.95%，熱點(diǎn)降低率分別為26.61%、15.43% 、42.31%、12.6%和23.66%，溫度梯度降低 49.59%、23.13%、64.63%、77.49%和61.63%?？梢?jiàn)經(jīng)過(guò)RMT分配，系統(tǒng)的峰值溫度、熱點(diǎn)個(gè)數(shù)和溫度梯度都得到了明顯的降低，實(shí)現(xiàn)全局熱量分布均勻，提高了系統(tǒng)的可靠性和有效性。

圖7 峰值比較

圖8 熱點(diǎn)比較

圖9 溫度梯度比較

3 結(jié)束語(yǔ)

本文針對(duì)MPSoC中的散熱問(wèn)題，提出了一種基于處理器核區(qū)域均溫的任務(wù)分配的方法。該方法充分考慮了處理器核溫度及其區(qū)域均溫對(duì)其溫度的影響，并通過(guò)遺傳算法進(jìn)行任務(wù)分配的優(yōu)化。與隨機(jī)任務(wù)分配策略相比，該策略降低了熱點(diǎn)個(gè)數(shù)和峰值溫度降低，同時(shí)降低了系統(tǒng)的溫度梯度，使得全局的熱量分布更加均勻。今后將針對(duì)散熱問(wèn)題的實(shí)時(shí)溫度感知方面展開(kāi)更為深入的研究。

[1] XIANG D,CHAKRABARTY K,FUJIWARA H.Multicast-Based Testing and Thermal-Aware Test Scheduling for 3D ICs with a Stacked Network-on-Chip[J].IEEE Transactions on Computers,2016,65(9):2 767-2 779.

[2] BAHREBAR P,STROOBANDT D.Adaptive Routing in MPSoCs Using an Efficient Path-based Method[C]∥ Soc Design Conference,IEEE,2013:031-034.

[3] WEI L,ZHOU L.An Equilibrium Partitioning Method for Multicast Traffic in 3D NoC Architecture[C]∥Very Large Scale Integration(VLSI-SoC),2015 IFIP/IEEE International Conference on,IEEE,2015:128-133.

[4] HAMEDANI P K,HESSABI S,Sarbazi-Azad H,et al.Exploration of Temperature Constraints for Thermal Aware Mapping of 3D Networks on Chip[C]∥ Euromicro International Conference on Parallel,Distributed and Network-Based Processing,IEEE Computer Society,2012:499-506.

[5] RAHMANI A M,VADDINA K R,LATIF K,et al.Design and Management of High-Performance,Reliable and Thermal-Aware 3D Networks-on-Chip[J].Iet Circuits Devices & Systems,2012,6(5):308-321.

[6] HUANG W,GHOSH S,VELUSAMY S,et al.Hotspot:Acompact Thermal Modeling Methodology for Early-stage VLSI Design[J].IEEE Transactions on Very Large Scale Integration Systems,2006,14(5):501-513.

[7] ZHU C,GU Z,SHANG L,et al.Three-Dimensional Chip-Multiprocessor Run-Time Thermal Anagement[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,2008,27(8):1 479-1 492.

[8] WANG H,FU Y,LIU T,et al.Thermal Management via Task Scheduling for 3D NoC Based Multi-processor[C]∥SoC Design Conference(ISOCC),2010 International,IEEE,2010:440-444.

[9] LUNG C L,HO Y L,KWAI D M,et al.Thermal-aware on-line Task Allocation for 3D Multi-core Processor Throughput Optimization[C]∥ Design,Automation & Test in Europe Conference & Exhibition(DATE),2011.IEEE,2011:1-6.

[10] CUI Y,ZHANG W,CHATURVEDI V,et al.Thermal-Aware Task Scheduling for 3D-Network-on-Chip:A Bottom to Top Scheme[J].Journal of Circuits,Systems and Computers,2016,25(1):1640003.

[11] ZHU C,GU Z,SHANG L,et al.Three-Dimensional Chip-Multiprocessor Run-Time Thermal Management[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,2008,27(8):1 479-1 492.

[12] GHOSH P,SEN A,HALL A.Energy Efficient Application Mapping to NoC Processing Elements Operating at Multiple Voltage Levels[C]∥International Symposium on Networks-On-Chips,NOCS 2009,May 10-13 2009,La Jolla,Ca,Usa.Proceedings.DBLP,2009:80-85.

A Static Task Allocation Method for Multiprocessor System-on-Chip

JI Hui,ZHOU Lei

(CollegeofInformationEngineering，YangzhouUniversity，YangzhouJiangsu225000，China)

10.3969/j.issn.1003-3106.2017.08.06

吉慧，周磊.一種針對(duì)多處理器片上系統(tǒng)的靜態(tài)任務(wù)分配方法[J].無(wú)線電工程,2017,47(8):22-26.[JI Hui,ZHOU Lei.A Static Task Allocation Method for Multiprocessor System-on-Chip[J].Radio Engineering,2017,47(8):22-26.]

2017-04-01

國(guó)家自然科學(xué)基金資助項(xiàng)目(61376025，61301111)；江蘇省高校自然科學(xué)基金資助項(xiàng)目(13KJB510039)；揚(yáng)州市自然科學(xué)青年基金資助項(xiàng)目(SQN20150035)。

TN919

A

1003-3106(2017)08-0022-05

吉 慧 女，(1991—) ，碩士研究生。主要研究方向:電子系統(tǒng)集成和專(zhuān)用集成電路設(shè)計(jì)。

周 磊 男，(1980—) ，博士，講師。主要研究方向:電子系統(tǒng)集成和專(zhuān)用集成電路設(shè)計(jì)。