面向溫度優(yōu)化的片上網(wǎng)絡(luò)任務(wù)調(diào)度方法*

吉 慧，周 磊

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

1 引言

隨著半導(dǎo)體技術(shù)和集成電路技術(shù)的發(fā)展，單個(gè)芯片上可集成的IP(Intellectual Property)核越來(lái)越多，設(shè)計(jì)復(fù)雜度的提高和片上系統(tǒng)SoC(System on Chip)規(guī)模的擴(kuò)大使得傳統(tǒng)的基于總線的互連方式成為提升系統(tǒng)性能的瓶頸。因此，片上網(wǎng)絡(luò)NoC(Network-on-Chip)得到了發(fā)展，以實(shí)現(xiàn)眾核之間數(shù)據(jù)的高效傳輸[1 - 4]。由于片上網(wǎng)絡(luò)規(guī)模的擴(kuò)大，片上網(wǎng)絡(luò)的設(shè)計(jì)需要考慮的問(wèn)題越來(lái)越多，主要有拓?fù)浣Y(jié)構(gòu)設(shè)計(jì)[5,6]、路由算法[7,8]、交換機(jī)制[9]、任務(wù)調(diào)度、流量控制、QoS(Quality of Service)[10]、路由器結(jié)構(gòu)、資源網(wǎng)絡(luò)接口、性能評(píng)估[11]、定時(shí)和映射優(yōu)化[12]等多個(gè)問(wèn)題。并且，眾多學(xué)者在這些問(wèn)題上展開(kāi)了深入研究。

任務(wù)的初始分配情況直接決定了系統(tǒng)的功耗密度和熱量分布。當(dāng)系統(tǒng)處于運(yùn)行狀態(tài)時(shí)，由于通信功耗的不同可能會(huì)導(dǎo)致局部熱點(diǎn)的出現(xiàn)，動(dòng)態(tài)監(jiān)控并及時(shí)調(diào)整各區(qū)域的任務(wù)負(fù)載是實(shí)現(xiàn)系統(tǒng)溫度動(dòng)態(tài)管理的重要手段，因此任務(wù)調(diào)度對(duì)實(shí)現(xiàn)NoC溫度優(yōu)化非常重要。

目前，NoC的動(dòng)態(tài)溫度管理機(jī)制包括：時(shí)間性動(dòng)態(tài)溫度管理和空間性動(dòng)態(tài)溫度管理[13 - 16]。時(shí)間性動(dòng)態(tài)溫度管理機(jī)制通過(guò)采用臨時(shí)性措施降低熱點(diǎn)區(qū)域功耗來(lái)控制溫度。空間性動(dòng)態(tài)溫度管理機(jī)制采用任務(wù)遷移技術(shù)將過(guò)熱區(qū)域處理器中的任務(wù)遷移或者交換，讓其處于相對(duì)空閑狀態(tài)使得溫度降低。兩種動(dòng)態(tài)溫度管理機(jī)制相比，空間性動(dòng)態(tài)溫度管理的溫度控制對(duì)系統(tǒng)性能帶來(lái)的影響較小。空間性溫度管理機(jī)制包括集中式管理和分布式管理。前者通過(guò)將各節(jié)點(diǎn)溫度信息匯總傳送給中央控制器，中央控制器根據(jù)接收到的溫度消息判斷是否執(zhí)行任務(wù)調(diào)度操作。后者由NoC中各個(gè)處理器根據(jù)本地與其他區(qū)域節(jié)點(diǎn)的溫度對(duì)比，自行決定是否執(zhí)行任務(wù)調(diào)度。

在NoC系統(tǒng)中，各處理器均為同質(zhì)的CPU核，系統(tǒng)需要在運(yùn)行初期將等待運(yùn)行的任務(wù)分配到相應(yīng)CPU核之中。雖然在NoC初始運(yùn)行時(shí)期，任務(wù)分配算法通過(guò)合理分布任務(wù)位置優(yōu)化系統(tǒng)溫度，但是在系統(tǒng)運(yùn)行過(guò)程中，各區(qū)域的熱量分布和峰值溫度仍然會(huì)出現(xiàn)波動(dòng)。因此，在系統(tǒng)運(yùn)行期間實(shí)時(shí)監(jiān)控各區(qū)域溫度變化，并通過(guò)任務(wù)調(diào)度保障系統(tǒng)長(zhǎng)時(shí)間可靠地運(yùn)行是非常關(guān)鍵的。Ge等人[15]提出了基于神經(jīng)網(wǎng)絡(luò)溫度預(yù)測(cè)模型的任務(wù)調(diào)度方法。該方法將預(yù)測(cè)溫度與閾值溫度對(duì)比，交換處理器核中的任務(wù)，實(shí)現(xiàn)系統(tǒng)溫度動(dòng)態(tài)調(diào)節(jié)。但是，該方案中溫度預(yù)測(cè)模型需要的訓(xùn)練時(shí)間較長(zhǎng)，對(duì)隨機(jī)性任務(wù)負(fù)載突變情況不適用。Liu等人[16]提出了將平均溫度作為溫度閾值的任務(wù)調(diào)度算法DTM(Distributed Task Migration)。每經(jīng)過(guò)一次調(diào)度系統(tǒng)的平均溫度都會(huì)變化，隨之觸發(fā)條件也跟著改變，系統(tǒng)的任務(wù)遷移觸發(fā)次數(shù)得到了優(yōu)化。為了降低峰值溫度和均衡系統(tǒng)溫度，一種溫度感知任務(wù)調(diào)度啟發(fā)式被提出[17]。與現(xiàn)有的方法相比，該方法充分考慮了瞬時(shí)溫度、熱耦合和核的物理位置，使得峰值溫度降低4.48℃和溫度變化減少到45%。Sharifi等人[18]將頻率/電壓調(diào)節(jié)算法與任務(wù)調(diào)度算法相結(jié)合，并且使用耗盡算法搜索運(yùn)行新載入任務(wù)的處理器核。該方案使得功耗和系統(tǒng)峰值溫度得到優(yōu)化，但是較大的計(jì)算量帶來(lái)額外的計(jì)算功耗，反過(guò)來(lái)對(duì)整個(gè)系統(tǒng)的溫度又產(chǎn)生了一定的影響。楊鵬飛等人[19]設(shè)計(jì)了新任務(wù)模型，使其能夠更加真實(shí)地反映子任務(wù)間的制約關(guān)系，使其適于解決大規(guī)模任務(wù)調(diào)度問(wèn)題，克服了算法前期搜索過(guò)快的不足，其缺點(diǎn)是后期搜索能力下降，易陷入局部最優(yōu)。

以上現(xiàn)有的調(diào)度策略大部分考慮了系統(tǒng)的溫度，但是都沒(méi)有考慮到任務(wù)之間通信距離對(duì)系統(tǒng)溫度優(yōu)化帶來(lái)的影響。基于上述問(wèn)題，本文提出一種基于處理器間最短曼哈頓路徑的任務(wù)調(diào)度SMDS(Shortest Manhattan Distance Scheduling)方案。該方法首先給出核通信圖，將任務(wù)映射到NoC體系結(jié)構(gòu)圖上。當(dāng)系統(tǒng)的平均溫度高于觸發(fā)機(jī)制規(guī)定的閾值溫度時(shí)，則進(jìn)行任務(wù)調(diào)度。該調(diào)度方案啟動(dòng)任務(wù)調(diào)度的時(shí)候，選擇系統(tǒng)峰值溫度節(jié)點(diǎn)進(jìn)行任務(wù)調(diào)度。調(diào)度的目的節(jié)點(diǎn)選擇規(guī)則為尋找核通信圖中峰值節(jié)點(diǎn)對(duì)應(yīng)的目的節(jié)點(diǎn)，計(jì)算通信節(jié)點(diǎn)之間的最短曼哈頓路徑集，并且選擇其中平均溫度最低的一條路徑，選擇此條路徑上的節(jié)點(diǎn)與峰值溫度點(diǎn)進(jìn)行任務(wù)調(diào)度，采用模擬退火算法進(jìn)行任務(wù)調(diào)度的優(yōu)化，降低了遷移次數(shù)和平均跳數(shù)，達(dá)到系統(tǒng)溫度優(yōu)化的目的。

2 SMDS方案設(shè)計(jì)

2.1 任務(wù)調(diào)度問(wèn)題定義與描述

任務(wù)調(diào)度指的是NoC在運(yùn)行過(guò)程中，由于任務(wù)或通信量的變化，可能會(huì)出現(xiàn)局部熱點(diǎn)，當(dāng)處理器溫度情況滿足任務(wù)調(diào)度觸發(fā)機(jī)制的條件時(shí)，系統(tǒng)將啟動(dòng)任務(wù)調(diào)度機(jī)制。首先，熱點(diǎn)區(qū)域中的處理器將向其他區(qū)域發(fā)出任務(wù)調(diào)度請(qǐng)求，并收集反饋的溫度信息。然后，任務(wù)調(diào)度機(jī)制將根據(jù)接收到的信息確定任務(wù)調(diào)度對(duì)，并將溫度最低的處理器作為任務(wù)調(diào)度的目的節(jié)點(diǎn)。最后，溫度過(guò)熱的處理器將發(fā)送調(diào)度信息到目的處理器，從而完成任務(wù)調(diào)度操作。任務(wù)調(diào)度對(duì)整個(gè)NoC系統(tǒng)性能有著重要的影響。為了更好地分析調(diào)度問(wèn)題，下面提出一些定義和假設(shè)。

定義1給定核通信圖CCG(Core Communication Graph)，表示為CCG(C,A)，其中頂點(diǎn)Ci∈C表示一個(gè)IP核，ai,j∈A表示Ci到Cj之間的通信蹤跡。

定義2給定NoC架構(gòu)圖NAG(NoC Architecture Graph),表示為NAG(R,P)，其中ri∈R表示資源節(jié)點(diǎn)，Pi,j∈P表示ri到rj通信路徑。hi,j表示ri到rj之間的曼哈頓距離。

將CCG上每個(gè)IP核自動(dòng)分配到NoC構(gòu)架圖上。假設(shè)已經(jīng)確定C3與C2為任務(wù)調(diào)度對(duì)，當(dāng)系統(tǒng)滿足觸發(fā)機(jī)制條件時(shí)，執(zhí)行任務(wù)調(diào)度，具體任務(wù)調(diào)度過(guò)程如圖1所示。

Figure 1 Process diagram of task scheduling圖1 任務(wù)調(diào)度過(guò)程圖

針對(duì)2D Mesh片上網(wǎng)絡(luò)結(jié)構(gòu)，源節(jié)點(diǎn)i(xi,yi)和目的節(jié)點(diǎn)j(xj,yj)之間的曼哈頓距離可以表示為：

hi,j=|xi-xj|+|yi-yj|

在i(xi,yi) 和j(xj,yj)之間存在最適合調(diào)度的節(jié)點(diǎn)qt(t=1,2,…,r)。Thi,j是Ci到Cj這條路徑上所有處理器核的溫度總和。Tavg是Ci到Cj這條路徑上所有處理器核的平均溫度。

本文優(yōu)化的溫度采用系統(tǒng)的平均溫度。假設(shè)2D Mesh的規(guī)模為N*M,對(duì)于每個(gè)核Ci′j′(i′=1,2,3,…,N；j′=1,2,3，…,M),Ci′j′對(duì)應(yīng)處理核溫度為T(mén)Ci′j′,E為系統(tǒng)的平均溫度，表示如下：

假設(shè)任務(wù)調(diào)度前系統(tǒng)的平均溫度為Einitial，Enew為任務(wù)調(diào)度后系統(tǒng)的平均溫度，Ebest為平均溫度歷史最優(yōu)解。令Enew=Ebest=Einitial。令ΔE=Enew-Ebest。目標(biāo)函數(shù)定義為：

f=min{ΔE}(min{hi,j}中{Tavg})

(1)

選擇源節(jié)點(diǎn)對(duì)應(yīng)的所有目的節(jié)點(diǎn)的最短曼哈頓距離min{hi,j}中平均溫度最低min{Tavg}的路徑進(jìn)行調(diào)度。基于上述定義，結(jié)合下文提出的任務(wù)調(diào)度方案，最終使得目標(biāo)函數(shù)式(1)的結(jié)果盡可能優(yōu)化。

2.2 任務(wù)調(diào)度策略

2.2.1 搜索算法

任務(wù)調(diào)度是在片上網(wǎng)絡(luò)任務(wù)分配后系統(tǒng)運(yùn)行期間出現(xiàn)溫度分布不均的情況下進(jìn)行的任務(wù)位置的交換操作。當(dāng)給定已經(jīng)進(jìn)行任務(wù)分配后的NoC架構(gòu)圖，根據(jù)CCG，通過(guò)搜索算法選擇任務(wù)調(diào)度的目的節(jié)點(diǎn)。任務(wù)遷移對(duì)搜索算法設(shè)計(jì)步驟具體如下：

步驟1當(dāng)系統(tǒng)進(jìn)入運(yùn)行狀態(tài)，達(dá)到觸發(fā)條件，選擇需要調(diào)度的節(jié)點(diǎn)i(xi,yj)。

步驟2根據(jù)CCG，選擇節(jié)點(diǎn)i(xi,yi)需要調(diào)度的目的節(jié)點(diǎn)j(xj,yj)。目的節(jié)點(diǎn)選取規(guī)則：根據(jù)CCG，選擇節(jié)點(diǎn)i(xi,yi)在CCG中的所有目的節(jié)點(diǎn)，形成集合D=[j1,j2,j3,…,jn],n=1,2,3,…,k。

步驟3將i與D的每個(gè)子集之間的最短曼哈頓路徑中平均溫度最低的路徑形成集合Pi，Pi=[Pi,j1,Pi,j2,Pi,j3,…,Pi,jn],假設(shè)Pi,jn路徑中的每個(gè)節(jié)點(diǎn)形成集合Q,由離選中的節(jié)點(diǎn)i(xi,yi)距離由近到遠(yuǎn)形成集合Q，Q=[q1,q2,q3,…,qt],t=1,2,3,…,r。

步驟4選擇i與Pi中平均溫度最低的路徑Pi,jn中的節(jié)點(diǎn)進(jìn)行任務(wù)調(diào)度。Pi,jn中的被調(diào)度目的節(jié)點(diǎn)選擇按照集合Q中t由小到大與i(xi,yi)依次進(jìn)行調(diào)度。

2.2.2 優(yōu)化算法

模擬退火算法是一種通用的概率演算法，能夠?qū)崿F(xiàn)全局優(yōu)化[20]。本文提出了一種根據(jù)最短曼哈頓距離并基于模擬退火算法的任務(wù)調(diào)度算法。上述調(diào)度方法經(jīng)過(guò)模擬退火算法的優(yōu)化，可以在保證算法高效的前提下，減少任務(wù)在調(diào)度過(guò)程中的遷移次數(shù)和調(diào)度完成后執(zhí)行整個(gè)任務(wù)圖通信所需的平均跳數(shù)，提升系統(tǒng)性能。具體方案如下：

(1)初始化。假設(shè)系統(tǒng)的峰值溫度為T(mén)I。初始選中的峰值溫度為T(mén)0，此時(shí)系統(tǒng)平均溫度為Einitial。令Enew=Ebest=Einitial。令△E=Enew-Ebest。

(2)對(duì)于選中的峰值節(jié)點(diǎn)，按照調(diào)度規(guī)則，找到與之最適應(yīng)調(diào)度的目的節(jié)點(diǎn)，調(diào)度后系統(tǒng)平均溫度作為Enew。

(3)若ΔE<0，則Ebest=Enew，并且進(jìn)行任務(wù)調(diào)度，然后選擇下一個(gè)峰值溫度點(diǎn)，繼續(xù)按此方案進(jìn)行任務(wù)調(diào)度對(duì)的確定。否則直接尋找下一個(gè)峰值溫度點(diǎn)更新TI。

(4)重復(fù)(2)～(3)，直到達(dá)到目標(biāo)函數(shù)，即直到系統(tǒng)平均溫度基本不變，則停止任務(wù)調(diào)度。

(5)輸出最優(yōu)解，計(jì)算遷移次數(shù)和平均跳數(shù)。

2.2.3 調(diào)度實(shí)例

通過(guò)搜索算法尋找到最優(yōu)任務(wù)調(diào)度對(duì)后，完成任務(wù)調(diào)度，再利用模擬退火算法完成目標(biāo)函數(shù)的優(yōu)化，使得整個(gè)系統(tǒng)溫度得到優(yōu)化。假設(shè)3*3 mesh,有9個(gè)任務(wù)已經(jīng)分配到NoC架構(gòu)圖中。具體調(diào)度過(guò)程實(shí)現(xiàn)如圖2所示。

Figure 2 An instance of the SMDS scheme圖2 SMDS方案實(shí)例

3 實(shí)驗(yàn)與分析

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

(1)溫度仿真軟件：本文使用HotSpot[21]進(jìn)行溫度仿真。通過(guò)輸入各個(gè)處理器核功耗，HotSpot將會(huì)產(chǎn)生每個(gè)核的溫度(溫度包括瞬態(tài)溫度和穩(wěn)態(tài)溫度)。在本實(shí)驗(yàn)中溫度指的是系統(tǒng)的穩(wěn)態(tài)溫度，具體的配置信息如表1所示。

(2)測(cè)試樣例：采用E3S[22]基準(zhǔn)進(jìn)行實(shí)驗(yàn)。E3S基準(zhǔn)中包括來(lái)自EEMBC基準(zhǔn)的automation/industrial，office automation，networking，telecom-munication 和consumerelectronic 5個(gè)基準(zhǔn)組。每個(gè)基準(zhǔn)程序由一個(gè)任務(wù)圖和預(yù)定的通信模式組成，表2展示了E3S測(cè)試樣例組件的詳細(xì)信息。

Table 1 HotSpot configuration information表1 HotSpot配置信息

3.2 結(jié)果分析

實(shí)驗(yàn)分別從任務(wù)遷移次數(shù)與平均跳數(shù)兩個(gè)方面對(duì)SMDS策略與DT策略進(jìn)行比較。為了驗(yàn)證SMDS策略的有效性，采用6*6、8*8和10*10 mesh NoC拓?fù)浣Y(jié)構(gòu)進(jìn)行實(shí)驗(yàn)。本文進(jìn)行了6次實(shí)驗(yàn)，測(cè)試過(guò)程中的測(cè)試樣例全部取自E3S測(cè)試樣例組件，針對(duì)本文選擇的36個(gè)、64個(gè)和100個(gè)處理器將任意執(zhí)行測(cè)試樣例中的一個(gè)任務(wù)。任務(wù)調(diào)度方法觸發(fā)機(jī)制的設(shè)定對(duì)任務(wù)調(diào)度的觸發(fā)起到關(guān)鍵作用。假設(shè)節(jié)點(diǎn)溫度超過(guò)溫度閾值85℃時(shí)會(huì)觸發(fā)SMDS任務(wù)調(diào)度算法。

Table 2 E3S benchmark specification表2 E3S測(cè)試樣例

任務(wù)遷移次數(shù)定義為在實(shí)驗(yàn)過(guò)程中任務(wù)遷移過(guò)程的次數(shù)，如表3所示。平均跳數(shù)定義為通過(guò)模擬退火算法后，f達(dá)到最小時(shí)，完成整個(gè)CCG需求時(shí)的平均跳數(shù)，如表4所示。通過(guò)表3和表4可以得到遷移次數(shù)平均降低率和平均跳數(shù)平均降低率。遷移次數(shù)平均降低率定義為6次實(shí)驗(yàn)遷移次數(shù)降低率的平均值，如圖3所示。平均跳數(shù)平均降低率定義為6次實(shí)驗(yàn)平均跳數(shù)降低率的平均值，如圖4所示。

Figure 3 Average reduction of migrations圖3 遷移次數(shù)平均降低率

由實(shí)驗(yàn)看出，SMDS策略對(duì)于解決任務(wù)調(diào)度問(wèn)題是非常有效的。DTM策略通過(guò)系統(tǒng)的全局搜索，尋找任務(wù)調(diào)度目的節(jié)點(diǎn)，其空間復(fù)雜度為O(n2)。而SMDS策略沿著任務(wù)調(diào)度對(duì)之間的最短曼哈頓距離進(jìn)行任務(wù)調(diào)度目的節(jié)點(diǎn)的搜索，其空間復(fù)雜度為O(n)。隨著系統(tǒng)規(guī)模的擴(kuò)大，SMDS策略明顯優(yōu)于DTM策略。SMDS策略在實(shí)現(xiàn)目標(biāo)函數(shù)的過(guò)程中，系統(tǒng)的溫度得到了優(yōu)化。SMDS策略在確定任務(wù)遷移對(duì)的過(guò)程中，以遷移后是否降低系統(tǒng)平均溫度為依據(jù)，決定是否同意本次任務(wù)遷移，挑選最終的任務(wù)遷移目的節(jié)點(diǎn)，實(shí)驗(yàn)通過(guò)遷移次數(shù)的降低，實(shí)現(xiàn)額外功耗的減小，降低系統(tǒng)的溫度。如表3和圖3所示，與DTM策略相比，針對(duì)6*6、8*8和10*10的拓?fù)浣Y(jié)構(gòu)，SMDS實(shí)驗(yàn)方案在遷移次數(shù)方面分別優(yōu)化了(10%～31.58%)、(16.92%～28.21%)和(18.12%～28.95%)，平均優(yōu)化率分別為22.08%、21.74%和23.02%。 此外，如表4和圖4所示，與DTM策略相比，針對(duì)6*6、8*8和10*10的拓?fù)浣Y(jié)構(gòu)，SMDS實(shí)驗(yàn)方案在平均跳數(shù)方面分別優(yōu)化了(9.89%～34.28%)、(18.19%～37.22%)和(19.18%～27.16%)，平均優(yōu)化率分別為24.04%、29.18%和23.04%，實(shí)現(xiàn)了通信功耗的降低和系統(tǒng)溫度的優(yōu)化。

Table 3 Number of migrations表3 遷移次數(shù)

Table 4 Number of average hops表4 平均跳數(shù)

Figure 4 Average reduction of average hops圖4 平均跳數(shù)平均降低率

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

針對(duì)片上網(wǎng)絡(luò)中的任務(wù)調(diào)度問(wèn)題，本文提出了SMDS方法。該方法充分考慮了核通信圖中任務(wù)調(diào)度對(duì)之間的最短曼哈頓距離，通過(guò)模擬退火算法進(jìn)行任務(wù)調(diào)度的優(yōu)化。本文選擇優(yōu)化的目標(biāo)為遷移次數(shù)和平均跳數(shù)。遷移次數(shù)的降低可以減少系統(tǒng)在任務(wù)調(diào)度過(guò)程中的額外功耗。平均跳數(shù)的減少可以縮小系統(tǒng)中通信節(jié)點(diǎn)之間的距離，因此可以降低節(jié)點(diǎn)之間的通信功耗。本文選取6*6、8*8和10*10的拓?fù)浣Y(jié)構(gòu)，并與傳統(tǒng)的DTM策略相比，SMDS策略在實(shí)現(xiàn)目標(biāo)函數(shù)的過(guò)程中，不僅使得系統(tǒng)的溫度得到了優(yōu)化，同時(shí)在遷移次數(shù)和平均跳數(shù)方面均得到了明顯的改善，遷移次數(shù)和平均跳數(shù)優(yōu)化率分別為(22.08%、21.74%和23.02%)和(24.04%、29.18%和23.04%)。今后將針對(duì)片上網(wǎng)絡(luò)半實(shí)物仿真平臺(tái)方面展開(kāi)更為深入的研究。