片上互連網(wǎng)絡(luò)的功耗特征分析與優(yōu)化*

孫曉樂,錢亞龍,齊新新,張云放,陳 娟,袁 遠(yuǎn),董 勇

(國防科技大學(xué)計算機(jī)學(xué)院，湖南 長沙 410073)

1 引言

隨著半導(dǎo)體工藝技術(shù)的發(fā)展與進(jìn)步，單芯片晶體管的數(shù)量也在不斷地增長，帶來了互連延遲增大、存儲帶寬受限、功耗密度極限等問題。計算機(jī)體系結(jié)構(gòu)研究者不斷地采取包括提高頻率、指令并行等技術(shù)來提高處理器性能，但這些不可避免地帶來了功耗的急劇上升。與此同時，處理器性能提升的減緩，導(dǎo)致了處理器體系結(jié)構(gòu)的改變，研究人員轉(zhuǎn)向設(shè)計多核處理器。盡管多核乃至眾核處理器的出現(xiàn)極大提高了處理器的性能，但還是面臨著延遲較大、可擴(kuò)展性差、帶寬較低和功耗較高等方面的挑戰(zhàn)[1]。片上互連網(wǎng)絡(luò)NoC(Network-on-Chip)的出現(xiàn)很好地避免了這些缺陷。片上互連網(wǎng)絡(luò)將傳統(tǒng)網(wǎng)絡(luò)中報文交換的思想引入芯片內(nèi)部的通信機(jī)制里，迅速成為眾核處理器片上通信設(shè)計的標(biāo)準(zhǔn)[2]。

NoC設(shè)計中最關(guān)鍵的問題之一是應(yīng)用處理的能耗效率。正如文獻(xiàn)[3]中所指出的，NoC能耗占芯片總能耗的絕大部分。很多學(xué)者從硬件設(shè)計的角度減少應(yīng)用的通信能耗。Mineo等[4]提出運(yùn)行時調(diào)整路由器鏈路電壓，從而降低信號在交叉桿和鏈路中的電壓波動。Charles等[5]研究了應(yīng)用在不同內(nèi)存模式、處理器核親和性模式配置下，目錄與內(nèi)存控制器數(shù)據(jù)傳輸?shù)臒狳c(diǎn)問題，為不同應(yīng)用的運(yùn)行提供了相應(yīng)的配置。Yang等[6]基于 STT-RAM(Spin-Torque Transfer Magnetic RAM)的路由器，通過計算爭用的flit來減少通信能耗。

這些方法都依賴于特定的硬件條件，眾多研究人員則從軟件優(yōu)化的角度，在應(yīng)用映射時提高其局部性，減少通信能耗。Zhu等[7]通過多應(yīng)用的啟發(fā)式映射，在性能感知的情況下平衡最小的片上數(shù)據(jù)包延遲，減少能耗。Pang等[8]提出了一種分支界定算法，將IP核映射到基于區(qū)塊架構(gòu)的NoC，同時滿足帶寬約束并最小化總通信能耗。Reza等[9]針對多核處理器上的深度神經(jīng)網(wǎng)絡(luò)應(yīng)用，提出了一種高效的集中式的NoC架構(gòu)和一種負(fù)載均衡的映射解決方案來加速深度神經(jīng)網(wǎng)絡(luò)，減少通信開銷。

盡管眾多映射方法的出發(fā)點(diǎn)有所差別，但是保證了應(yīng)用在片上的通信距離盡可能小，以此來保證較低的通信開銷。為此本文針對一種典型的凸區(qū)域增量映射方法INC(INCremental mapping)[10]，分析改進(jìn)其區(qū)域選擇的相關(guān)參數(shù)并提出了新的映射算法。通過實(shí)驗(yàn)表明，新的算法相較于INC減少了12.10%的通信功耗并且?guī)砹?1.23%的通信延遲優(yōu)化。

本文第2節(jié)介紹了典型NoC案例包括FT-2000和KNL，以及任務(wù)映射問題描述；第3節(jié)詳細(xì)闡述了改進(jìn)的參數(shù)以及新的映射算法；第4節(jié)給出了改進(jìn)算法(our)在NIRGAM(NoC Interconnect Routing and Application Modeling)[11]模擬器中的實(shí)驗(yàn)結(jié)果，并且與常見的2種算法以及INC進(jìn)行了比較；第5節(jié)為本文總結(jié)，并指出了進(jìn)一步的工作方向。

2 NoC典型案例及任務(wù)映射問題描述

2.1 NoC典型案例

目前，處理器已經(jīng)進(jìn)入多核時代。一般核數(shù)小于或等于8個的處理器被稱為多核處理器，具有更多核數(shù)的處理器被稱為眾核處理器。目前關(guān)于片上互連網(wǎng)絡(luò)的理論研究部分已經(jīng)投入工業(yè)生產(chǎn)中。

2.1.1 飛騰(PHYTIUM)FT-2000

FT-2000處理器芯片集成64個自主開發(fā)的基于ARMv8處理器核心，兼容處理器內(nèi)核FTC662，采用片上并行系統(tǒng)(PSoC)體系結(jié)構(gòu)。通過集成高效處理器核心、基于數(shù)據(jù)親和的大規(guī)模性存儲架構(gòu)、層次式二維Mesh互連網(wǎng)絡(luò)，優(yōu)化存儲訪問延時，提供業(yè)界領(lǐng)先的計算性能、訪存帶寬和IO擴(kuò)展能力。

2.1.2 Intel Knight Landing

KNL(KNight Landing) 是Intel首款專門針對高度并行工作負(fù)載而設(shè)計的可獨(dú)立自啟動的主處理器，并首次實(shí)現(xiàn)了內(nèi)存與高速互連技術(shù)的集成。KNL單顆芯片最大支持72個CPU物理核心，16 GB片上高速內(nèi)存，384 GB DDR4系統(tǒng)內(nèi)存，單CPU的雙精度浮點(diǎn)峰值超過3 TFlops，可以為高并行負(fù)載應(yīng)用提供強(qiáng)大的性能支持。Intel在Knight Landing中引入了新的片內(nèi)總線：Mesh取代了雙環(huán)(Dual Ring),它是一種2D的Mesh網(wǎng)絡(luò)。

2.2 任務(wù)映射問題描述

映射到片上互連網(wǎng)絡(luò)的所有應(yīng)用程序都由程序任務(wù)圖描述。如圖1所示是一個程序的應(yīng)用通信圖ACG(Application Communication Graph)。一個ACG圖包括通信節(jié)點(diǎn)及其電壓水平、通信邊及權(quán)重，ACG圖中的一個通信節(jié)點(diǎn)代表實(shí)際應(yīng)用程序的一個進(jìn)程或一個子任務(wù)。該ACG圖映射到如圖2所示的4×4共16個tile的片上互連網(wǎng)絡(luò)結(jié)構(gòu)上。圖2中，有黑色圓圈的矩形代表該tile已經(jīng)被映射了應(yīng)用程序，不可再被其他應(yīng)用程序映射。故tile 0已經(jīng)有了對應(yīng)的應(yīng)用程序，不能重復(fù)被映射?；疑匦螀^(qū)域代表這個tile是高電平，其余區(qū)域?qū)?yīng)低電平。應(yīng)用程序中的節(jié)點(diǎn)v4和v6必須映射到高電平tile上，而tile 5～tile 7是高電平，其余都是低電平。節(jié)點(diǎn)之間按照任務(wù)圖進(jìn)行通信。

Figure 1 ACG of a program[10]圖1 一個程序的應(yīng)用通信圖[10]

Figure 2 Structure of NoC圖2 片上互連網(wǎng)絡(luò)結(jié)構(gòu)圖

一個新的應(yīng)用(如圖1所示)到達(dá)系統(tǒng)，并映射到片上互連網(wǎng)絡(luò)(如圖2所示)，使得功耗最優(yōu)化的過程可以抽象為：

給定條件：當(dāng)前系統(tǒng)的狀態(tài)(包括處理單元PE(Processing Elements)的使用狀態(tài)以及電壓水平)，新應(yīng)用的ACG圖。

目標(biāo)：找到一個區(qū)域R以及一個映射map()，使得對于任意節(jié)點(diǎn)vi∈V,map(vi)→PEi,使得:

最小化。

其中,V是ACG圖中的節(jié)點(diǎn)集合，ei,j是節(jié)點(diǎn)vi到vj的邊，w(ei,j)是邊ei,j的權(quán)重，MD是映射到片上互連網(wǎng)絡(luò)節(jié)點(diǎn)的曼哈頓距離。W是加權(quán)后的通信距離，根據(jù)Chou等[10]的論文，片上互連網(wǎng)絡(luò)的通信能耗和通信距離成正比。因此,能耗問題可轉(zhuǎn)化為曼哈頓距離問題。

定義1L(R)：由N個PE組成的一個區(qū)域R中任意2個PE之間曼哈頓距離之和。

解決的問題：對于一個已經(jīng)映射過應(yīng)用的系統(tǒng)，共有M個PE可用，假設(shè)新來一個包含N個節(jié)點(diǎn)的應(yīng)用(N

Figure 3 Minimization problem：Select a region,such that the sum of the totalMDbetween any pair of tiles inside regionsR1andR-R1is minimized圖3 L(R1)+L(R-R1)最小化問題

L(R1)最小化使得需要映射的應(yīng)用節(jié)點(diǎn)間的通信代價最小化，L(R1)+L(R-R1)最小化是從整個系統(tǒng)出發(fā)，使得新應(yīng)用映射結(jié)束后，剩余PE離散化的程度小，使得整體通信代價小。因此，本文采用這2個指標(biāo)來比較改進(jìn)映射算法和未改進(jìn)算法的優(yōu)劣。

3 改進(jìn)區(qū)域選擇算法并提出新的映射算法

由于目標(biāo)應(yīng)用程序的到達(dá)順序不是可預(yù)測或已知的，在多處理器片上系統(tǒng)(MPSoC)中實(shí)現(xiàn)有效的運(yùn)行時映射是一項具有挑戰(zhàn)性的任務(wù)。Chou等[10]提出了一種有效的啟發(fā)式映射算法(包括區(qū)域選擇和節(jié)點(diǎn)分配)，用來解決具有多個電壓電平的NoC的能量和性能感知的增量映射問題。該算法是一個2步算法，分為近凸區(qū)域選擇算法和節(jié)點(diǎn)分配算法。所提出的算法允許以最小的處理器間開銷將新的應(yīng)用添加到系統(tǒng)。與使用任意映射方案相比，該算法極大地降低了能耗。

通常，如果區(qū)域包含連接其中任何一對點(diǎn)的所有線段，則該區(qū)域是凸的。近凸區(qū)域選擇算法通過計算待選擇PE的分散因子與離散因子的和，來逐步確定對應(yīng)片上互連網(wǎng)絡(luò)的映射區(qū)域。實(shí)際上，發(fā)現(xiàn)選擇的區(qū)域近似凸形。

在選擇近凸區(qū)域之后，將輸入應(yīng)用的節(jié)點(diǎn)分配給具有所選區(qū)域中的特定電壓電平的PE，同時最小化處理器間通信。使用其總通信量的非遞增順序?qū)⒐?jié)點(diǎn)分類為有序集，即節(jié)點(diǎn)具有的通信量越大，發(fā)現(xiàn)或完成得越早。按照該有序集對應(yīng)用的節(jié)點(diǎn)一一分配，每分配一個，計算可用區(qū)域內(nèi)該節(jié)點(diǎn)對應(yīng)每一個位置的通信距離，選擇距離最小的位置。

3.1 區(qū)域選擇算法

Chou的區(qū)域選擇算法通過計算待選擇PE的分散因子與離散因子的和，來逐步確定對應(yīng)片上互連網(wǎng)絡(luò)的映射區(qū)域。這2個因子是整個區(qū)域選擇算法中最核心的部分。

3.1.1 分散因子的改進(jìn)

Chou對片上互連網(wǎng)絡(luò)的PE的分散因子定義為D(PE)=C-該P(yáng)E使用鄰居的數(shù)量，其中C是常數(shù)，其選擇是根據(jù)經(jīng)驗(yàn)，對于角落PE，C= 3;對于其他PE(包括邊界)，C= 4。對于區(qū)域選擇而言，具有較小D(PE)值的PE表示該P(yáng)E被包括在當(dāng)前區(qū)域中的可能性較高。實(shí)際上，其大多數(shù)鄰居被使用的PE(即具有小D(PE)值的PE)很可能后來被隔離，所以將該P(yáng)E添加到區(qū)域中有助于降低其分散概率。

但是，經(jīng)過分析，我們認(rèn)為分散因子的定義有如下問題，首先常數(shù)C的選取沒有充分的理由，是靠經(jīng)驗(yàn)得出的，事實(shí)上邊界PE和中間PE的鄰居數(shù)分別是3和4，情況有所區(qū)別，不能統(tǒng)一定義為C=4;其次最優(yōu)化的區(qū)域選擇考慮的是全局的最優(yōu)化，不但要使得當(dāng)前應(yīng)用映射區(qū)域的通信距離最優(yōu)化，還要使得余下的區(qū)域通信距離盡可能小。Chou提出的分散因子對于PE只考慮了與其鄰居的使用情況，未能衡量全局通信距離。

分散因子D實(shí)際上是衡量一個PE可使用的鄰居數(shù)量的指標(biāo)，當(dāng)前可使用鄰居數(shù)量越少，其被選入到區(qū)域中的可能性越大。

為此，我們改進(jìn)Chou關(guān)于分散因子的定義。PE的分散因子D定義為：D(PE)=該P(yáng)E能夠使用的鄰居數(shù)量和鄰居的曼哈頓路徑覆蓋的PE。如圖4所示，PE5的鄰居節(jié)點(diǎn)包括PE1、PE4、PE6、PE9，按照XY路由規(guī)則，從PE4到PE1需要經(jīng)過PE5，圖中白色箭頭指示方向；而從PE1到PE4需要經(jīng)過PE0，圖中黑色箭頭指示方向，PE0和PE5就是鄰居PE1和PE4的曼哈頓路徑覆蓋。因此對于未分配的Mesh結(jié)構(gòu)而言，角落PE分散因子為3個PE(2個鄰居+1個覆蓋)、邊界PE分散因子為5個PE(3個鄰居+2個覆蓋)、中間PE分散因子為8個PE(4個鄰居+4個覆蓋)。

Figure 4 Neighbor nodes and Manhattan overlay nodes圖4 鄰居節(jié)點(diǎn)及曼哈頓覆蓋節(jié)點(diǎn)示意圖

圖5所示是對一個已經(jīng)映射應(yīng)用的系統(tǒng)通過啟發(fā)因子選擇4個PE的結(jié)果。黑色圓表示該P(yáng)E已經(jīng)被使用，白色三角形是新來應(yīng)用分配的區(qū)域。圖5a只考慮鄰居，圖5b考慮鄰居以及鄰居的曼哈頓覆蓋，可以明顯看出，2種離散因子選擇出的L(R1)是相同的，但是圖5b的L(R1)+L(R-R1)小于圖5a的，剩余區(qū)域更加緊湊，有利于后續(xù)應(yīng)用的映射，并降低整個系統(tǒng)通信能耗。

倒是在一邊旁觀者清的葉總有些好奇，便出聲詢問王祥整個事件的來龍去脈。王祥開始還遮遮掩掩，不過當(dāng)著兩位老板的面也編不出什么高明的謊話，便把事情經(jīng)過避輕就重地給兩位老總說了一遍。從他們從老家偶得玉石到城里擺攤巧遇老道，最后一起說服胖子成交，再到如何和老道分道揚(yáng)鑣，王祥都如實(shí)講了出來。最后，王祥還向葉、錢兩位老總展示了自己留作紀(jì)念的玉墜，證明確有其事。

Figure 5 Mapping comparasion圖5 映射對比圖

3.1.2 離心因子的改進(jìn)

Chou對片上互連網(wǎng)絡(luò)的PE的離心因子定義為：C(PE)為任何PE與當(dāng)前區(qū)域的邊界之間的曼哈頓距離。

對于區(qū)域選擇而言，離心因子較小的PE被包括在當(dāng)前區(qū)域中的可能性較高。實(shí)際上，由于區(qū)域中的每個PE應(yīng)該都接近該區(qū)域的邊界，因此具有較小離心因子的PE更適合于添加到區(qū)域中。

但是，對于離心因子若只考慮PE到當(dāng)前區(qū)域的邊界，選擇的PE雖然離當(dāng)前區(qū)域的距離較近，但是對于選擇后的區(qū)域而言，并不能保證新加入的PE使得整體的通信距離最優(yōu)。

為此我們改進(jìn)Chou關(guān)于離心因子的定義。PE離心因子C(PE)被定義為任何PE與當(dāng)前區(qū)域邊界PE的最大曼哈頓距離。離心因子反映的是PE到當(dāng)前區(qū)域的位置關(guān)系，以最遠(yuǎn)距離來衡量，在保證相鄰的基礎(chǔ)上，使得區(qū)域平衡地進(jìn)行擴(kuò)張，同時也保證新加入的PE到最遠(yuǎn)邊界的距離不會太大。

圖6用一個簡單的示例說明了改進(jìn)的離心因子和分散因子的效果。如圖6所示，黑色圓代表已經(jīng)使用的PE，白色三角形為新應(yīng)用分配的區(qū)域，假設(shè)N=10，在當(dāng)前區(qū)域基礎(chǔ)上增加1個PE。在Chou的算法中，由于PE1～PE5都有1個鄰居被使用且與當(dāng)前區(qū)域相鄰，D(PE)=4-1=3，C(PE)=1，都是相同的，算法比較的啟發(fā)因子相同，因此會隨機(jī)選擇，甚至?xí)葱蛱栠x擇。若使用改進(jìn)后的算法，待選PE的啟發(fā)因子，以及加入到當(dāng)前區(qū)域后的L(R1)和L(R-R1)計算結(jié)果如表1所示。

Figure 6 Mapping example(choosing one PE to current region by differentDandC)圖6 映射示例(考慮下一步選入?yún)^(qū)域的PE)

表1 改進(jìn)算法待選節(jié)點(diǎn)的啟發(fā)因子及新區(qū)域的L(R1)和L(R1)+L(R-R1)比較

如果只考慮離心因子C，C(PE3)和C(PE4)最小，其L(R1)是最小的，加上分散因子D，D(PE5)+C(PE5)是最小的，加入PE5后區(qū)域L(R1)+L(R-R1)最小。通過這個例子可以看出，改進(jìn)算法中的離心因子C側(cè)重于新加PE使得新區(qū)域內(nèi)部通信距離最小化，分散因子D側(cè)重于全局，保證剩余區(qū)域是集中的，方便后續(xù)應(yīng)用映射，提升全局性能。

3.1.3 改進(jìn)算法效果

我們對已經(jīng)映射過應(yīng)用的區(qū)域進(jìn)行討論，考慮其在整個系統(tǒng)中的位置分別為：聚集在某一角落(gather in the corner)、聚集在中心位置(gather in the center)以及在系統(tǒng)中碎片化分布(fragmentation distribution)。分別采用Chou和改進(jìn)后的區(qū)域選擇算法，比較L(R1)和L(R1)+L(R-R1) 2項指標(biāo)。

考慮到在實(shí)際應(yīng)用中會分配一個PE作為GM(Global Manager)，其作用是運(yùn)行區(qū)域選擇算法，為新到的應(yīng)用選擇資源，并在選定區(qū)域運(yùn)行映射算法。如圖7所示，在7×7的2D Mesh網(wǎng)絡(luò)中，第1個PE作為GM，白色圓表示已經(jīng)使用的PE。我們在7×7的2D Mesh網(wǎng)絡(luò)中考慮了多種情況，圖7a假定4個被占用的PE聚集在左上角；圖7b假定5個被占用的PE聚集在中心位置；圖7c和圖7d假定8個被占用的PE碎片化分布，利用隨機(jī)數(shù)生成工具生成區(qū)間在1～48共8個不重復(fù)的隨機(jī)數(shù)，作為被占用的PE號碼(片上互連網(wǎng)絡(luò)的PE編號按照從左到右、自上而下的順序?qū)?yīng)0號到48號)，得到圖7c和圖7d 2種情況。

Figure 7 Four different system mappings圖7 4種不同的系統(tǒng)映射情況

考慮到實(shí)際應(yīng)用通信節(jié)點(diǎn)規(guī)模的不同，對于上述4種PE使用情況的系統(tǒng)，對于新到應(yīng)用考慮其節(jié)點(diǎn)數(shù)目分別從N=3開始到N達(dá)到最大可用PE數(shù)目，對于corner和centerN取3～42各40種情況，對于random1和random2N各取3～39各37種情況，所以實(shí)驗(yàn)共考慮154種情況，分別采用Chou和改進(jìn)后的區(qū)域選擇算法，比較L(R1)和L(R1)+L(R-R1) 2項指標(biāo)。

圖8和圖9分別是L(R1)和L(R1)+L(R-R1)的比較結(jié)果，我們使用改進(jìn)算法比Chou區(qū)域選擇算法減少通信距離的百分比為衡量指標(biāo)，也就是對L(R1)和L(R1)+L(R-R1)降低的百分比。對提升結(jié)果進(jìn)行排序，位于0以上部分表示改進(jìn)算法提升性能，位于0以下部分表示改進(jìn)算法不能提升性能。

從L(R1)的結(jié)果中可以看出,改進(jìn)算法對于corner和center 2種情況性能改善比較好，分別獲得4.89%和2.83%的性能提升，對于random1和random2 2種情況效果并不顯著，4種系統(tǒng)情況，154個實(shí)驗(yàn)平均可以獲得1.45%的性能提升。從的結(jié)果上看出，幾乎柱狀圖的大部分位于0以上，corner、center、random1、random2分別獲得6.29%,2.03%,0.20%,1.47%的性能提升，平均亦獲得了2.5%的性能提升。尤其對于random2而言，雖然對于L(R1)的性能提升并不明顯，但是考慮到系統(tǒng)整體，其L(R1)+L(R-R1)提升顯著。從4種系統(tǒng)實(shí)驗(yàn)結(jié)果的比較可以看出，改進(jìn)算法更適合corner和center 2種情況，同時在碎片化分布上并不比Chou算法的差，甚至在L(R1)+L(R-R1)上要優(yōu)于Chou算法的。

Figure 8 L(R1) performance improvement of improved algorithm in different initial systems圖8 不同初始系統(tǒng)下改進(jìn)算法L(R1)性能提升圖

Figure 9 L(R1)+L(R-R1) performance improvement ofimproved algorithm in different initial systems圖9 不同初始系統(tǒng)下改進(jìn)算法L(R1)+L(R-R1)性能提升圖

實(shí)驗(yàn)說明改進(jìn)的算法與Chou算法相比，在保證當(dāng)前應(yīng)用映射區(qū)域通信能耗較小的基礎(chǔ)上，更加注重在系統(tǒng)級減少通信能耗，為后續(xù)程序提供規(guī)整化的可使用PE，適合于運(yùn)行時動態(tài)地映射應(yīng)用。

3.2 映射算法

應(yīng)用程序的區(qū)域選擇完成后，我們繼續(xù)將傳入應(yīng)用程序的節(jié)點(diǎn)分配到所選區(qū)域具有特定電壓水平的PE上，同時最小化處理器間通信。

為了跟蹤節(jié)點(diǎn)分配過程，Chou算法將每個節(jié)點(diǎn)涂成白色、灰色或黑色?；疑?jié)點(diǎn)表示它對應(yīng)一些暫定的PE位置，其精確位置將在以后確定。相反，一個黑色節(jié)點(diǎn)表示它已經(jīng)映射到某個PE上，并且這個映射將不再改變。所有的節(jié)點(diǎn)一開始都是白色的，然后可能變成灰色，然后變成黑色，或者直接變成黑色。將黑節(jié)點(diǎn)映射到某一PE之后，該P(yáng)E被設(shè)置為已占用。

Chou算法的節(jié)點(diǎn)分配核心思想是：首先使用其總通信量的非遞增順序?qū)⒐?jié)點(diǎn)分類為有序集，即節(jié)點(diǎn)具有的通信量越大，發(fā)現(xiàn)或完成得越早，按照該有序集對應(yīng)用的節(jié)點(diǎn)一一分配，每分配一個，計算可用區(qū)域內(nèi)該節(jié)點(diǎn)對應(yīng)每一個位置的通信距離，選擇最小的位置。相對于順序映射或者隨機(jī)映射而言，效果明顯，可以有效縮短通信距離，降低通信能耗，從而可以實(shí)現(xiàn)節(jié)省能耗的目的。

但是，經(jīng)過分析我們認(rèn)為算法在以下方面欠缺考慮：(1)在節(jié)點(diǎn)映射時，只考慮了總通信量以及其鄰居節(jié)點(diǎn)是否映射。很可能節(jié)點(diǎn)的鄰居有很多，但是它們之間的通信量是不同的，這一點(diǎn)Chou有所忽略。對于某個節(jié)點(diǎn)而言，在映射該節(jié)點(diǎn)時，與其通信量最大的鄰居節(jié)點(diǎn)未完成映射，根據(jù)算法啟發(fā)，反而會映射到通信量較少的鄰居旁邊，可能會導(dǎo)致通信量最大的鄰居節(jié)點(diǎn)通信距離反而相對變大。(2)該算法只有按照通信量從大到小的方向逐一進(jìn)行映射，然而對于一些區(qū)域和程序而言，通信量較小的節(jié)點(diǎn)更容易精確映射。(3)算法中為每個節(jié)點(diǎn)定義了2個狀態(tài)DISCOVER和FINISH，在最壞條件下每個節(jié)點(diǎn)需要遍歷2遍，首先DISCOVER，選出可用的PE，并將節(jié)點(diǎn)標(biāo)灰暫定在這些可用PE位置上，再等鄰居節(jié)點(diǎn)映射DISCOVER，進(jìn)入FINISH，確定精確映射PE位置，并將節(jié)點(diǎn)標(biāo)成黑色。

為此我們提出如下映射算法：

根據(jù)ACG圖計算每個節(jié)點(diǎn)t的相鄰邊數(shù)作為衡量該節(jié)點(diǎn)通信量的指標(biāo)，記做comm(t)。通過對每個節(jié)點(diǎn)的comm(t)排序得到不同電壓組合的節(jié)點(diǎn)序列，共k組，分別記做Vi,i=1,…,k。

(1)計算選中區(qū)域中每個PE的D(PE)。

(2)從V1開始，每次選擇該組中comm(t)最小和最大的節(jié)點(diǎn)，分別記做S和B。

(3)雖然每次選2個節(jié)點(diǎn)，但是2個節(jié)點(diǎn)不是同時進(jìn)行映射，此時對這2個節(jié)點(diǎn)需要考慮如下情形：

①如果B節(jié)點(diǎn)權(quán)重較大的鄰居已經(jīng)映射，則對其優(yōu)先映射；如果該鄰居沒有映射，優(yōu)先S節(jié)點(diǎn)。

②對于S節(jié)點(diǎn)只需要尋找D最小的PE進(jìn)行映射。

③對于B節(jié)點(diǎn)，如果鄰居節(jié)點(diǎn)已經(jīng)映射，那么該節(jié)點(diǎn)映射到靠近鄰居節(jié)點(diǎn)且D(PE)最大的PE上；如果有多個鄰居節(jié)點(diǎn)映射完畢，且其D(PE)相等，此時應(yīng)該考慮該節(jié)點(diǎn)與鄰居節(jié)點(diǎn)的通信量comm，選擇接近c(diǎn)omm最大的鄰居PE進(jìn)行映射；如果鄰居節(jié)點(diǎn)都沒有被映射，那么該節(jié)點(diǎn)選擇D(PE)最大的PE。

④S節(jié)點(diǎn)或B節(jié)點(diǎn)映射完成都需要更新未選擇的D(PE)。

(4)V1遍歷結(jié)束，對Vi遍歷，直到k組序列均映射完成,算法結(jié)束。

該算法對通信量不同的節(jié)點(diǎn)的映射方法是不同的，對于通信量較小的節(jié)點(diǎn)只需要找具有最小的D的PE進(jìn)行映射，對于通信量較大的節(jié)點(diǎn)優(yōu)先映射到權(quán)重較大的鄰居旁邊。這樣可以把較小通信量節(jié)點(diǎn)定位到相對孤立的PE位置，使得通信量大的節(jié)點(diǎn)之間局部通信距離最優(yōu)。

Chou算法的節(jié)點(diǎn)分配核心思想是：首先使用其總通信量的非遞增順序?qū)⒐?jié)點(diǎn)分類為有序集，即節(jié)點(diǎn)具有的通信量越大，發(fā)現(xiàn)或完成得越早。在此基礎(chǔ)上，改進(jìn)算法把邏輯上通信量大的節(jié)點(diǎn)與其權(quán)重較大的鄰居在物理上映射到相鄰的PE上，并通過定位通信量較小的節(jié)點(diǎn)到孤立的PE上從而增加權(quán)重較大的鄰居出現(xiàn)的概率。

下面用一個簡單的例子逐步描述該算法，需要注意的是在映射過程中使用的改進(jìn)算法分散因子D，并且對D的計算限定在選定的區(qū)域內(nèi)。

片上互連網(wǎng)絡(luò)如圖10所示，其中括號中的數(shù)字代表PE編號，灰色網(wǎng)格表示高電位的PE，網(wǎng)格中的黑色圓圈表示應(yīng)用選擇的區(qū)域，映射過程為(0)→(1)→(2)→(3)→(4)。

Figure 10 Mapping process圖10 映射過程示意圖

根據(jù)ACG圖對節(jié)點(diǎn)的通信量由大到小進(jìn)行排序,獲得節(jié)點(diǎn)有序集為：{v5,v1,v6,v8,v9,v4,v2,v3}，根據(jù)電壓水平可以將有序集分成2組，VH={v6,v4}，VL={v5,v1,v7,v8,v9,v2,v3}。

(1)首先從VH開始映射，選擇通信量最小節(jié)點(diǎn)S=v4，最大節(jié)點(diǎn)B=v6，由于v6權(quán)重較大的鄰居節(jié)點(diǎn)未映射，故先對v6進(jìn)行映射，片上的2個高電位D(PE6)=4,D(PE7)=5，因此v4映射到PE6上，接著對v6進(jìn)行映射，高電位只有PE7，故v6映射到PE7，結(jié)果如圖10b所示。

(2)VH映射結(jié)束，對VL進(jìn)行映射，選擇通信量最小節(jié)點(diǎn)S=v3，最大節(jié)點(diǎn)B=v5，對于v5，權(quán)重最大鄰居v6映射完成，故優(yōu)先，在片上與PE7相鄰的有PE2和PE8，D(PE2)=3，D(PE8)=4，因此v5映射到PE8上，v3直接找D最小的PE，故映射到PE5，結(jié)果如圖10c所示。

(3)繼續(xù)對VL進(jìn)行映射，選擇通信量最小節(jié)點(diǎn)S=v2，最大節(jié)點(diǎn)B=v1，由于v1權(quán)重最大的鄰居節(jié)點(diǎn)未映射，故先對v2進(jìn)行映射，直接選取D最小的PE1進(jìn)行映射，接著對v1進(jìn)行映射，其權(quán)重最大的鄰居節(jié)點(diǎn)v2剛好映射完，故v2映射到片上與PE1相鄰的有PE2上，結(jié)果如圖10d所示。

(4)以同樣的方法映射v7、v9后，分別對應(yīng)片上的PE3和PE4，剩下節(jié)點(diǎn)v8自動映射到剩下的PE9上，結(jié)果如圖10e所示。VL映射結(jié)束后所有電壓水平的序列均已映射完成，過程結(jié)束。

3.3 算法復(fù)雜性分析

本文對區(qū)域選擇算法的改進(jìn)只針對于分散因子和離心因子，并沒有改變算法的步驟，這就意味著改進(jìn)區(qū)域選擇算法的時間復(fù)雜度為O(|V| log |V| )[10]，其中|V|為應(yīng)用ACG圖的節(jié)點(diǎn)數(shù)。對于選定區(qū)域的映射算法而言，|V|個節(jié)點(diǎn)都需要遍歷一次，在每次遍歷節(jié)點(diǎn)時需要檢查該節(jié)點(diǎn)的鄰居節(jié)點(diǎn)的映射情況，最多遍歷E條邊，時間復(fù)雜度為O(|V|E )。因此，整個映射算法的時間復(fù)雜度為O(|V| log |V|+ |V|E )。

4 基于NIRGAM的NoC功耗優(yōu)化方法對比實(shí)驗(yàn)

本節(jié)將利用TGFF[13]工具隨機(jī)產(chǎn)生的應(yīng)用映射到8×8共64個tile的片上互連網(wǎng)絡(luò)結(jié)構(gòu)上。其中tile 0代表GM。本節(jié)比較的映射算法包括隨機(jī)映射(FT2000+在不綁定核的情況下根據(jù)任務(wù)數(shù)隨機(jī)映射到核上)、順序映射(按照tile編號的順序進(jìn)行任務(wù)映射)、INC以及本文新的映射算法(our)。通過NIRGAM來模擬片上處理器核通信的能耗。

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

本文基于NIRGAM模擬器研究應(yīng)用在片上映射的功耗。

NIRGAM是由英國南安普頓大學(xué)電子與計算機(jī)科學(xué)院電子系統(tǒng)設(shè)計團(tuán)隊和印度一家研究所共同聯(lián)合開發(fā)的，是專門面向片上互連網(wǎng)絡(luò)研究而開發(fā)的一種離散事件和周期精確的模擬器[11]。該模擬器采用SystemC編寫。NIRGAM模擬器可以模擬現(xiàn)有常見片上互連網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和路由規(guī)則，并且可進(jìn)行擴(kuò)展。此外，該模擬器可以進(jìn)行周期精確的功耗模擬，適合進(jìn)行片上互連網(wǎng)絡(luò)功耗研究。

NIRGAM允許對片上互連網(wǎng)絡(luò)設(shè)計的每個階段的各種屬性進(jìn)行實(shí)驗(yàn)，如拓?fù)?、交換機(jī)制、虛通道、緩沖區(qū)、時鐘頻率、路由算法和應(yīng)用等。該模擬器支持蟲洞式交換機(jī)制。NIRGAM模擬器自身存在代碼級別的缺陷，為了避免對功耗測量產(chǎn)生影響，根據(jù)已有解決方法對NIRGAM模擬器進(jìn)行修復(fù)。王榮陽等[12]在實(shí)際測試中發(fā)現(xiàn)NIRGAM在緩沖區(qū)與虛擬通道的關(guān)系、微片數(shù)目與pkt和flit大小關(guān)系、負(fù)載與包注入率之間關(guān)系這三方面存在問題。本文根據(jù)其提出的修改建議對NIRGAM進(jìn)行修復(fù)。表2是NIRGAM的配置表。

Table 2 NIRGAM configuration

本節(jié)利用TGFF工具生成2組隨機(jī)應(yīng)用程序序列：A組與B組。以應(yīng)用程序?qū)Φ男问竭M(jìn)行映射，一個應(yīng)用程序?qū)Χx為(a,b)，其中a來自A組，b來自B組。每次映射時，a先于b映射。用于模擬先后到達(dá)的應(yīng)用程序，以此來驗(yàn)證映射算法對系統(tǒng)整體的優(yōu)化效果。在實(shí)驗(yàn)中A、B2組各包括60個應(yīng)用程序，每個應(yīng)用任務(wù)數(shù)從 4～32，任務(wù)之間的通信量權(quán)重從 2～15。規(guī)定單個應(yīng)用任務(wù)數(shù)不超過32，是為了保證a、b都可以分配到資源，避免后到的應(yīng)用b由于計算資源缺少而造成等待。

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

本節(jié)用加權(quán)曼哈頓距離WMD(Weighted Manhattan Distance，應(yīng)用程序任務(wù)在片上的曼哈頓距離與相應(yīng)通信的權(quán)重的乘積之和) 作為一個應(yīng)用程序映射好壞的度量，WMD越小代表應(yīng)用程序任務(wù)之間通信距離越小，映射結(jié)果越好。如圖11所示是A、B2組應(yīng)用程序采取4種映射方法的WMD對比圖。相對于其他算法而言，our不但可以有效降低當(dāng)前應(yīng)用程序的通信距離(如A組WMD)，并且可以減小對后續(xù)應(yīng)用程序的映射距離(如B組WMD)。就2組應(yīng)用程序的平均通信距離而言，相比于隨機(jī)映射、順序映射、INC，our映射結(jié)果的通信距離分別減少了56.05%,29.81% 以及 17.45%。

Figure 11 WMDcomparison among different mapping algorithms圖11 映射算法加權(quán)曼哈頓距離比較

通過在NIRGAM對A、B2組應(yīng)用程序的映射結(jié)果進(jìn)行模擬，得到4種算法映射下的功耗對比。其中圖12是每組應(yīng)用程序在4種算法映射下的功耗對比，該圖按照our的功耗大小對橫坐標(biāo)進(jìn)行排序?？梢钥闯?5%的應(yīng)用通過our映射后功耗相比于之前得到了優(yōu)化。圖13是2組應(yīng)用程序在4種算法下應(yīng)用程序平均的通信延遲和功耗對比，our相對于隨機(jī)映射、順序映射、INC算法分別降低了45.38%,20.30%,11.23%的應(yīng)用程序通信功耗。在降低功耗的同時，our算法也可以減少通信的延遲。our與隨機(jī)映射、順序映射、INC相比帶來了36.60%,20.46%,12.10%的通信優(yōu)化。

Figure 12 Power comparison among different mapping algorithms for job set圖12 每組應(yīng)用程序在4種算法映射下的功耗對比

Figure 13 Latency and power comparison among different mapping algorithms for jobs inA,B圖13 A、B2組應(yīng)用程序在4種算法下的延遲&功耗對比圖

通過對A組應(yīng)用程序的映射結(jié)果可以看出，本文改進(jìn)的算法對減少單個應(yīng)用程序通信功耗提升通信性能是有益的。同時,通過B組應(yīng)用程序的映射結(jié)果可以看出，算法對后續(xù)應(yīng)用程序的通信開銷有優(yōu)化作用。

5 結(jié)束語

縮短應(yīng)用在片上互連網(wǎng)絡(luò)的通信距離對減少其通信功耗是有益的。本文分析Chou等提出的任務(wù)映射算法(INC)中的啟發(fā)因子，包括分散因子和離心因子，對其區(qū)域選擇算法進(jìn)行改進(jìn)，并驗(yàn)證了其有效性；提出了新的節(jié)點(diǎn)映射算法，本文提出的映射算法在通信量越大的節(jié)點(diǎn)映射越早的基礎(chǔ)上，進(jìn)一步把邏輯上通信量大的節(jié)點(diǎn)與其權(quán)重較大的鄰居在物理上映射到相鄰的tile上，并通過定位通信量較小的節(jié)點(diǎn)到孤立的tile上從而增加權(quán)重較大的鄰居出現(xiàn)的概率，減少了通信開銷，降低了功耗。它為進(jìn)一步尋找更優(yōu)的映射以及對算法進(jìn)行改進(jìn)提供了新的思路。實(shí)驗(yàn)表明，相比于INC，新算法減少了12.10%的通信功耗，且?guī)砹?1.23%的通信延遲優(yōu)化。如何發(fā)現(xiàn)和改進(jìn)片上互連網(wǎng)絡(luò)映射算法一直以來是一個重要的研究課題，該問題是一個NP完全問題，業(yè)界關(guān)于映射算法的研究正在繼續(xù)。下一步計劃將本文的算法擴(kuò)展到實(shí)際的平臺上，例如FT-2000，并參考天河的互連網(wǎng)絡(luò)相關(guān)技術(shù)和方法[14,15]提出更有效的映射策略。