吉 慧，周 磊

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

1 引言

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

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

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

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

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

2 SMDS方案設計

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

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

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

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

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

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

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

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

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

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

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

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

(1)

選擇源節(jié)點對應的所有目的節(jié)點的最短曼哈頓距離min{hi,j}中平均溫度最低min{Tavg}的路徑進行調(diào)度?；谏鲜龆x，結(jié)合下文提出的任務調(diào)度方案，最終使得目標函數(shù)式(1)的結(jié)果盡可能優(yōu)化。

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

2.2.1 搜索算法

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

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

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

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

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

2.2.2 優(yōu)化算法

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

(1)初始化。假設系統(tǒng)的峰值溫度為TI。初始選中的峰值溫度為T0，此時系統(tǒng)平均溫度為Einitial。令Enew=Ebest=Einitial。令△E=Enew-Ebest。

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

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

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

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

2.2.3 調(diào)度實例

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

Figure 2 An instance of the SMDS scheme圖2 SMDS方案實例

3 實驗與分析

3.1 實驗環(huán)境

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

(2)測試樣例：采用E3S[22]基準進行實驗。E3S基準中包括來自EEMBC基準的automation/industrial，office automation，networking，telecom-munication 和consumerelectronic 5個基準組。每個基準程序由一個任務圖和預定的通信模式組成，表2展示了E3S測試樣例組件的詳細信息。

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

3.2 結(jié)果分析

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

Table 2 E3S benchmark specification表2 E3S測試樣例

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

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

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

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