吳鳳陽，劉勤讓

(國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心，河南 鄭州 450002)

一種新的片上網(wǎng)絡(luò)擁塞感知容錯(cuò)路由算法

吳鳳陽，劉勤讓

(國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心，河南 鄭州 450002)

提出一個(gè)有效的路由通道選擇機(jī)制，實(shí)現(xiàn)了基于片上網(wǎng)絡(luò)(networks on chips,NoC)的擁塞感知的自適應(yīng)容錯(cuò)路由算法(congestion-aware adaptive fault-tolerant routing algorithm, CAFR)。該算法基于Up*/Down*路由算法得出源節(jié)點(diǎn)到目的節(jié)點(diǎn)每條路徑的轉(zhuǎn)向概率，再根據(jù)每條鏈路的兩端路由器剩余內(nèi)存時(shí)隙得出一個(gè)加權(quán)鏈路，最后由每條路徑權(quán)重值和其路徑的轉(zhuǎn)向概率計(jì)算出源地址到目的地址各條路徑的總權(quán)重值。實(shí)驗(yàn)結(jié)果表明，在無故障條件下，該算法的平均延遲和平均吞吐率都能維持較好水平。在故障條件下，該算法相對(duì)其他算法在吞吐量衰減方面有很大改善，尤其在故障率達(dá)到20%時(shí)，該算法吞吐量只有44.32%的衰減，而其他有容錯(cuò)性能的算法衰減達(dá)到48%～70%。

片上網(wǎng)絡(luò)；擁塞感知；Up*/Down*路由算法；加權(quán)鏈路

0 引 言

隨著技術(shù)的發(fā)展，硅元件的特征尺寸已發(fā)展到亞納米階段，同時(shí)元件的可靠性也越來越低。另外，數(shù)字系統(tǒng)復(fù)雜度的增加很可能會(huì)造成在它們的使用過程中要經(jīng)歷永久性故障。為了克服這個(gè)問題，片上網(wǎng)絡(luò)在設(shè)計(jì)時(shí)不僅要滿足性能的需要，而且在面對(duì)許多故障發(fā)生時(shí)還得具有較強(qiáng)的魯棒性。

當(dāng)代復(fù)雜的片上系統(tǒng)引入新的互連策略，如允許可擴(kuò)展芯片上多種處理單元之間通信的片上網(wǎng)絡(luò)(network on chips,NoC)。當(dāng)前NoCs中，通信延遲和容錯(cuò)對(duì)于復(fù)雜性和高概率應(yīng)用映射結(jié)構(gòu)的片上多處理器是個(gè)挑戰(zhàn)[1]。在經(jīng)常發(fā)生故障的工藝制造中，先前工藝制造處理和物理缺陷的增加對(duì)于實(shí)際NoC可靠性是關(guān)鍵挑戰(zhàn)。NoC通信延遲主要由路由算法決定。自適應(yīng)路由算法需要解決有繁忙/擁塞爭(zhēng)論的流量監(jiān)測(cè)，同時(shí)還要解決可靠性問題和提供容錯(cuò)[2]。目前算法不僅需要考慮鏈路的流量，而且還有在NoC中產(chǎn)生的永久和暫時(shí)性故障。特殊永久故障的存在對(duì)于動(dòng)態(tài)系統(tǒng)是不可逆的；額外的敏感電流和輻射能造成短暫的故障，同時(shí)不穩(wěn)定的硬件能造成間歇的故障，如卡殼、橋接、竄擾、單事件更新和傳輸?shù)墓收?。根?jù)國際半導(dǎo)體技術(shù)發(fā)展路線圖(international technology roadmap semicoductors,ITRS)報(bào)道，在日常運(yùn)作期間，每天將有1%的芯片產(chǎn)生故障。在不久的將來，工藝制造的缺陷概率將達(dá)到每平方米大約有1 000個(gè)缺陷[3-4]。測(cè)試結(jié)果表明在NoC中，即使很小數(shù)量的故障，如邏輯門開關(guān)故障，都能造成5～50的鏈路故障，這極大損害NoC網(wǎng)絡(luò)系統(tǒng)[5]。當(dāng)一條鏈路發(fā)生故障，自適應(yīng)路由算法應(yīng)該選擇一條無故障路徑發(fā)送數(shù)據(jù)包，避免數(shù)據(jù)包傳輸?shù)陌c瘓。因此，確保NoCs模塊能夠容納故障和維持標(biāo)準(zhǔn)工藝的運(yùn)行需要，自動(dòng)化系統(tǒng)應(yīng)能夠根據(jù)真實(shí)的通信流量條件作出決定。解決這種情況首先要提出一個(gè)路徑選擇優(yōu)化方案讓系統(tǒng)能夠在當(dāng)前故障下運(yùn)行。

目前，國內(nèi)外學(xué)者對(duì)此展開大量的研究。文獻(xiàn)[6]在XY和Odd-Even 算法基礎(chǔ)上進(jìn)行改進(jìn)，提出了一種能在擁塞條件下進(jìn)行確定性和自適應(yīng)路由算法之間轉(zhuǎn)化的DyXY路由算法，該算法較單獨(dú)的XY和Odd-Even 算法在平均延遲上具有較好的特性，但在故障條件下吞吐量、平均延遲等性能急劇下降。文獻(xiàn)[7]提出了一種在每條鏈路增加2條專用線路來指示與當(dāng)前路由器有相同行或列路由節(jié)點(diǎn)的通信狀態(tài)以避免擁塞路徑的方案。但是這種增加專用線路的方案需要較大的資源開銷，如有網(wǎng)路發(fā)生故障時(shí)，網(wǎng)絡(luò)吞吐量衰減較大。文獻(xiàn)[8-9]提出了一種集中自適應(yīng)路由機(jī)制，它采用路由表和一個(gè)負(fù)反饋模塊檢測(cè)全局網(wǎng)絡(luò)通信狀態(tài)來選擇一條擁塞程度低的路徑轉(zhuǎn)發(fā)數(shù)據(jù)包。但是該類算法在故障條件下無法保持網(wǎng)絡(luò)性能。文獻(xiàn)[10]采用一個(gè)可重構(gòu)路由算法，當(dāng)檢測(cè)到故障或失效路由器時(shí)，該算法通過繞開故障路由器來達(dá)到容錯(cuò)的性能。但是該算法僅能容忍節(jié)點(diǎn)故障。陳慶強(qiáng)等人提出了一種鄰居節(jié)點(diǎn)感知和端口優(yōu)先級(jí)選擇方案[11-12]，該方案可以自適應(yīng)選擇無故障路徑轉(zhuǎn)發(fā)數(shù)據(jù)微片，但是該算法在端口優(yōu)先級(jí)劃分上略顯欠缺，控制擁塞也不明顯，而且在發(fā)生區(qū)域故障時(shí)平均延遲較高。

對(duì)于以上多數(shù)容錯(cuò)方案，在復(fù)雜的通信條件下做出擁塞控制和選擇優(yōu)先路徑方面普遍存在不足；而且在大量通信狀態(tài)和發(fā)生區(qū)域性故障條件下，不能很好地維持網(wǎng)絡(luò)的性能。因此提出了一種具有擁塞感知的容錯(cuò)路由算法(congestion-adaptive fault-tolerant routing algorithm，CAFR)。

容錯(cuò)NoC路由算法通過靈活地均衡它內(nèi)在的路由解決了這個(gè)難題。也就是說，CAFR路由算法通過限制通信在無故障路徑中傳輸來應(yīng)對(duì)故障發(fā)生。本文中，雖然一些不可知的拓?fù)浣Y(jié)構(gòu)路由算法提供了較高靈活性的路徑，甚至在目前存在許多故障情況下保持網(wǎng)絡(luò)的連通性。盡管如此，當(dāng)在芯片上不斷地配置不能實(shí)現(xiàn)的故障時(shí)，它們也經(jīng)常在很少的故障下導(dǎo)致系統(tǒng)的服務(wù)性能退化。例如，在文獻(xiàn)[13]中，在僅有10個(gè)故障下一個(gè)8×8 mesh網(wǎng)絡(luò)的吞吐量下降20%。這不合理的損失主要是由于在剩下健康路徑中通信擁塞的增加。因此，運(yùn)行時(shí)通信流量的控制對(duì)故障網(wǎng)絡(luò)的性能具有重要的影響。

本文中，采用CAFR算法的目的是在當(dāng)前故障下通過動(dòng)態(tài)路由最小化NoC吞吐量的退化。它采用一個(gè)在有效的區(qū)域中基于權(quán)重端口選擇機(jī)制定義可靠的、低擁塞的路由通道。CAFR算法對(duì)于多種通信流量條件(如 繁忙/擁塞/故障)定義不同的權(quán)重值，在算法中繁忙和故障條件下被分別定義成最大和最小權(quán)重值。每個(gè)NoC路由器端口被設(shè)定權(quán)重值，最大的權(quán)重端口作為優(yōu)先轉(zhuǎn)發(fā)數(shù)據(jù)包。通過計(jì)算端口的權(quán)重，在路由器端口之間做路由選擇時(shí)，能夠避免故障或擁塞的鏈路。因此，在NoC系統(tǒng)中CAFR算法能夠繞開故障，并有能力根據(jù)復(fù)雜的通信流量條件做出優(yōu)化路由抉擇。通過定義好的端口，在給定的流量模式和故障條件下使全局NoC吞吐量最大，獲得優(yōu)秀的系統(tǒng)性能。

1 CAFR路由算法描述

1.1 路徑邊權(quán)重計(jì)算

路徑計(jì)算的主要思路為：① 將設(shè)計(jì)一個(gè)關(guān)聯(lián)的有向圖G(V，E)；②根據(jù)當(dāng)前網(wǎng)路通信狀態(tài)按比例分配邊權(quán)重；③基于ball-string模型，設(shè)計(jì)一種自檢測(cè)機(jī)制，該機(jī)制可以在已知的源節(jié)點(diǎn)與目的節(jié)點(diǎn)坐標(biāo)的條件下得出權(quán)重值最大的路徑[6]?？梢园焰溌返臓顟B(tài)分別定義成：空閑(權(quán)重：6～9)、繁忙(權(quán)重：3～5)、擁塞(權(quán)重：1～2)和故障(權(quán)重：0)。

本節(jié)根據(jù)當(dāng)前系統(tǒng)緩存占用率的信息來計(jì)算邊權(quán)重，如圖1所示。具體來說，就是計(jì)算上一跳路由節(jié)點(diǎn)輸出緩存與下一跳路由節(jié)點(diǎn)輸入緩存中所剩余內(nèi)存時(shí)隙的總個(gè)數(shù)。圖1a闡述了一條鏈路的邊權(quán)重計(jì)算算法。圖1b給出了3×2 NoC關(guān)聯(lián)圖的邊權(quán)重。最優(yōu)路徑中的邊權(quán)重wij(i=1,2,3…,|V|;j=1,2,3…,|V|)計(jì)算為

(1)

算法在部署時(shí)利用了網(wǎng)絡(luò)圖的鄰接矩陣[A]n×n，因?yàn)槊總€(gè)元素存儲(chǔ)了相應(yīng)的邊權(quán)重(即aij=wij) ，所以將其稱為網(wǎng)絡(luò)矩陣。圖1c給出了[A]3×2網(wǎng)路矩陣。

為了減小額外的硬件開銷，本文采取一種分布式、自適應(yīng)路由策略。NoC拓?fù)渚W(wǎng)絡(luò)被劃分成多個(gè)區(qū)，在每個(gè)分區(qū)設(shè)置一個(gè)本地監(jiān)測(cè)模塊(local monitoring module，LMM)[13]。LMM模塊作為一種檢測(cè)器，負(fù)責(zé)檢測(cè)該區(qū)域節(jié)點(diǎn)連接鏈路的擁塞狀態(tài)。如圖2中劃分的區(qū)域大小相等，實(shí)際中對(duì)區(qū)域大小不做要求。

每個(gè)LMM模塊主要工作是將當(dāng)前鏈路的狀態(tài)信息分發(fā)到其領(lǐng)域所有路由器中以及其領(lǐng)域一階(first-order )相鄰的路由器。LMM模塊還要計(jì)算出連接不同領(lǐng)域的鏈路權(quán)重，它們之間通過互連來實(shí)現(xiàn)信息共享。

1.2 轉(zhuǎn)向概率

研究中數(shù)據(jù)資料均采用統(tǒng)計(jì)學(xué)軟件SPSS20.0構(gòu)建的數(shù)據(jù)庫檢驗(yàn)，其中患者不良反應(yīng)、依從及滿意率、檢查圖像質(zhì)量分析均百分率表示，卡方檢驗(yàn)。當(dāng)數(shù)據(jù)差異P＜0.05，視為統(tǒng)計(jì)學(xué)價(jià)值存在。

CAFR算法基于Up*/Down*路由算法建立一個(gè)鏈路生成樹。鏈接到根節(jié)點(diǎn)被標(biāo)記為Up鏈路，而鏈接向葉節(jié)點(diǎn)被標(biāo)記為Down鏈路。Up*/Down*路由算法不允許Down-Up轉(zhuǎn)向：一旦數(shù)據(jù)包到達(dá)一個(gè)Down鏈路，它就不能被允許轉(zhuǎn)到一個(gè)Up鏈路。

圖1 邊權(quán)重計(jì)算示例Fig.1 Link weights

圖2 NoC被分割為4個(gè)分區(qū)的示意圖Fig.2 NoC segmentation image

對(duì)于路徑的每個(gè)部分，我們分3個(gè)步驟估算數(shù)據(jù)包從源節(jié)點(diǎn)到目的節(jié)點(diǎn)所有可能鏈路。

Step 1 估算不同路徑。計(jì)算出從源節(jié)點(diǎn)到達(dá)下一跳所有不同路由節(jié)點(diǎn)鏈路總數(shù)。例如，在圖3a中節(jié)點(diǎn)13可從2個(gè)不同路由器到達(dá)節(jié)點(diǎn)10的東邊鏈路：13→9→10和13→14→10，然而只有一個(gè)路由器能夠通向節(jié)點(diǎn)10的北邊鏈路：13→14→10。在這個(gè)處理中，只允許在有限的轉(zhuǎn)向約束下以最短跳步的路由路徑轉(zhuǎn)發(fā)數(shù)據(jù)。

Step 2 鏈路負(fù)載估計(jì)。根據(jù)Step 1的結(jié)果估算出基于多種可利用路徑中每條鏈路上來自上一跳的通路負(fù)載基數(shù)。節(jié)點(diǎn)輸入端口概率等于輸入端口鏈路的通路基數(shù)除去用相同跳數(shù)到達(dá)該節(jié)點(diǎn)的所有路由器總通路數(shù)。圖3b展示了連接節(jié)點(diǎn)10的每條輸入端口鏈路的概率。

Step 3 轉(zhuǎn)向負(fù)載估計(jì)。為了估計(jì)每個(gè)轉(zhuǎn)向負(fù)載概率，我們拿來自源方向輸入端口負(fù)載概率除去源方向允許輸出的端口總數(shù)。圖3c展示了連接節(jié)點(diǎn)10路由器的輸出端口概率。

圖3 鏈路負(fù)載和轉(zhuǎn)向概率示例Fig.3 Link load and turn probability

最優(yōu)路徑選擇

(2)

(2)式中：yii是一個(gè)二進(jìn)制變量，表示鏈路ch(vi，vj) 是否可以被采用；pi是轉(zhuǎn)向概率，表示路由器j選擇下一鏈路的幾率。計(jì)算最短路徑的方法是基于并行最短路徑搜索[14]原理，該方法是通過檢測(cè)當(dāng)前網(wǎng)絡(luò)通信狀態(tài)來計(jì)算出多條路徑權(quán)重，最終比較得出一條最優(yōu)路徑。如圖4展示了源節(jié)點(diǎn)13到目的節(jié)點(diǎn)4的各條鏈路權(quán)重和轉(zhuǎn)向概率。

1.3 死鎖避免

網(wǎng)絡(luò)通信中死鎖的產(chǎn)生是由于網(wǎng)絡(luò)中存在多個(gè)數(shù)據(jù)包同時(shí)轉(zhuǎn)發(fā)任務(wù)，每個(gè)轉(zhuǎn)發(fā)任務(wù)包都占據(jù)了一些鏈路或緩存資源，又同時(shí)請(qǐng)求被其他任務(wù)包所占據(jù)的通信資源，而形成依賴環(huán)。如果此時(shí)外界對(duì)網(wǎng)絡(luò)沒有給予一定處理，數(shù)據(jù)包將處于無限時(shí)間的等待中，不能得到有效地傳送。

圖4 最優(yōu)路徑Fig.4 Optimal path

如果節(jié)點(diǎn)端口的緩沖區(qū)或路由器內(nèi)部通道資源被占用，都將會(huì)造成數(shù)據(jù)包不能立即轉(zhuǎn)發(fā)而處于循環(huán)等待，最后形成死鎖。第1種情況(第1類)發(fā)生在路由器端口用于存儲(chǔ)轉(zhuǎn)發(fā)的Buf中，稱之為緩沖區(qū)死鎖(buffer deadlock)。當(dāng)4個(gè)相鄰的環(huán)形節(jié)點(diǎn)之間相互連接的鏈路端口上的緩沖區(qū)分別被不同的數(shù)據(jù)包占用，就會(huì)形成第1類死鎖，除非丟棄某個(gè)數(shù)據(jù)包或者其中1個(gè)任務(wù)包轉(zhuǎn)發(fā)路徑出錯(cuò)，否則死鎖一直存在。第2種情況(第2類)發(fā)生在采用蟲孔交換技術(shù)的Mesh型的網(wǎng)絡(luò)通道中，稱之為通道死鎖(channel deadlock)。因?yàn)橄x孔交換技術(shù)會(huì)把數(shù)據(jù)包切分成不同的微片以流水線的形式在網(wǎng)絡(luò)中向前“蠕動(dòng)”，所以大多時(shí)間一個(gè)數(shù)據(jù)包的頭微片(head flit)、數(shù)據(jù)微片(body flit)和尾微片(tail flit)分別存在于不同路由器通道中。如圖5所示，有4個(gè)數(shù)據(jù)包的微片同時(shí)分別占用了對(duì)方的轉(zhuǎn)發(fā)通道，形成一個(gè)依賴環(huán)就會(huì)產(chǎn)生第2類死鎖。當(dāng)前避免死鎖的技術(shù)主要有虛通道技術(shù)和轉(zhuǎn)向模型2種。

圖5 通道死鎖Fig.5 Channel deadlock

死鎖預(yù)防算法主要針對(duì)不同方向的數(shù)據(jù)包而提供不同的路由性能。此算法優(yōu)點(diǎn)是邏輯簡(jiǎn)單、易于實(shí)現(xiàn)，而缺點(diǎn)是卻存在極大地不公平現(xiàn)象。為了解決此類問題，Chiu提出的Odd-Even轉(zhuǎn)向模型，分別禁止奇數(shù)列通信節(jié)點(diǎn)上的EN(ES)轉(zhuǎn)向和偶數(shù)列上的NW(SW)轉(zhuǎn)向，從而解開依賴環(huán)。Odd-Even轉(zhuǎn)向模型解決了在死鎖預(yù)防算法中禁止同類節(jié)點(diǎn)的相同轉(zhuǎn)向而帶來不公平。

Up*/Down*路由算法是一種典型的禁止拐彎的模型,它首先是為DEcAutonet網(wǎng)絡(luò)提出的，是一種適用于規(guī)則或不規(guī)則拓?fù)渚W(wǎng)絡(luò)的無死鎖路由算法，可用源或分布式方式實(shí)現(xiàn),當(dāng)采用分布式方式實(shí)現(xiàn)時(shí),提供了部分自適應(yīng)性，它給每條鏈路指派Up或Down方向,把網(wǎng)絡(luò)配置成無圈的有向圖,然后通過禁止消息經(jīng)過Down方向到Up方向的拐彎(turn),來保證算法無第1類死鎖。

在Odd-Even 轉(zhuǎn)向模型的基礎(chǔ)上進(jìn)行改進(jìn)，當(dāng)LMM模塊檢測(cè)到4個(gè)環(huán)形結(jié)點(diǎn)的4個(gè)緩沖區(qū)剩余的內(nèi)存時(shí)隙總數(shù)量小于等于閥值權(quán)重8時(shí)進(jìn)行轉(zhuǎn)向控制：無故障NoC模塊采用Odd-Even的禁止轉(zhuǎn)向；當(dāng)在故障NoC模塊禁止min:wij×pj最小那一轉(zhuǎn)向。本文基于Odd-Even轉(zhuǎn)向模型進(jìn)行的改進(jìn)，傳統(tǒng)的Odd-Even轉(zhuǎn)向模型是對(duì)奇數(shù)列和偶數(shù)列上路由節(jié)點(diǎn)設(shè)定了一些特定方向的禁止轉(zhuǎn)向，主要應(yīng)用于無故障網(wǎng)絡(luò)和單故障節(jié)點(diǎn)無死鎖路由中，對(duì)區(qū)域故障和多故障網(wǎng)絡(luò)會(huì)加大網(wǎng)絡(luò)擁塞概率，相應(yīng)的通信延遲也會(huì)增加。而本文利用LMM模塊對(duì)網(wǎng)絡(luò)通信狀況進(jìn)行檢測(cè)，無故障區(qū)域可以利用Odd-Even 轉(zhuǎn)向模型；在多故障區(qū)域發(fā)生死鎖，可以禁止通信量相對(duì)較小的轉(zhuǎn)向，從而減小擁塞程度，預(yù)防發(fā)生死鎖。圖6所示10-11-15-14環(huán)路鏈路的總權(quán)重值為8，將產(chǎn)生死鎖，利用禁止轉(zhuǎn)向方案在有故障節(jié)點(diǎn)下禁止最小的SW轉(zhuǎn)向使能。

圖6 死鎖避免Fig.6 Deadlock free

2 實(shí)驗(yàn)與分析

本節(jié)概述實(shí)驗(yàn)所使用的方法和呈現(xiàn)的性能結(jié)果都是在無故障條件下使用CAFR算法得出的。

2.1 衡量性能分析的系數(shù)和實(shí)驗(yàn)平臺(tái)

本文評(píng)估系數(shù)標(biāo)準(zhǔn)采用文獻(xiàn)[16]的方法。例如數(shù)據(jù)包的注入率(packet injection rate ，PIR)指的是數(shù)據(jù)包注入NoC網(wǎng)路的概率。在NoC中對(duì)于給予的任何單節(jié)點(diǎn)路由器，每個(gè)時(shí)鐘周期發(fā)送數(shù)據(jù)包的標(biāo)準(zhǔn)數(shù)量等于PIR(0

(3)

(3)式中：Rflits表示接收到微片的總數(shù)；Nnodes表示節(jié)點(diǎn)的總數(shù)；Nclk表示產(chǎn)生第一個(gè)微片到接收到最后一個(gè)微片總的時(shí)鐘周期。 因此，吞吐量是網(wǎng)絡(luò)在物理處理給定路徑的能力時(shí)衡量最大負(fù)載的一部分。延遲被定義為產(chǎn)生在頭微片從源節(jié)點(diǎn)注入網(wǎng)路和產(chǎn)生在目標(biāo)節(jié)點(diǎn)接收到最后尾微片兩者之間流失的時(shí)鐘周期數(shù)量。如(4)式定義的平均延遲D，它是總信息數(shù)量平均值；K是到達(dá)目標(biāo)節(jié)點(diǎn)信息的總數(shù)量；Di是產(chǎn)生延遲的節(jié)點(diǎn)。

(4)

表1列出了評(píng)估環(huán)境。引用Noxim仿真器對(duì)CAFR路由算法性能進(jìn)行評(píng)估。本文的CAFR路由算法使用的仿真平臺(tái)基于一個(gè)2D-mesh系統(tǒng)。為了保證得到精確的結(jié)果，仿真在每個(gè)PIR點(diǎn)重復(fù)運(yùn)行多次(此處運(yùn)行5次)。準(zhǔn)備階段和執(zhí)行階段循環(huán)次數(shù)分別是1 000和20 000時(shí)鐘周期。CAFR路由算法被評(píng)估是在各種流量模式下進(jìn)行的包括①uniform，②transpose，③shuffle。算法的性能評(píng)估和數(shù)據(jù)對(duì)比按以下2步驟進(jìn)行。第1步使用擴(kuò)展的Noxim軟件仿真評(píng)估CAFR擁塞感知能力。Noxim整合了DyAD，Odd-even，XY，Negative-first路由算法。標(biāo)準(zhǔn)的模擬器允許所研究的CAFR算法與整合的路由算法在相同的流量條件下進(jìn)行性能比較。這種評(píng)估算法很實(shí)用，然而所整合的路由算法都是沒有容錯(cuò)性能的。為了驗(yàn)證本算法的容錯(cuò)特性，第2步引進(jìn)一些優(yōu)秀的具有容錯(cuò)能力的路由算法進(jìn)行比較，用來突出本算法在大量通信狀態(tài)和發(fā)生區(qū)域性故障條件下，能更好地維持網(wǎng)絡(luò)的性能，尤其在維持吞吐量方面更為突出。這些用來對(duì)比的算法有FoN,Cost，F(xiàn)TDR，F(xiàn)TDR-H，LAFT，HLAFT。

表1 仿真模型具體參數(shù)

2.2 網(wǎng)絡(luò)性能

本節(jié)介紹關(guān)于CAFR算法與所列的基準(zhǔn)算法的性能在不同的流量模式下的仿真結(jié)果。圖7展示了在均勻分布(Uniform)的流量模式下CAFR算法與所有的基準(zhǔn)算法仿真結(jié)果后的平均延遲D和吞吐量T數(shù)據(jù)。從圖7a中可以看到CAFR算法和XY路由算法比較其他算法達(dá)到一個(gè)較低的延遲。圖7b中DyAD，Odd-even，XY，Negative-first在注入率PIR分別為0.01，0.014，0.015，0.012處平均吞吐率開始飽和，可CAFR算法卻一直保持較好的性能。

圖8展示了在Transpose流量模式下的仿真結(jié)果。圖8a中，在PIR=0.017以后，DyAD，XY和Negative-first算法平均延遲急劇增加。從圖8b中可以看出XY和Negative-first算法在注入率PIR=0.07時(shí)平均吞吐率分別達(dá)到飽和，并且Odd-Even在PIR=0.1處達(dá)到飽和。Odd-Even和CAFR算法都在這個(gè)流量模式下平均延遲有所變動(dòng)，但是較其他算法還是具有較高的性能。此外CAFR算法具有較少的擁塞鏈路和均衡了鏈路負(fù)載的性能。圖9是對(duì)于在Shuffle流量模式下的平均延遲和吞吐量仿真結(jié)果。如圖9a中，DyAD，Negative-first和XY算法的平均延遲分別在PIR=0.017和PIR=0.025之間開始增加，圖9b吞吐率也在注入率為PIR=0.105和PIR=0.12達(dá)到飽和。然而Odd-Even和CAFR算法維持較低延遲和較高的吞吐量。我們應(yīng)該注意到CAFR算法在各種流量模式下都具有較好的性能。

圖7 Uniform流量模式下的性能Fig.7 Performance under Uniform traffic pattern

2.3 容錯(cuò)性能

實(shí)驗(yàn)設(shè)置了不同程度的故障鏈路來評(píng)估CAFR算法的性能。當(dāng)系統(tǒng)有故障鏈路時(shí)，4個(gè)對(duì)比算法的吞吐量將會(huì)退減。吞吐量的衰減情況在表2中列出。從表2中可以看出系統(tǒng)在5%～20%故障鏈路下，所有的路由算法性能都有不同程度的退化。DyAD算法在5%-20%故障鏈路條件下有23.82%～61.90%的退化；Odd-Even算法有 21.78%～63.85%的退化；Negative-first和 XY算法分別有19.08～63.03%和20.75%～65.25%的退化。然而CAFR算法只有16.88%～44.32%的退化程度，較其他算法其退減較低。當(dāng)故障率增加，CAFR算法吞吐量有較小衰減，如故障率是15%時(shí)衰減是36.04%，故障率為20%時(shí)衰減是44.32%。本算法的吞吐量性能較其他4個(gè)算法都獲得了很大的提升。

圖8 Transpose流量模式下的性能Fig.8 Performance under transpose Traffic pattern

圖9 Shuffle流量模式下的性能Fig.9 Performance under Shuffle traffic pattern

本算法與其他具有較好容錯(cuò)性能的算法進(jìn)行了比較。如FoN，Cost，F(xiàn)TDR，TDR-H，LAFT 和 HLAFT作為評(píng)估CAFR算法容錯(cuò)性能的基準(zhǔn)比較算法。表3是分別來自于文獻(xiàn)[16]和[17]中容錯(cuò)算法的吞吐量衰減數(shù)據(jù)。從表3中可以發(fā)現(xiàn)，在故障率為10%和20%時(shí)，F(xiàn)oN，Cost，F(xiàn)TDR 和FTDR-H容錯(cuò)算法有48%～70%吞吐量衰減。然而在同樣的條件下本算法最高只達(dá)到45.12%吞吐量衰減。因此，該結(jié)果展現(xiàn)了CAFR算法優(yōu)于這些基準(zhǔn)容錯(cuò)算法。結(jié)果也證明了當(dāng)故障發(fā)生時(shí)CAFR算法容錯(cuò)性能具有較小的衰減。

表2 在不同流量模式下吞吐量衰減度

表3 CAFR算法與其他容錯(cuò)算法對(duì)比

‘N/A’表示數(shù)據(jù)在作者論文沒有呈現(xiàn)

3 結(jié) 論

本文所提的CAFR擁塞感知容錯(cuò)算法在復(fù)雜通信條件下對(duì)NoC吞吐性能有很大的改進(jìn)。該算法采用分布式策略將常規(guī)的片上網(wǎng)絡(luò)架構(gòu)分為多個(gè)由本地監(jiān)測(cè)單元控制的區(qū)域，每個(gè)本地監(jiān)控單元檢測(cè)出所有路徑最大權(quán)重值得出最優(yōu)路徑，以避免采用擁塞嚴(yán)重的路由器和故障鏈路，進(jìn)而降低延遲。最后，算法在應(yīng)用程序上能估算路由需求而且還能在可利用的資源下均衡通信路徑。通過鏈路權(quán)重和節(jié)點(diǎn)轉(zhuǎn)向概率方案定義一個(gè)最小延遲的輸出端口方向；采用嵌入改進(jìn)禁止轉(zhuǎn)向模型保證了算法的無死鎖性。實(shí)驗(yàn)結(jié)果表明，在無故障下，隨著注入率增加該算法在平均吞吐率、平均延遲等性能上和Odd-Even等優(yōu)秀算法保持在同一水平；在10%～20%故障條件下，其他具有容錯(cuò)能力的算法隨著故障概率的提高吞吐量衰減達(dá)到48%～70%，而該算法最高只達(dá)到45.12%吞吐量衰減。總之，提出的算法在維持網(wǎng)絡(luò)性能上就有很大的優(yōu)勢(shì)。未來研究工作的重點(diǎn)將探索對(duì)于可配置系統(tǒng)發(fā)生永久性故障后緩存資源如何再分配利用和如何提高路由算法的性能增益。

[1] AGARWAL A, SHANKAR R. Survey of Network on Chip (NoC) Architectures & Contributions[J]. Journal of Engineering Computing & Architecture, 2009, 3(1):1934-1938.

[2] LIU J, HARKIN J, LI Y, et al. Low cost fault-tolerant routing algorithm for Networks-on-Chip[J]. Microprocessors & Microsystems, 2015, 39(6):358-372.

[3] SHAFIK R A, MATHEW J, PRADHAN D K. Introduction to energy-efficient fault-tolerant systems[C]// Energy-Efficient Fault-Tolerant Systems. New York: IEEE,2014： 1-10.

[4] AISOPOS K, DEORIO A, PEH L S, et al. Agnostic Reconfiguration in a Disconnected Network Environment[C]// International Conference on Parallel Architectures & Compilation Techniques. New York:ACM, 2011:298-309.

[5] LI M, ZENG Q A, JONE W B. DyXY-A Proximity Congestion-Aware Deadlock-Free Dynamic Routing Method for Network on Chip[C]// DESIGN AUTOMATION CONFERENCE. New York: ACM/IEEE, 2006:849-852.

[6] LOTFI K P, RAHMANI A M, DANESHTALAB M, et al. EDXY-A low cost congestion-aware routing algorithm for network-on-chips[J]. Journal of Systems Architecture, 2010, 56(7):256-264.

[7] MANEVICH R, CIDON I, KOLODNY A, et al. Centralized Adaptive Routing for NoCs[J]. Computer Architecture Letters, 2010, 9(2):57-60.

[8] RAN M, CIDON I, KOLODNY A, et al. A Cost Effective Centralized Adaptive Routing for Networks-on-Chip[C]// Euromicro Conference on Digital System Design, IEEE Computer Society. New York:IEEE, 2011:39-46.

[9] WANG Y, ZHANG M, XIAO C W. A fault tolerant adaptive routing algorithm in 2D mesh network on chip[J]. Journal of Liaoning Medical University, 2011, 64(4):140-144.

[10] 陳慶強(qiáng), 羅興國, 陳韜,等. 一種鄰節(jié)點(diǎn)狀態(tài)感知的NoC可重構(gòu)容錯(cuò)路由[J]. 小型微型計(jì)算機(jī)系統(tǒng), 2013, 34(6):1365-1370. CHENG Qinqiang, LUO Xinguo, CHENG Tao.et al. A Reconfigurable Fault-tolerance Routing Algorithm of NoC Based on the Awareness of Status-on-neighbor [J]. Journal of Chinese Mini-Micro Computer Systems, 2013, 34(6): 1365-1370. [11] 張士鑒, 韓國棟, 沈劍良. 基于故障鏈路緩存再利用的NoC容錯(cuò)路由算法[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2014, 26(1):131-137. ZHANG Shijian, HAN Guodong, SHEN Jianliang. A fault-tolerant algorithm of NoC based on buffer reuse[J]. Journal of Computer-Aided Design & Computer Graphics, 2014,26(1):131-137.

[12] WANG Y, ZHANG M, XIAO C W. A fault tolerant adaptive routing algorithm in 2D mesh network on chip[J]. Journal of Liaoning Medical University, 2011, 64(4):140-144.

[13] 孫利, 田進(jìn)華. 片上網(wǎng)絡(luò)中基于擁塞感知的自適應(yīng)路由算法[J]. 計(jì)算機(jī)工程, 2015, 41(8):82-88. SUN Li, TIAN Jinhua. Adaptive Routing Algorithm Based on Congestion-aware in Network-on-Chip [J].Computer Engineering,2015, 41(8):82-88.

[14] LEE D, PARIKH R, BERTACCO V. Highly Fault-tolerant NoC Routing with Application-aware Congestion Management[C]//International Symposium on Networks-On-Chip. New York: ACM, 2015:1-8.

[15] AISOPOS K, DEORIO A, PEH L S, et al. Agnostic Reconfiguration in a Disconnected Network Environment.[C]// International Conference on Parallel Architectures & Compilation Techniques. New York: IEEE, 2011:298-309.

[16] FENG C, LU Z, JANTSCH A, et al. Addressing Transient and Permanent Faults in NoC With Efficient Fault-Tolerant Deflection Router[J]. IEEE Transactions on Very Large Scale Integration Systems, 2013, 21(6):1053-1066.

[17] AHMED A B, ABDALLAH A B. Graceful deadlock-free fault-tolerant routing algorithm for 3D Network-on-Chip architectures[J]. Journal of Parallel & Distributed Computing, 2014, 74(4):2229-2240.

(編輯：張 誠)

A new congestion-aware fault-tolerant routing algorithm for networks-on-chips

WU Fengyang, LIU Qinrang

(National Digital Switching System Engineering & Technology Research Center, Zhengzhou 450002, P.R. China)

We put forward an effective routing channel selection mechanism to realize the adaptive fault-tolerant routing algorithm with ability of congestion aware on NoC, called CAFR(congestion-aware adaptive fault-tolerant routing algorithm). CAFR algorithm gets the turning probability of each path from the source node to the destination node based on the Up*/Down*routing algorithm; secondly, it gets a weighted link according to the remaining memory time-slot of the endpoint router in each link; finally, the total weight value in each path from the source node to the destination node is calculated according to the weight value of each path and its path turning probability. Experimental results show that the algorithm can maintain a good level on the performance of average latency and average saturation throughput under the condition of trouble-free. Under fault conditions, the algorithm has greatly improved the attenuation of the throughput compared with other algorithms. Especially When the failure rate reach 20%, the algorithm only get 44.32% decay on the throughput, and other fault tolerant algorithms get 48%～70% decay.

networks-on-chips; congestion aware; Up*/Down*routing algorithm; weighted link

10.3979/j.issn.1673-825X.2017.02.005

2016-03-14

2016-06-18 通訊作者：吳鳳陽 wufengyang666@163.com

國家自然科學(xué)基金(61572520)

Foundation Item：The National Nature Science Foundation of China(61572520)

TN914.53

A

1673-825X(2017)02-0167-09

吳鳳陽(1989-)，男，河南信陽人，碩士研究生，主要研究方向?yàn)槠暇W(wǎng)絡(luò)容錯(cuò)路由技術(shù)。E-mail：wufengyang666@163.com。