基于動態(tài)注入率的片上網(wǎng)絡(luò)擁塞避免方法

摘要：片上網(wǎng)絡(luò)的擁塞現(xiàn)象極大地限制了路由器的有效性能，擁塞問題將直接影響到整個處理器芯片的性能.本文首先分析了片上網(wǎng)絡(luò)中虛通道路由器通信流量的特性.提出設(shè)定不同的閾值將網(wǎng)絡(luò)擁塞狀態(tài)進行劃分，將擁塞避免問題劃分為擁塞預(yù)防和擁塞解除兩個階段.提出使用一種動態(tài)注入率策略，根據(jù)實時檢測網(wǎng)絡(luò)的擁塞狀態(tài)，動態(tài)調(diào)整網(wǎng)絡(luò)報文的注入率，將網(wǎng)絡(luò)中的通信流量控制在一個合理水平內(nèi)，減輕網(wǎng)絡(luò)的負(fù)載壓力，避免NoC完全陷入擁塞而出現(xiàn)癱瘓狀態(tài).仿真模擬結(jié)果表明，擁塞預(yù)防時NoC性能約在“最大負(fù)載點”，擁塞解除時性能約在“膝點”，注入率可以達到0.05，在避免擁塞的同時有效兼顧了網(wǎng)絡(luò)性能.

關(guān)鍵詞：片上網(wǎng)絡(luò)；擁塞避免；動態(tài)注入率

中圖分類號：TP391.41 文獻標(biāo)識碼：A

Dynamic Injecting Strategy for Congestion Avoidance for NoC

LI Jin-wen， ZHANG Xi-min

（College of Computer， National Univ of Defense Technology， Changsha， Hunan 410073， China）

Abstract： Network-on-chip congestion greatly limits the effective performance of the router， and directly affects the performance of the processor chip. This paper divided the network's congestion state by using different threshold， and set the congestion avoidance apart into two distinct phases： congestion prevention and congestion relieving. Then a dynamic injection strategy was proposed. According to the congestion state in real-time， packet injection rate was adjusted dynamically， and communication traffic was controlled in reasonable level to decrease load press， avoiding congestion effectively. The simulation result shows that the performance of congestion prevention is almost at \"Cliff\" point， while congestion relieving is almost at \"Knee\" point， the injection rate can reach 0.05， and network performance is tradeoff with congestion avoidance.

Key words： network-on-chip； congestion avoidance； dynamic injection rate

片上網(wǎng)絡(luò)（Networks-on-Chip，NoC）是一種源自于并行計算機網(wǎng)絡(luò)的片上互連技術(shù)，這種網(wǎng)絡(luò)化的互連方式不但能夠有效地克服傳統(tǒng)互連結(jié)構(gòu)延遲和帶寬等方面的不足，而且更加符合具有顯著分布式計算特征的復(fù)雜SoC的需求.因此，NoC被視為未來SoC中的解決互連問題的關(guān)鍵技術(shù)之一.

由于單芯片在功耗和面積開銷方面的制約，片上網(wǎng)絡(luò)可以利用的資源受到很大限制，而另一方面，新一代片上多核系統(tǒng)（MPSoC）的內(nèi)核頻率不斷提高，對網(wǎng)絡(luò)互連通信的高性能和低延遲需求十分迫切，因而，各種高性能的路由器體系結(jié)構(gòu)和無死鎖的路由算法相繼被提出.然而，在無死鎖路由的前提條件下，片上網(wǎng)絡(luò)的擁塞現(xiàn)象極大地限制了路由器的有效性能.為了滿足片上網(wǎng)絡(luò)內(nèi)部的高速通信，緩解擁塞，提高通信的可靠性，降低報文的發(fā)送和接收延遲，合理有效的擁塞緩解和避免機制尤為重要.

提高路由器的性能主要是提高其報文吞吐率和降低路由器報文延遲.提高吞吐率的必然途徑是提高網(wǎng)絡(luò)注入率，在無死鎖的路由策略下，提高注入率可以適當(dāng)提高網(wǎng)絡(luò)吞吐率，但可能會帶來網(wǎng)絡(luò)的擁塞問題，有三方面的原因：

第一，路由器通道資源不足.理論上，要無限地提高網(wǎng)絡(luò)注入率，只需要無限提高路由器的通道資源，保證注入的報文都能及時地進入通道內(nèi)進行交換.但在實際應(yīng)用中是不可行的.

第二，路由器的吞吐率低.不能及時地對報文進行處理交換，限制了注入率.

第三，不合理的路由器策略.主要是報文注入策略，可能出現(xiàn)局部注入報文過剩，導(dǎo)致局部擁塞，從而使整個網(wǎng)絡(luò)產(chǎn)生擁塞，影響網(wǎng)絡(luò)的吞吐率.

目前，對擁塞的處理主要有如下幾種方法：

1）流控技術(shù)[1-2].最初采用流控技術(shù)是為了防止死鎖問題，事實上對擁塞的緩解也很有幫助.

2）面向局部（Regional Congestion Awareness RCA）^[3]和鄰近（Proximity Congestion Awareness PCA）節(jié)點的擁塞控制策略^[4].RCA將局部范圍的擁塞情況記錄下來并廣播出去通知整個網(wǎng)絡(luò)，降低或避免路由使用出現(xiàn)擁塞的路徑；PCA路由時，通過比較相鄰節(jié)點的擁塞度來選擇路由路徑.兩種策略均采用負(fù)載均衡技術(shù)來緩解擁塞.

3）多級擁塞控制路由算法（Multiple Level Congestion Control， MLCC）[5].該算法優(yōu)先選擇擁塞度低的路徑進行報文路由.

圖1為網(wǎng)絡(luò)性能與負(fù)載之間的經(jīng)典關(guān)系曲線.[1-2]

從圖1中可以看到，在“膝點”（Knee point）到最大負(fù)載點區(qū)間，隨著注入率增加，都是負(fù)載影響占主導(dǎo)地位，即此時增大注入率對網(wǎng)絡(luò)整體造成的是積極的影響.在最大負(fù)載點，兩者的影響相當(dāng)，一旦超過此點，延遲影響將占主導(dǎo)地位.用兩者的斜率來表征兩者影響的變化快慢可以看到，延遲影響增大的速度比負(fù)載增大的趨勢要大得多，且負(fù)載增大趨勢在“崖點”位置已經(jīng)降為零，而延遲迅速變大.

本文選擇最大負(fù)載點處為擁塞解除點，崖點處為擁塞預(yù)防點，在此基礎(chǔ)上提出一種動態(tài)注入率策略來避免片上網(wǎng)絡(luò)擁塞，仿真結(jié)果表明了該方法的有效性.

1 擁塞率定義

虛通道是一種將物理通道進行多路復(fù)用的技術(shù)[1-2]，每條單向的虛通道由一對獨立管理的消息緩沖器實現(xiàn)，并不需要添加額外的通道資源，只是需要在軟件層的設(shè)計中，能夠區(qū)分當(dāng)前正在使用物理通道對應(yīng)的虛通道.虛通道技術(shù)在解決死鎖問題的同時，同樣可以用來降低消息延遲，提高網(wǎng)絡(luò)吞吐量，多路復(fù)用技術(shù)允許消息持續(xù)發(fā)送而不至于阻塞.因此虛通道路由器得到了廣泛應(yīng)用，本文的算法、理論分析和實驗也都基于虛通道路由器.

本文將網(wǎng)絡(luò)的擁塞率定義為一個比值，即當(dāng)前網(wǎng)絡(luò)的擁塞節(jié)點數(shù)占網(wǎng)絡(luò)總節(jié)點數(shù)的百分比，用σCR來表示.公式（1）是擁塞率的表達式，其中N為網(wǎng)絡(luò)的總路由器節(jié)點數(shù)，由網(wǎng)絡(luò)規(guī)模確定；NC為出現(xiàn)擁塞節(jié)點數(shù)目.

擁塞節(jié)點判定方式如下：無擁塞狀態(tài)下至多3個端口為忙狀態(tài)；擁塞狀態(tài)下至少4個端口為忙狀態(tài).路由器端口處的忙閑狀態(tài)定義根據(jù)該端口的虛通道占用情況進行區(qū)分.

對路由器節(jié)點設(shè)置狀態(tài)標(biāo)志位（Node State），當(dāng)路由器處于擁塞時，該路由器節(jié)點的狀態(tài)標(biāo)志信號為高電平，否則為低電平.這樣在任意時刻都能便捷地檢測網(wǎng)絡(luò)當(dāng)前的擁塞狀態(tài)，有助于實時地對注入率進行調(diào)整.網(wǎng)絡(luò)擁塞程度可通過查路由器狀態(tài)表獲取.

采用擁塞率（Congestion Rate）來表征當(dāng)前網(wǎng)絡(luò)擁塞狀態(tài)，將網(wǎng)絡(luò)的擁塞水平分為閑、忙、擁塞和癱瘓4種狀態(tài)，分別對應(yīng)相應(yīng)的擁塞水平，即當(dāng)前注入率在某個范圍內(nèi)時對應(yīng)相應(yīng)的擁塞層次，具體劃分如圖2示.

基于前述網(wǎng)絡(luò)擁塞程度定義，本文實現(xiàn)了兩種不同的動態(tài)注入率策略，并分別定義為擁塞預(yù)防（注入率不超過0.045）和擁塞解除（注入率可以達到0.05，但檢測到網(wǎng)絡(luò)發(fā)生擁塞時會立即發(fā)生改變）.

2 擁塞預(yù)防

擁塞預(yù)防的基本思想是在監(jiān)測到網(wǎng)絡(luò)進入擁塞狀態(tài)時，通過調(diào)整注入率，實現(xiàn)擁塞的預(yù)防.在擁塞預(yù)防中的動態(tài)擁塞率使用“加性遞增”（Additive Increasing）模型[6]：

式中：T為檢測時刻；R為擁塞率檢測周期，如可取固定間隔1 000個周期，若設(shè)定50個周期為一個基本窗口（W）大小，則R=20W；α為注入率增大系數(shù)（下邊界）.圖3是注入率增加過程示意圖.

式（2）中，R的值取得越大，則在時間R內(nèi)報文的注入體現(xiàn)的隨機性越大，注入過程越接近平穩(wěn).事實上，隨著注入率的不斷增加，報文平均在每50個時鐘周期內(nèi)注入的報文數(shù)也隨著增加，如在注入率為0.05時，平均報文注入為每50個周期注入10個報文，而在0.005時只注入一個報文，因此，固定檢測周期R對注入率小的時候有利.當(dāng)注入率很大時，在檢測周期內(nèi)可能已經(jīng)注入了很多報文，造成檢測結(jié)果不準(zhǔn)確.有效的解決辦法是讓檢測周期可變，即擁塞率越大檢測時間越短，這將在擁塞解除情況下可用到.

3 擁塞解除

擁塞預(yù)防中，報文注入率增大的趨勢逐漸趨于穩(wěn)定，并沒有充分地利用網(wǎng)絡(luò)資源，發(fā)揮出更優(yōu)的性能.以下方式能夠?qū)崿F(xiàn)注入率達到0.05時網(wǎng)絡(luò)性能的最大化.同樣地，在擁塞解除中也認(rèn)為0.005為注入率變化的原子單位.擁塞解除時的注入率變化公式如下所示^[5].

注入率增加：

式中的所有參數(shù)跟式（2）中完全一樣.另外，RCD表示注入率在0.05下網(wǎng)絡(luò)的擁塞檢測時間，RCD越小，則網(wǎng)絡(luò)擁塞檢測的靈敏度越高.const是一個常數(shù)，加入const的目的是為了在檢測到網(wǎng)絡(luò)擁塞時注入率能夠調(diào)整到原來的初始大小.注入率變化過程如圖4所示.

圖4中粗虛線表示沒有加入const參量時注入率的瞬間跳變過程.如果不加入const參量，隨著仿真周期的增加，初始注入率會越來越接近time坐標(biāo)軸，即Iinj_rate無限趨于“0”.在動態(tài)的注入率過程中，注入率迅速地增大，以便在最短的時間內(nèi)達到合理的網(wǎng)絡(luò)狀態(tài)，盡可能充分地利用網(wǎng)絡(luò)資源和鏈路帶寬.注入率越大，要求注入率的增幅越小，從而不會向網(wǎng)絡(luò)中注入過多的報文導(dǎo)致?lián)砣踔涟c瘓.公式中的const參量的另外一個作用就是讓注入率在跳變的時候回到的初始注入率盡量地高，從而能讓注入率更快地接近跳變點.

4 實驗和性能分析

在仿真實驗中，采用Verilog中的函數(shù)實現(xiàn)網(wǎng)絡(luò)動態(tài)注入率調(diào)整.擁塞預(yù)防中，動態(tài)注入率函數(shù)實現(xiàn)算法如下：

在上述算法中，T為時間參量，1 000為固定擁塞率檢測周期，T%1000即表示擁塞率檢測序數(shù).alpha即為公式中的α，取值為0.02.“**”在Verilog中表示乘方運算，該運算符左邊為乘方運算的基數(shù)，右邊為冪指數(shù)，上述函數(shù)能夠完整實現(xiàn)擁塞預(yù)防中的動態(tài)注入率調(diào)整過程.函數(shù)的調(diào)用形式如下：

INJECTION_RATE（timestamp-10 000）

timestamp是設(shè)置的網(wǎng)絡(luò)時鐘計數(shù)器，10 000是網(wǎng)絡(luò)的預(yù)熱周期，預(yù)熱過程會產(chǎn)生少量的報文，約200個，但是產(chǎn)生報文不在報文計數(shù)器內(nèi)，因此預(yù)熱過程對后面的報文注入過程不會產(chǎn)生影響.

在擁塞解除中，擁塞率的檢測周期是可變的，注入率小的情況下檢測周期長，注入率大的情況下檢測周期短.同時還要實現(xiàn)注入率的周期規(guī)律性變化，函數(shù)現(xiàn)實算法如下.

算法中TD為擁塞率檢測間隔，呈周期性變化，在取擁塞感知時間TCD為250 cycles時，周期TC為2 500 cycles.

分析發(fā)現(xiàn)擁塞預(yù)防的動態(tài)注入率下的網(wǎng)絡(luò)特點與注入率為0.045的靜態(tài)注入模式下非常相似，同時擁塞解除時的網(wǎng)絡(luò)特點與注入率為0.025的靜態(tài)注入模式下也很類似，如圖5所示.

可以直觀地看到，在較短的時間范圍內(nèi)（如2 500個cycles），基于動態(tài)注入率的擁塞解除比擁塞預(yù)防的報文注入過程更穩(wěn)定，在任意擁塞率檢測間隔內(nèi)注入的報文不會超過100個，這比擁塞預(yù)防中的最高180個報文數(shù)量少了近一半，因此導(dǎo)致了最終產(chǎn)生的報文數(shù)量約為擁塞預(yù)防的動態(tài)注入率下的1/2.

實驗是在4×4的2D-Mesh，srandom traffic通信流量模式下采集得到的.事實上可以證明該方法與網(wǎng)絡(luò)規(guī)模以及網(wǎng)絡(luò)拓?fù)錈o關(guān)，動態(tài)注入率解決擁塞問題的方法適用于任意網(wǎng)絡(luò)規(guī)模和拓?fù)浣Y(jié)構(gòu).在仿真過程的100 000個周期內(nèi)，兩種動態(tài)注入率下的網(wǎng)絡(luò)平均流量都比較穩(wěn)定，但擁塞解除的注入率過程中可能出現(xiàn)“爆發(fā)式”的注入，使網(wǎng)絡(luò)暫時地進入擁塞狀態(tài)，這種爆發(fā)式注入持續(xù)時間很短，注入率的瞬間跳變（變小）完全可以使網(wǎng)絡(luò)從擁塞狀態(tài)中恢復(fù)過來，因此，擁塞解除過程從長的時間尺度上來說也可認(rèn)為是擁塞避免的.

5 結(jié)束語

NoC在高注入率下會出現(xiàn)嚴(yán)重的擁塞現(xiàn)象，并且隨著注入率增加而加重.在適當(dāng)?shù)膱笪淖⑷氩呗韵拢梢詫崿F(xiàn)將網(wǎng)絡(luò)中的通信流量控制在一個合理水平內(nèi)，從根本上減輕網(wǎng)絡(luò)的負(fù)載壓力，有效避免NoC完全陷入擁塞而出現(xiàn)癱瘓的局面，使NoC通

信的安全可靠性得到保障.實驗證明，動態(tài)注入率策略下，可以有效避免NoC擁塞，同時，在擁塞預(yù)防下的網(wǎng)絡(luò)性能約處于“崖點”位置，注入率可以達到0.045；擁塞解除下的網(wǎng)絡(luò)性能約處于“膝點”位置，注入率可以達到0.05.

參考文獻

[1] MARCULESCU R， OGRAS U Y， PEH L S， et al. Outstanding research problems in NoC design： system， microarchitecture， and circuit perspectives[J]. IEEE Transaction on Computer-Aided Design of Integrated Circuit and Systems， 2009， 28（1）： 3-21.

[2] DALLY W J， TOWLES B P. Principles and practices of interconnection networks[M]. San Francisco， California： Morgan Kanfman Publishers， 2004.

[3] LOTFI-KAMRAN P， DANESHTALAB M， LUCAS C， et al. BARP-A dynamic routing protocol for balanced distribution of traffic in NoCs[C]//Proceedings of EDAA’08. New York： ACM， 2008：3-4

[4] KIM J. Low-cost router microarchi-tecture for on-chip networks[C]//Proceedings of 42nd Annual IEEE/ACM International Symposium on Microarchitecture. New York： IEEE， 2009：255-266.

[5] KUMAR A， PEH L S， KUNDU P， et al. Express virtual channels： towards the ideal interconnection fabric[C]// Proceedings of the 34th Annual International Symposium on Computer Architecture. New York： ACM， 2007：150-161.

[6] NYCHIS G， FALLIN C， MOSCIBRODA T， et al. Congestion control for scalability in bufferless on-chip networks（SAFARI Technical Report No.2011-003）[R]. Pittsburgh， Pennsylvania， United States： Carnegie Mellon University， 2011.

[7] KOZIEROK C M. The TCP/IP guide： a comprehensive， illustrated internet protocols reference[M]. San Francisco， California： No Starch Press， 2005.