片上互連網絡的功耗特征分析與優化*

孫曉樂,錢亞龍,齊新新,張云放,陳 娟,袁 遠,董 勇

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

1 引言

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

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

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

盡管眾多映射方法的出發點有所差別，但是保證了應用在片上的通信距離盡可能小，以此來保證較低的通信開銷。為此本文針對一種典型的凸區域增量映射方法INC(INCremental mapping)[10]，分析改進其區域選擇的相關參數并提出了新的映射算法。通過實驗表明，新的算法相較于INC減少了12.10%的通信功耗并且帶來了11.23%的通信延遲優化。

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

2 NoC典型案例及任務映射問題描述

2.1 NoC典型案例

目前，處理器已經進入多核時代。一般核數小于或等于8個的處理器被稱為多核處理器，具有更多核數的處理器被稱為眾核處理器。目前關于片上互連網絡的理論研究部分已經投入工業生產中。

2.1.1 飛騰(PHYTIUM)FT-2000

FT-2000處理器芯片集成64個自主開發的基于ARMv8處理器核心，兼容處理器內核FTC662，采用片上并行系統(PSoC)體系結構。通過集成高效處理器核心、基于數據親和的大規模性存儲架構、層次式二維Mesh互連網絡，優化存儲訪問延時，提供業界領先的計算性能、訪存帶寬和IO擴展能力。

2.1.2 Intel Knight Landing

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

2.2 任務映射問題描述

映射到片上互連網絡的所有應用程序都由程序任務圖描述。如圖1所示是一個程序的應用通信圖ACG(Application Communication Graph)。一個ACG圖包括通信節點及其電壓水平、通信邊及權重，ACG圖中的一個通信節點代表實際應用程序的一個進程或一個子任務。該ACG圖映射到如圖2所示的4×4共16個tile的片上互連網絡結構上。圖2中，有黑色圓圈的矩形代表該tile已經被映射了應用程序，不可再被其他應用程序映射。故tile 0已經有了對應的應用程序，不能重復被映射。灰色矩形區域代表這個tile是高電平，其余區域對應低電平。應用程序中的節點v4和v6必須映射到高電平tile上，而tile 5～tile 7是高電平，其余都是低電平。節點之間按照任務圖進行通信。

Figure 1 ACG of a program[10]圖1 一個程序的應用通信圖[10]

Figure 2 Structure of NoC圖2 片上互連網絡結構圖

一個新的應用(如圖1所示)到達系統，并映射到片上互連網絡(如圖2所示)，使得功耗最優化的過程可以抽象為：

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

目標：找到一個區域R以及一個映射map()，使得對于任意節點vi∈V,map(vi)→PEi,使得:

最小化。

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

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

解決的問題：對于一個已經映射過應用的系統，共有M個PE可用，假設新來一個包含N個節點的應用(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)最小化使得需要映射的應用節點間的通信代價最小化，L(R1)+L(R-R1)最小化是從整個系統出發，使得新應用映射結束后，剩余PE離散化的程度小，使得整體通信代價小。因此，本文采用這2個指標來比較改進映射算法和未改進算法的優劣。

3 改進區域選擇算法并提出新的映射算法

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

通常，如果區域包含連接其中任何一對點的所有線段，則該區域是凸的。近凸區域選擇算法通過計算待選擇PE的分散因子與離散因子的和，來逐步確定對應片上互連網絡的映射區域。實際上，發現選擇的區域近似凸形。

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

3.1 區域選擇算法

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

3.1.1 分散因子的改進

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

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

分散因子D實際上是衡量一個PE可使用的鄰居數量的指標，當前可使用鄰居數量越少，其被選入到區域中的可能性越大。

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

Figure 4 Neighbor nodes and Manhattan overlay nodes圖4 鄰居節點及曼哈頓覆蓋節點示意圖

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

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

Figure 5 Mapping comparasion圖5 映射對比圖

3.1.2 離心因子的改進

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

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

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

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

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

Figure 6 Mapping example(choosing one PE to current region by differentDandC)圖6 映射示例(考慮下一步選入區域的PE)

表1 改進算法待選節點的啟發因子及新區域的L(R1)和L(R1)+L(R-R1)比較

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

3.1.3 改進算法效果

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

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

Figure 7 Four different system mappings圖7 4種不同的系統映射情況

考慮到實際應用通信節點規模的不同，對于上述4種PE使用情況的系統，對于新到應用考慮其節點數目分別從N=3開始到N達到最大可用PE數目，對于corner和centerN取3～42各40種情況，對于random1和random2N各取3～39各37種情況，所以實驗共考慮154種情況，分別采用Chou和改進后的區域選擇算法，比較L(R1)和L(R1)+L(R-R1) 2項指標。

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

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

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

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

實驗說明改進的算法與Chou算法相比，在保證當前應用映射區域通信能耗較小的基礎上，更加注重在系統級減少通信能耗，為后續程序提供規整化的可使用PE，適合于運行時動態地映射應用。

3.2 映射算法

應用程序的區域選擇完成后，我們繼續將傳入應用程序的節點分配到所選區域具有特定電壓水平的PE上，同時最小化處理器間通信。

為了跟蹤節點分配過程，Chou算法將每個節點涂成白色、灰色或黑色。灰色節點表示它對應一些暫定的PE位置，其精確位置將在以后確定。相反，一個黑色節點表示它已經映射到某個PE上，并且這個映射將不再改變。所有的節點一開始都是白色的，然后可能變成灰色，然后變成黑色，或者直接變成黑色。將黑節點映射到某一PE之后，該PE被設置為已占用。

Chou算法的節點分配核心思想是：首先使用其總通信量的非遞增順序將節點分類為有序集，即節點具有的通信量越大，發現或完成得越早，按照該有序集對應用的節點一一分配，每分配一個，計算可用區域內該節點對應每一個位置的通信距離，選擇最小的位置。相對于順序映射或者隨機映射而言，效果明顯，可以有效縮短通信距離，降低通信能耗，從而可以實現節省能耗的目的。

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

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

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

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

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

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

①如果B節點權重較大的鄰居已經映射，則對其優先映射；如果該鄰居沒有映射，優先S節點。

②對于S節點只需要尋找D最小的PE進行映射。

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

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

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

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

Chou算法的節點分配核心思想是：首先使用其總通信量的非遞增順序將節點分類為有序集，即節點具有的通信量越大，發現或完成得越早。在此基礎上，改進算法把邏輯上通信量大的節點與其權重較大的鄰居在物理上映射到相鄰的PE上，并通過定位通信量較小的節點到孤立的PE上從而增加權重較大的鄰居出現的概率。

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

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

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

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

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

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

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

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

3.3 算法復雜性分析

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

4 基于NIRGAM的NoC功耗優化方法對比實驗

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

4.1 實驗環境

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

NIRGAM是由英國南安普頓大學電子與計算機科學院電子系統設計團隊和印度一家研究所共同聯合開發的，是專門面向片上互連網絡研究而開發的一種離散事件和周期精確的模擬器[11]。該模擬器采用SystemC編寫。NIRGAM模擬器可以模擬現有常見片上互連網絡拓撲結構和路由規則，并且可進行擴展。此外，該模擬器可以進行周期精確的功耗模擬，適合進行片上互連網絡功耗研究。

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

Table 2 NIRGAM configuration

本節利用TGFF工具生成2組隨機應用程序序列：A組與B組。以應用程序對的形式進行映射，一個應用程序對定義為(a,b)，其中a來自A組，b來自B組。每次映射時，a先于b映射。用于模擬先后到達的應用程序，以此來驗證映射算法對系統整體的優化效果。在實驗中A、B2組各包括60個應用程序，每個應用任務數從 4～32，任務之間的通信量權重從 2～15。規定單個應用任務數不超過32，是為了保證a、b都可以分配到資源，避免后到的應用b由于計算資源缺少而造成等待。

4.2 實驗結果

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

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

通過在NIRGAM對A、B2組應用程序的映射結果進行模擬，得到4種算法映射下的功耗對比。其中圖12是每組應用程序在4種算法映射下的功耗對比，該圖按照our的功耗大小對橫坐標進行排序。可以看出95%的應用通過our映射后功耗相比于之前得到了優化。圖13是2組應用程序在4種算法下應用程序平均的通信延遲和功耗對比，our相對于隨機映射、順序映射、INC算法分別降低了45.38%,20.30%,11.23%的應用程序通信功耗。在降低功耗的同時，our算法也可以減少通信的延遲。our與隨機映射、順序映射、INC相比帶來了36.60%,20.46%,12.10%的通信優化。

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

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

通過對A組應用程序的映射結果可以看出，本文改進的算法對減少單個應用程序通信功耗提升通信性能是有益的。同時,通過B組應用程序的映射結果可以看出，算法對后續應用程序的通信開銷有優化作用。

5 結束語

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