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

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

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

中圖分類(lèi)號(hào)：TP391.41 文獻(xiàn)標(biāo)識(shí)碼：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）是一種源自于并行計(jì)算機(jī)網(wǎng)絡(luò)的片上互連技術(shù)，這種網(wǎng)絡(luò)化的互連方式不但能夠有效地克服傳統(tǒng)互連結(jié)構(gòu)延遲和帶寬等方面的不足，而且更加符合具有顯著分布式計(jì)算特征的復(fù)雜SoC的需求.因此，NoC被視為未來(lái)SoC中的解決互連問(wèn)題的關(guān)鍵技術(shù)之一.

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

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

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

第二，路由器的吞吐率低.不能及時(shí)地對(duì)報(bào)文進(jìn)行處理交換，限制了注入率.

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

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

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

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

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

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

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

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

1 擁塞率定義

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

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

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

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

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

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

2 擁塞預(yù)防

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

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

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

3 擁塞解除

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

注入率增加：

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

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

4 實(shí)驗(yàn)和性能分析

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

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

INJECTION_RATE（timestamp-10 000）

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

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

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

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

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

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

5 結(jié)束語(yǔ)

NoC在高注入率下會(huì)出現(xiàn)嚴(yán)重的擁塞現(xiàn)象，并且隨著注入率增加而加重.在適當(dāng)?shù)膱?bào)文注入策略下，可以實(shí)現(xiàn)將網(wǎng)絡(luò)中的通信流量控制在一個(gè)合理水平內(nèi)，從根本上減輕網(wǎng)絡(luò)的負(fù)載壓力，有效避免NoC完全陷入擁塞而出現(xiàn)癱瘓的局面，使NoC通

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

參考文獻(xiàn)

[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.