一種針對多處理器片上系統的靜態任務分配方法

吉 慧，周 磊

(揚州大學 信息工程學院， 江蘇 揚州 225000)

一種針對多處理器片上系統的靜態任務分配方法

吉 慧，周 磊

(揚州大學 信息工程學院， 江蘇 揚州 225000)

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

多處理器片上系統(MPSoCs)；任務分配；區域均溫；遺傳算法

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 引言

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

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

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

以上現有的分配策略只考慮了峰值溫度，沒有考慮到處理器核與其區域溫度差對初始任務分配帶來的影響。基于上述問題，本文提出一種基于處理器核區域均溫的靜態任務分配方法，該方法通過向量距離計算溫度梯度，并基于遺傳算法實現初始任務分配的優化，以降低系統的峰值溫度，減小熱點產生的幾率，減小溫度梯度，均勻全局熱量分布。

1 區域均溫方法設計

1.1 區域向量距離變化對處理核溫度影響

在簡化熱傳導模型中，根據溫度與熱阻、功耗之間的關系,IP核在穩定狀態下的熱量模型如下[11]：

(1)

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

如式(2)所示，tcij表示根據向量距離選擇區域某個處理器核，并且通過功耗變化后Cij的溫度；σ為處理器核Cij溫度增長率。4*4的mesh網絡如圖1所示，圖1對應的向量圖如圖2所示。選擇Bpred_0進行研究，選擇區域處理器核向量距離為1、2和3處理器核，分別為DTB_1、Bpred_2和FPReg_1。當DTB_1、Bpred_2和FPReg_1的功耗分別都增加30 W，代入式(2)，如圖3所示，Bpred_0溫度上升分別為5.631%、4.360%和4.135%。可見σ與向量距離形成負相關關系。本文選擇影響最大的向量距離為1的處理器核作為區域處理器，并且研究處理器核與其區域溫度差，使得最后達到均勻全局的熱量分布的效果。

(2)

圖1 4*4 mesh網絡

圖2 向量距離

1.2 區域均溫分配方法

在 2D MPSoC 中，考慮各層之間的散熱能力及分配完成后的處理器核運行溫度的均衡性，將相應的任務各自分配至不同層上不同位置的處理器核中是一個十分復雜的問題，假設mesh結構為N*M，對于每個核Cij(i=1,2,3……,N；j=1,2,3，…,M)，同層與之向量距離為1的節點為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，根據處理器核位置的不同分別定義A(i-1)j、A(i+1)j、Ai(j-1)和Ai(j+1)的值。例如：對于FPAdd_1的A(i-1)j、A(i+1)j、Ai(j-1)和Ai(j+1)分別為0、1、0和1；對于DTB_1的A(i-1)j、A(i+1)j、Ai(j-1)和Ai(j+1)分別為1、1、1和1，如圖4所示。

圖3 區域向量距離變化對處理核溫度影響

圖4 處理器核區域模型

Cij對應處理核溫度為TCij與之最相鄰的節點對應溫度為T(i-1)j、T(i+1)j、Ti(j-1)和Ti(j+1)。假設基于區域均溫的處理器核溫度為Tij，Tavg為T(i-1)j、T(i+1)j、Ti(j-1)和Ti(j+1)的均溫，ΔTij為TCij與Tavg的差值,ΔTij的均值表示為ΔTavg，ΔTij的方差表示為μ，作為溫度梯度。

(3)

ΔTij=TCij-Tavg，

(4)

(5)

(6)

適應度決定染色體個體的生存機會，與算法的優化目標相關。本文適應度函數定義如下：

f=min{μ}。

(7)

映射屬于NP完全問題，為了優化溫度梯度，遺傳算法可以有效地解決該類優化問題，進行溫度梯度的優化，方法如下：

① 產生n個染色體組成的初始種群。每個染色體用整數編碼，染色體的基因與任務序號相對應，將任務分配到IP核上。其長度等于任務圖中的任務數。染色體中的每個基因表示一個任務，生成初始種群時，基因值對應任務圖中隨機選取的頂點標號。

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

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

圖5 交叉操作

圖6 變異操作

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

根據上述原則，在算法中設置種群大小為100，交換率為0.9，變異率為0.01，最大進化代數為1 500，染色體的長度等于IP核的類型數目。通過遺傳算法，選擇最優結果，將任務分配到相應的IP核。

2 實驗結果分析

2.1 實驗環境

為了驗證RMT策略的有效性，采用 4*4mesh、4*6mesh、6*6mesh、6*8mesh和8*8mesh這5種拓撲結構進行實驗。實驗中的任務分配將基于E3S[12]基準進行實現，E3S基準中包括來自EEMBC基準的automation/industrial，officeautomation，networking，telecommunication和consumer-electronic這5個基準組。每個基準程序由一個任務圖和預定的通信模式組成，E3S基準的詳細信息如表1所示。

表1 E3S基準規范

2.2 實驗結果

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

Peaktemperaturereduction=

式中，Hotspotreduction為熱點降低率；Hotspotrandom為隨機分布熱點平均個數；HotspotRMT為RMT分布熱點個數；Peaktemperaturereduction為峰值降低率；Peaktemperaturerandom為隨機分布峰值平均值；PeaktemperatureRMT為RMT峰值；Temperauregradientreduction為溫度梯度降低率；μRMT為RMT任務分配處理器溫度梯度；μrandom為隨機任務分配處理器溫度梯度。

如圖7、圖8和圖9所示，實驗選取4*4 mesh、4*6 mesh、6*6 mesh、6*8 mesh和8*8 mesh的網絡，將2種任務分配策略進行比較，峰值溫度降低率分別為3.66%、4.69%、3.51%、4.19%和2.95%，熱點降低率分別為26.61%、15.43% 、42.31%、12.6%和23.66%，溫度梯度降低 49.59%、23.13%、64.63%、77.49%和61.63%。可見經過RMT分配，系統的峰值溫度、熱點個數和溫度梯度都得到了明顯的降低，實現全局熱量分布均勻，提高了系統的可靠性和有效性。

圖7 峰值比較

圖8 熱點比較

圖9 溫度梯度比較

3 結束語

本文針對MPSoC中的散熱問題，提出了一種基于處理器核區域均溫的任務分配的方法。該方法充分考慮了處理器核溫度及其區域均溫對其溫度的影響，并通過遺傳算法進行任務分配的優化。與隨機任務分配策略相比，該策略降低了熱點個數和峰值溫度降低，同時降低了系統的溫度梯度，使得全局的熱量分布更加均勻。今后將針對散熱問題的實時溫度感知方面展開更為深入的研究。

[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

吉慧，周磊.一種針對多處理器片上系統的靜態任務分配方法[J].無線電工程,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

國家自然科學基金資助項目(61376025，61301111)；江蘇省高校自然科學基金資助項目(13KJB510039)；揚州市自然科學青年基金資助項目(SQN20150035)。

TN919

A

1003-3106(2017)08-0022-05

吉 慧 女，(1991—) ，碩士研究生。主要研究方向:電子系統集成和專用集成電路設計。

周 磊 男，(1980—) ，博士，講師。主要研究方向:電子系統集成和專用集成電路設計。