基于擁塞預測的ＮｏＣ自適應仲裁方法

(南京大學 a.微電子設計研究所; b.江蘇省光電信息功能材料重點實驗室， 南京 210093)



摘 要：

傳統用于總線系統或互聯網的仲裁方法已不能很好地適應NoC應用環境。圍繞NoC系統性能的關鍵影響因素——擁塞狀態，提出了一種基于全局和本地擁塞預測的仲裁策略(GLCA)，以改善NoC網絡延遲。實驗結果表明，相對于RR方法，新仲裁算法使得網絡平均包延遲和平均吞吐量最大分別可改善20.5%和8%，并且在不同負載條件下都保持了其優勢。綜合結果顯示， GLCA與RR方法相比，路由器僅在組合邏輯上有少許增加(25.7%)。

關鍵詞：片上網絡； 仲裁方法； 擁塞； 延遲； 擁塞區域

中圖分類號：TP393.03 文獻標志碼：A

文章編號：1001-3695(2009)02-0652-03



NoC adaptive arbitrating policy based on congestion prediction



YANG Sheng-guanga，b， LI Lia，b， XU Yia，b， ZHANG Yu-anga，b， LOU Xiao-xianga，b， GAO Ming-luna，b

(a. Institute of VLSI Design， b. Key Laboratory of Advanced Photonic Electronic Materials， Nanjing 210093， China)



Abstract:Many conventional arbitration policies used in bus-based systems or macro network were not suitable for NoC because of its new features. It was found that congestion was a common phenomenon in NoC communication and posed great impact on the network delay of NoC. This paper proposed a new arbitration policy-GLCA based on global and local congestion prediction to improve the network latency. Experiment results demonstrat that the new policy fits well with NoC. Compared with round robin arbitration policy， average latency per packet and average throughput can be improved by 20.5% and 8% at best， respectively. GLCA always keeps its advantage under different load conditions. In synthesis， the cost of router with GLCA is only larger than that with RR by 25.7% in combinational logic.

Key words：NoC(network on a chip); arbitration policy; congestion; latency; congestion area



0 引言

近年來，一種規則化的通信結構，稱為片上網絡(network on a chip， NoC)，開始被應用到系統芯片(system on a chip， SoC)的設計中[1~3]。仲裁機制是影響NoC系統性能的重要因素之一。文獻[4]比較了若干種仲裁策略及其對NoC網絡延遲和吞吐量的影響，數據分析表明不同仲裁機制對于系統網絡延遲的影響差異可達35%，對吞吐量的影響可達10%，對并行程序的執行時間影響可達12%。可見，NoC中采用何種仲裁策略是一個值得研究的問題。

固定優先級仲裁機制大量應用于現代總線系統中[5，6]。該方法中每個主設備訪問共享資源的優先級是固定的，傳輸任務較重的主設備優先級相對較高。但NoC中通道為各主設備共享，難以確定各通道的優先級。輪轉優先級仲裁(round robin，RR)[7，8]輪換主設備的優先級順序，使優先級隨著主設備占有總線的結束而動態變化。該方法在平衡負載情況下能取得很好的性能。然而在NoC中各節點的通信量通常相差懸殊，該方法往往不能取得最佳的效果。Lottery仲裁屬于隨機優先級仲裁機制[9，10]，它通過隨機算法來決定主設備的優先級，具有更好的公平性。類似于RR方法，它不能很好地處理非均衡通信負載。先來先服務仲裁方法能避免“饑餓”現象，但是當網絡某些區域出現擁塞時，它不能靈活決策以提高效率。

常用于總線系統和傳統網絡的仲裁方法大多在效率與公平性之間進行某種程度的折中，而沒有考慮到NoC網絡的通信特征，因此很難充分發掘NoC網絡的潛力。由于NoC網絡的性能在很大程度上受到擁塞狀態影響以及NoC網絡中分布著大量的仲裁器，NoC仲裁方法需要做到兩點：a)考慮網絡的擁塞狀態，最大化網絡通信效率；b)具有低復雜度，減少實現成本。鑒于該思想，本文提出了基于全局和本地擁塞預測的NoC仲裁方法(global and local congestion aware arbitration， GLCA)，以滿足NoC仲裁高效率和低成本的要求。

1 NoC平臺概述

1. 1 NoC平臺系統結構

NoC平臺是一個參數化的、二維網格結構的SystemC模型。NoC由路由器(R)、鏈路和本地子系統(LS)組成(4×4規模，如圖1所示)。路由器是網絡的核心部件，構成網絡的開關節點(switch)；本地子系統包含一個網絡接口(NI)和IP(intellectual property)核，構成網絡的資源節點。其中IP核表示處理單元、存儲單元或SoC。

1. 2 路由器結構

上述路由器設計為五個雙向端口：北(north)、東(east)、南(south)、西(west)和本地(local)。每個端口具有輸入和輸出通道。輸入通道包含緩存和路由邏輯，輸出通道包含仲裁邏輯。本地端口負責路由器與本地子系統的通信，其他端口負責路由器與近鄰路由器的通信。路由器結構如圖2所示。

2 NoC仲裁方法——GLCA

2. 1 GLCA仲裁方法的動因和簡介

NoC中的通信情況與總線通信有很大的區別，常用于總線和網絡的仲裁方法都不足以發掘片上網絡通信的潛力。NoC系統中大量的通信任務并行執行，當發生多個輸入通道申請同一個輸出通道時就需要進行仲裁，仲裁獲勝的一方繼續傳輸，其他輸入通道就需要等待。如果某些區域通信總需要等待，并且等待時間比其他區域長，那么說明存在擁塞區域。擁塞會嚴重影響NoC系統的性能。

本地擁塞狀態最早被引入到自適應路由算法[11]中以改善NoC傳輸性能。但是，自適應路由算法存在數據包的無序到達問題，需要在目標節點處對包重新排序，這大大增加了網絡接口和流控制設計的復雜度。因此，自適應路由算法的應用受到了很大程度的限制。

為了進一步挖掘NoC的通信潛力而不明顯增加NoC設計的復雜性，筆者采用靜態路由算法，將全局和本地擁塞的思想引入到仲裁策略中。于是，一種全新的仲裁方法(GLCA)被提了出來。在GLCA中，依次考慮如下三個因素。

2. 1. 1 全局擁塞預測

全局擁塞預測就是根據應用特征來預測網絡中最有可能出現擁塞的區域。NoC布局確定以后，其總體通信分布也基本確定。根據應用特征，對NoC的通信量分布進行預測，確定可能出現嚴重擁塞的區域；仲裁時優先讓通往其他區域的數據先行。該方法可緩解擁塞區域的擁擠情況，并且不會使去往非擁塞區域的數據受阻，從而降低了平均等待延遲。全局擁塞預測在網絡重負載(接近飽和或飽和)時作用顯著。 

在仲裁機制中引入全局擁塞預測，首先要確定擁塞區域；然后對數據包目的地進行判斷，完成相應仲裁。

2. 1. 2 局部擁塞預測

局部擁塞預測就是根據輸出通道掌握的本地輸入通道信息預測上游路由器的擁塞狀況。仲裁時輸出通道根據輸入通道緩存狀態來決定其優先次序。如果緩存中數據量大，說明該緩存導致上游路由器阻塞的可能性更大，因此讓緩存緊張的輸入通道先行。該方法使得緩存數據分布趨向于均勻化，避免部分緩存閑置或排隊過長，降低平均等待延遲。局部擁塞預測在網絡低負載(未飽和)時作用顯著。

在仲裁機制中引入局部擁塞預測，首先要采集本地各輸入通道緩存狀態(緩存數據量)；然后比較競爭通道的緩存狀態，完成相應仲裁。

2. 1. 3 公平性仲裁

公平性原則是NoC仲裁策略不能忽視的一個方面。輪轉優先級仲裁(RR)能保證良好的公平性，并使實現成本比較低。因此，RR受到了廣泛的應用，并且被證實具有較好的總體性能。RR仲裁通常作為平等主體之間的仲裁規則。

GLCA仲裁由三個階段組成：它首先考慮全局擁塞預測；然后考慮本地擁塞預測；最后考慮RR規則。如果兩個包去向不同類型的區域，則讓去向非擁塞區域的包先行；如果兩個包來自不同負載的輸入通道，則讓來自重負載通道的包先行，否則，采用RR仲裁規則。GLCA仲裁算法兼具全局擁塞預測、局部擁塞預測和公平仲裁的優勢，因此可以預期其在不同的網絡負載條件下都會有良好的表現。

2. 2 GLCA仲裁方法偽碼

GLCA仲裁方法主要通過函數granting ()實現。其偽碼描述如下：

int granting()

{

int i=0，j=0，k=0;

int req[N_PORT];/*將隊列in_req[]中當前有效的請求按照RR規則的順序重組進新隊列req[]*/

for (i= previous+ 1;i < N_PORT; i++)

{if (in_req[i]==1) {req[j]=i;j++;}}

for (i = 0; i<=previous; i++)

{if (in_req[i]==1) {req[j]=i;j++;}}

//如果當前沒有有效請求，則通知仲裁器等待

if (j==0) return (-1);

//FBCA仲裁算法實現

for (i=1;i

{

//全局擁塞預測

if ((hot[req[i]]

k=i;

//本地擁塞預測

else if ((hot[req[i]]==hot[req[k]]) (stress

[req[k]]

k=i;

//默認情況下實施RR規則

else

k=k;

}

//記錄當前被授權請求的序號

previous= req[k];/*如果當前被授權請求的序號為N_PORT-1，則開始新一輪仲裁*/

if (previous == N_PORT - 1)

previous= -1;

//給出當前被授權請求的序號

return(req[k]);

}

2. 3 GLCA仲裁器結構

GLCA仲裁器由六個部分組成：CA、VREQ、GCP、LCP、RR和OUTPUT。其結構如圖3所示。圖中，data[i]表示來自第i個輸入通道的數據；CA根據數據data[i]的目的地設置hot[i]，“1”表示擁塞區域，“0”表示非擁塞區域；VREQ將當前有效請求in_req[]重組到req[]中；GCP執行全局擁塞預測；LCP執行本地擁塞預測；RR執行輪轉優先級仲裁策略；OUTPUT給出授權結果gnt[i]。每次仲裁只有一個決策環節(GCP、LCP 或RR)能產生一個有效決定(k)。

3 實驗與分析

3. 1 性能指標

平均包延遲(latency)和平均吞吐量(throughput)是評價NoC網絡性能的兩個重要指標。其定義如下：

latency=(total latency of received packets)/(number of received packtes)

throughput=(received packets)/(number of nodes×simulation cycles)

3. 2 實驗條件

本實驗基于4×4二維網格結構NoC仿真平臺，本地系統充當數據包的發送器和接收器。系統設置：蟲孔交換，靜態XY路由，緩存深度為8，包長度為3個數據片(flit)，數據片寬度為35位。每次模擬運行20 000個時鐘周期。以上說明為實驗的默認環境，如無特殊說明均采用該環境。

NoC中非平衡通信流量分布通過遵循泊松(Poisson)分布的交通發生器來實現。擁塞是通信負載過重導致的，因此通信負載將是主要的擁塞標志。本地擁塞預測中與文獻[11]一樣，采用緩存數據量作為擁塞標志。全局擁塞預測中是根據網絡總體的通信分布情況來預測可能的擁塞區域。擁塞區域由兩種類型的節點組成：a)承擔較重負載的節點；b)臨近重負載的節點，這主要是因為通信借道的緣故。本實驗中定義兩個擁塞區域(CA1和CA2)以作比較。CA1為負載最重的三個節點；

CA2為CA1外加離最重負載節點曼哈頓距離小于兩步的節點。

當然，擁塞區域的范圍是可以放大或縮小的，其關鍵在于關于擁塞區域的假設要合理。

考慮到RR仲裁算法廣泛應用于實踐中，其體現出的綜合性能非常不錯，而且GLCA仲裁算法是在RR基礎上的改進，因此實驗中將其作為GLCA的比較參考。

3. 3 實驗結果

平均包延遲和平均吞吐量曲線分別如圖4和5所示。

模擬結果顯示，與RR相比，GLCA仲裁方法在平均包延遲和平均吞吐量上最大分別能改善20.5%和8%。在不同負載條件下，GLCA都優于RR。實驗結果印證了之前的分析結果。 

實驗結果同時也顯示出擁塞區域定義對仲裁算法性能有一定的影響。擁塞區域的合理范圍取決于NoC的通信分布和片上緩存容量。低網絡負載和高緩存容量通常需要收縮擁塞區域，相反情況則需要放大擁塞區域。本實驗中，CA2 定義顯然比CA1合理。要獲得更優化的參數設置，則依賴于更多的實驗。

3. 4 綜合結果

3.3節中實驗結果顯示，GLCA仲裁方法性能優越，與RR方法相比優勢明顯，但是該方法實現成本如何還需要綜合結果進一步驗證。本文使用Verilog HDL語言對采用兩種仲裁機制的路由器SystemC模型(R-GLCA和R-RR)進行了改寫，然后在Quartus Ⅱ6.0環境下進行了綜合。FPGA型號為Stratix Ⅱ，器件型號為EP2S180F1020C3。綜合結果如表1所示。

表1 路由器模塊資源使用情況

routerLC-CLC-Rmemory/bit

R-RR1 0073451 400

R-GLCA1 2663501 400

表中LC-C、LC-R分別表示Stratix Ⅱ標準器件中的組合邏輯單元和寄存器單元，以個數計；memory為存儲器資源，以位(bit)計算使用量。綜合結果顯示，與R-RR相比，R-GLCA組合邏輯單元數有少許增加(25.7%)，而寄存器和memory用量幾乎未受影響，這與GLCA算法中增加了邏輯判斷的情況相吻合。可見，GLCA仲裁方法導致路由器成本增加很少。

4 結束語

由于網絡擁塞對NoC的性能造成了嚴重的影響，本文將擁塞思想引入到NoC仲裁策略中。于是，一種全新的自適應仲裁方法(GLCA)被提出來了。該方法協同考慮了全局擁塞預測、局部擁塞預測和公平性，因此它在不同網絡負載條件下都具有性能改善的能力。實驗結果顯示，與RR相比，GLCA仲裁方法在平均包延遲和平均吞吐量上最大分別能改善20.5%和8%，而且其優勢覆蓋了從輕到重的整個負載條件，該特性對NoC設計具有重要價值。綜合結果表明，GLCA仲裁方法僅導致路由器組合邏輯少許增加(25.7%)。可見，GLCA仲裁方法是一種新穎、高效率、低成本的NoC自適應仲裁方法。

參考文獻：

[1]BENINI L， MICHELI G D.Network on chips: a new SoC paradigm[J]. IEEE Computer， 2002，35(1):70-78.

[2]AHMAD B， ARSLAN T. Dynamically reconfigurable NoC for reconfigurable MPSoC[C]//Proc of IEEE Custom Integrated Circuits Conference. San Jose， CA: IEEE Press，2005:277-280.

[3]PANDE P P， ZHU Hai-bo， GANGULY A， et al. Energy reduction through crosstalk avoidance coding in NoC paradigm[C]//Proc of the 9th EUROMICRO Conference on Digital System Design. Cavtat， HR: IEEEPress， 2006:689-695.

[4]PIRVU M， BHUYAN L， NI Nan. The impact of link arbitration on switch performance[C]//Proc of the 5th International Symposium on High-Performance Computer Architecture. Orlando， FL: IEEE Press， 1999:228-235.

[5]KETTLER K A， LEHOCZKY J P， TTROSNIDER J K. Modeling bus scheduling policies for real-time systems[C]//Proc of the 16th IEEE Real-time Systems Symposium. Oakland: IEEE Press， 1995:242-253. 

[6]CHEN C H， LEE G W， HUANG J D， et al. A real-time and bandwidth guaranteed arbitration algorithm for SoC bus communication[C]//Proc of Asia and South Pacific Design Automation Conference. Pacifica Yokohama: IEEE Press， 2006:600-605.

[7]KOVALSKI A B. High-speed bus arbiter for multiprocessors[C]//Proc of IEEE. [S.l.]:IEEE Press， 1983:49-56.

[8]SECELEANU T， KNUUTILA T， NEVALAINEN O. Starvation free arbitration policies for the segmented-bus platform[C]//Proc of International Symposium on Signals， Circuits and Systems. Iasi， Romania: IEEE Press， 2005:67-70.

[9]LAHIRI K， RAGHUNATHAN A， LAKSHMINARAYANA G. LOTTERYBUS: a new high-performance communication architecture for system-on-chip designs[C]//Proc of DAC 2001. Las Vegas: IEEE Press， 2001:15-20.

[10]XU Yi， LI Li， GAO Ming-lun， et al. An adaptive dynamic arbiter for multi-processor SoC[C]//Proc of the 8th International Conference on Solid-State and Integrated Circuit Technology. Shanghai: IEEE Press， 2006:1993-1996.

[11]LI Ming， ZENG Qing-an， JONE W B.DyXY: a proximity congestion-aware deadlock-free dynamic routing method for network on chip[C]//Proc of DAC 2006. San Francisco， California: IEEE Press，2006:849-852.