一種片上網(wǎng)絡(luò)擁堵感知的自適應(yīng)容錯(cuò)路由算法

杭彥希,徐金甫,南龍梅

1(解放軍信息工程大學(xué),鄭州 450001) 2(復(fù)旦大學(xué) 專用集成電路與系統(tǒng)國家重點(diǎn)實(shí)驗(yàn)室,上海 200433)

1 引 言

隨著大數(shù)據(jù)和云計(jì)算等大批量、高速數(shù)據(jù)處理應(yīng)用的出現(xiàn),單核處理系統(tǒng)已經(jīng)遠(yuǎn)遠(yuǎn)不能滿足數(shù)據(jù)處理的需求,基于片上網(wǎng)絡(luò)互連的多核系統(tǒng)逐漸成為高性能數(shù)據(jù)處理系統(tǒng)發(fā)展的趨勢.而隨著片上核數(shù)的增加以及工藝尺寸的不斷縮小,由生產(chǎn)缺陷、工藝偏差和老化等原因?qū)е碌钠瞎收蠁栴}越來越突出,文獻(xiàn)[1]指出,天河、神威等超級計(jì)算機(jī)系統(tǒng)中處理器的核數(shù)已達(dá)到百萬量級以上,其平均無故障時(shí)間達(dá)到數(shù)小時(shí)已十分困難,高可靠性已成為多核處理系統(tǒng)發(fā)展的重要方向.而容錯(cuò)路由算法對于在故障條件下仍能保證系統(tǒng)的性能有著重要的作用,對容錯(cuò)路由算法的研究是多核系統(tǒng)可靠性研究的一個(gè)重要方面.

目前已有大量的文獻(xiàn)展開了對容錯(cuò)路由算法的研究,文獻(xiàn)[2]提出了一種較為經(jīng)典的容錯(cuò)的分布式可重構(gòu)路由算法,每個(gè)節(jié)點(diǎn)感知其周圍8個(gè)鄰節(jié)點(diǎn)的故障狀態(tài),采取繞行路由的方式避開故障節(jié)點(diǎn),并禁止東北角轉(zhuǎn)向來避免死鎖,但是其存在流量不均衡的問題，并且只能容忍一個(gè)節(jié)點(diǎn)故障.文獻(xiàn)[3]提出了一種適應(yīng)性容錯(cuò)路由算法Gradient,將目的節(jié)點(diǎn)分為8個(gè)區(qū)域,對于每個(gè)區(qū)域當(dāng)前節(jié)點(diǎn)采用不同的輸出端口優(yōu)先級順序路由數(shù)據(jù)包,但是這種方法輸出端口優(yōu)先級固定,且未充分考慮網(wǎng)絡(luò)的擁堵狀態(tài).文獻(xiàn)[4]提出了一種高度可靠的容錯(cuò)路由算法,但其需要在路由器中設(shè)置路由查找表,雖然增大了靈活性,但是面積開銷大且擴(kuò)展性不強(qiáng).文獻(xiàn)[5]提出了一種兩跳內(nèi)故障信息感知的方法,但是其對于部分雙鏈路故障無法覆蓋,且算法實(shí)現(xiàn)較復(fù)雜.文獻(xiàn)[6]提出了一種基于邏輯電路實(shí)現(xiàn)的分布式容錯(cuò)路由uLBDR,減少了面積開銷,但是故障覆蓋率不高,且其中的LBDRfork+dr算法只適用于虛擬直通交換方式,通用性不強(qiáng).文獻(xiàn)[7]也提出了一種基于邏輯電路實(shí)現(xiàn)的成本節(jié)約的路由算法,解決了LBDRfork+dr算法只能在虛擬直通交換方式中使用的限制,但是其故障覆蓋率仍然不高.

在實(shí)際的片上網(wǎng)絡(luò)應(yīng)用中,經(jīng)常會發(fā)生通道擁堵情況進(jìn)而阻止數(shù)據(jù)包的路由,而擁堵感知路由算法可以緩解片上擁堵狀態(tài).按照擁堵信息感知區(qū)域,可以將其分為本地?fù)矶滦畔⒏兄惴?、區(qū)域擁堵信息感知算法以及全局擁堵信息感知算法.對于本地?fù)矶滦畔⒏兄惴?文獻(xiàn)[8]利用當(dāng)前節(jié)點(diǎn)輸出端口可用緩存數(shù)作為擁堵度量值.文獻(xiàn)[9]提出了一種DyAD路由算法,其利用下游路由器輸入端口可用緩存槽數(shù)來判斷擁堵狀況.文獻(xiàn)[10]提出利用候選通道一定時(shí)間內(nèi)路由的微片數(shù)量來量化每個(gè)通道的帶寬進(jìn)而判斷擁堵.對于區(qū)域擁堵信息感知算法,文獻(xiàn)[11]提出一種RCA區(qū)域擁堵感知算法,其收集各節(jié)點(diǎn)本地?fù)矶聽顟B(tài)并通過一個(gè)監(jiān)控網(wǎng)絡(luò)傳輸,但是其面積開銷過大.文獻(xiàn)[12]提出利用鄰節(jié)點(diǎn)在目的節(jié)點(diǎn)方向的候選通道的可用緩存槽總數(shù)來判斷當(dāng)前節(jié)點(diǎn)的各個(gè)候選輸出端口的擁堵狀態(tài),其性能高于DyAD路由算法,但是其并未考慮鄰節(jié)點(diǎn)的擁堵狀態(tài).文獻(xiàn)[13]提出利用下游節(jié)點(diǎn)的通道狀態(tài)和交叉開關(guān)狀態(tài)來判斷擁堵信息.文獻(xiàn)[14]提出利用下游節(jié)點(diǎn)狀態(tài)和可用路徑數(shù)來判斷擁堵信息,但是這些方法仍存在擁堵信息判斷不充分且未考慮故障等問題.對于全局路由感知算法.文獻(xiàn)[15]提出了一種片上網(wǎng)絡(luò)全局擁堵感知的方法(Global Congestion Awareness,GCA),該方法提出在頭微片空閑位中增加流量向量,并在路由器中加入擁堵記錄及映射單元,通過頭微片與路由器的交互進(jìn)而獲得整個(gè)網(wǎng)絡(luò)的擁塞狀態(tài),但其受到微片大小的限制,實(shí)用性并不強(qiáng).根據(jù)文獻(xiàn)[16]大量的仿真實(shí)驗(yàn),可以發(fā)現(xiàn)擁堵主要發(fā)生在本地區(qū)域的部分節(jié)點(diǎn),并不需要通過文獻(xiàn)[15]提出的方法去感知全局的擁堵信息,相反會帶來更大的開銷.以上的這些擁堵感知的路由算法并未考慮到故障發(fā)生的情況,這對于路由算法的研究是不完善的.文獻(xiàn)[17]提出了一種粗粒度和細(xì)粒度的前瞻性容錯(cuò)路由算法,設(shè)定各端口輸出優(yōu)先級,利用下游節(jié)點(diǎn)輸入端口的緩存數(shù)作為擁堵判斷值,采取一種故障編碼與解碼方案,可以感知當(dāng)前節(jié)點(diǎn)周圍36條鏈路的故障情況,最后計(jì)算各個(gè)端口的權(quán)重值,選擇權(quán)重值最小的端口路由數(shù)據(jù)包,這種將故障信息和擁堵信息統(tǒng)一考慮的方法,不但計(jì)算復(fù)雜效率低下,而且面積開銷很大.文獻(xiàn)[18]基于LBDRdr算法提出了一種擁堵感知的二維片上網(wǎng)絡(luò)容錯(cuò)路由算法,但是其故障覆蓋率低,且采用的擁堵感知方法面積開銷很大.目前對于片上路由算法的研究主要存在兩個(gè)問題:①缺少高效的故障與擁堵感知方法;②在故障和擁堵都存在的情況下,缺少一種高效的路由算法.

綜合以上問題,本文提出了一種高效的擁堵與故障信息感知的片上網(wǎng)絡(luò)容錯(cuò)路由算法.文章有以下幾點(diǎn)創(chuàng)新之處:①結(jié)合故障實(shí)時(shí)檢測方法,提出一種新穎的節(jié)點(diǎn)鄰32鏈路故障感知機(jī)制;②根據(jù)路由器延時(shí)模型,提出了一種高效的擁堵信息感知機(jī)制;③對故障處理與擁堵處理進(jìn)行優(yōu)先級劃分,提出一套完備的自適應(yīng)容錯(cuò)機(jī)制,并基于邏輯電路設(shè)計(jì)了故障處理模塊和相應(yīng)的擁堵處理模塊.

2 故障及擁塞感知機(jī)制建立

為節(jié)約片上資源,本文算法的實(shí)現(xiàn)基于傳統(tǒng)的五端口無虛通道路由器,該路由器由東(E)、南(S)、西(W)、北(N)和本地(L)五端口、各端口輸入緩存、路由計(jì)算模塊(Routing Compute,RC)、交叉開關(guān)分配模塊(Switch Allocate,SA)以及相應(yīng)的連接線路組成.傳統(tǒng)的無虛通道路由器容易引起死鎖,本文采取的死鎖避免方式將在下文進(jìn)行介紹,首先介紹本文提出的故障及擁塞感知機(jī)制.

2.1 故障感知機(jī)制

故障感知機(jī)制主要包括故障模型建立、故障檢測與感知方法設(shè)計(jì)及故障感知區(qū)域建立.故障感知機(jī)制對于路由算法的容錯(cuò)性能至關(guān)重要,一個(gè)好的故障感知機(jī)制能極大的增加算法對故障的覆蓋率且能最大程度得減小因容錯(cuò)給片上網(wǎng)絡(luò)帶來的性能損失.結(jié)合文獻(xiàn)[5,19,20]的故障感知機(jī)制,本文提出一種新穎的節(jié)點(diǎn)鄰32鏈路故障實(shí)時(shí)感知機(jī)制.

2.1.1 故障感知區(qū)域

本文提出的故障感知機(jī)制是一種粗粒度的區(qū)域故障感知機(jī)制,其故障模型為將單向鏈路故障等效為雙向鏈路故障,將節(jié)點(diǎn)故障等效為與之相連的四條雙向鏈路故障.采用一種周期性故障檢測方法,每個(gè)路由節(jié)點(diǎn)在一定周期內(nèi)發(fā)送測試向量給鄰節(jié)點(diǎn),獲取到響應(yīng)向量后,與存儲在發(fā)送節(jié)點(diǎn)內(nèi)的正確向量做對比,若相同則認(rèn)為鏈路無故障,否則認(rèn)為鏈路發(fā)生故障.通過這種方法,每個(gè)節(jié)點(diǎn)能實(shí)時(shí)掌握與之相連的四條鏈路狀態(tài),但是通過這種方法定義的故障感知區(qū)域較小,對故障的覆蓋率較小.文獻(xiàn)[5,19]提出了一種兩跳范圍的故障感知區(qū)域,在一定程度上能覆蓋大部分的單鏈路故障,但對部分雙鏈路故障無法容忍.本文提出一種故障信息傳播機(jī)制,將故障感知區(qū)域擴(kuò)大到圖1所示的區(qū)域.假設(shè)圖中節(jié)點(diǎn)11為當(dāng)前節(jié)點(diǎn),此時(shí)節(jié)點(diǎn)11可以感知到虛線框內(nèi)鏈路①②③④⑤⑥⑦⑧共8條鏈路狀態(tài),將這些鏈路定義為當(dāng)前節(jié)點(diǎn)的北部鄰鏈路,其故障狀態(tài)分別表示為FN,FNW,FNE,FNWN,FNN,FNEW,FNNW,FNNE,當(dāng)其值為1時(shí)表示未發(fā)生故障,為0時(shí)表示無故障發(fā)生,并將①定義為北部直接鄰鏈路,②③⑤定義為北部初級鄰鏈路,④⑦⑥⑧定義為深級鄰鏈路.

圖1 節(jié)點(diǎn)鄰32鏈路故障實(shí)時(shí)感知區(qū)域示意圖Fig.1 Schematic diagram of the node′s adjacent 32 link online fault-aware region

2.1.2 故障信息傳播方案

為實(shí)現(xiàn)這種節(jié)點(diǎn)鄰32鏈路故障實(shí)時(shí)感知機(jī)制,本文設(shè)計(jì)了如圖2所示的故障信息傳播方案,在每個(gè)路由器內(nèi)部增加兩級故障感知信息傳播模塊(Fault-Aware Propagating,FAP),第一級為FAP1,第二級為FAP2,FAP1用于傳遞初級鄰鏈路故障信息,FAP2用于傳遞深級鄰鏈路故障信息,而直接鄰鏈路信息可直接通過鄰節(jié)點(diǎn)得到.

圖2 故障信息傳播方案Fig.2 Scheme of propagating of fault information

以圖2中節(jié)點(diǎn)R的西部端口為例為例,Fault_in[W]和Fault_out[W]是西部直接鄰鏈路R-R′的故障輸入和輸出信息,位寬都為1比特;FoN_in[W]代表R′的N,S,W端口的西部初級鄰鏈路故障信息,位寬為3比特;FoN_out[W]為R的N,S,E端口的東部初級鄰鏈路故障信息,位寬也為3比特;FoNN_in[W]代表R的西部深級鄰鏈路故障信息,位寬為4比特;FoNN_out[W]為R的東部深級鄰鏈路故障信息,位寬也為4比特.每個(gè)節(jié)點(diǎn)的各個(gè)端口只需存儲8條鄰鏈路信息,故在各端口增加3比特的故障狀態(tài)寄存器即可存儲節(jié)點(diǎn)周圍32條鏈路的故障狀態(tài).

2.2 擁塞感知機(jī)制

片上擁堵會極大影響片上網(wǎng)路的性能,不僅在出現(xiàn)故障時(shí)會發(fā)生片上擁堵,在處理大數(shù)據(jù)應(yīng)用時(shí)也會出現(xiàn)片上擁堵,常用的擁堵感知方案成本高,通用性不強(qiáng),如何高效的避免片上擁堵是片上網(wǎng)絡(luò)性能研究的重要方面.為此,本文提出了一種區(qū)域性低成本的片上網(wǎng)絡(luò)擁塞感知機(jī)制,其設(shè)計(jì)相應(yīng)的路由器延遲模型來衡量某一通道擁堵情況,并提出相應(yīng)的擁塞信息計(jì)算方案.

2.2.1 路由器延遲模型

文獻(xiàn)[21]指出路由器延時(shí)指數(shù)據(jù)包包頭從接受路由器服務(wù)到存儲在下游路由器的輸入緩存的時(shí)間,也即數(shù)據(jù)包包頭從上游路由器輸出端口輸出開始到下游路由器輸出端口輸出結(jié)束的時(shí)間,主要分為兩部分,其結(jié)構(gòu)如圖3所示.

第一部分延時(shí)是通道延時(shí),指數(shù)據(jù)包從路由器R輸出端口輸出到存儲在路由器R′中的時(shí)間,由緩存恒定延遲(τ′)以及緩存發(fā)送延遲(βo2i)構(gòu)成,第二部分是交叉開關(guān)延遲,由路由器服務(wù)時(shí)間(τ)以及端口分配延時(shí)(ρi2o′)構(gòu)成,則路由器總的延時(shí)可以描述為

L=τ′+βo2i+τ+ρi2o′

(1)

(1)式中τ′指輸入緩存空時(shí),包頭存儲到緩存中的時(shí)間,是固定延時(shí).τ指路由器無擁堵時(shí),路由器轉(zhuǎn)發(fā)一個(gè)微片所需的延時(shí),也為固定值.βo2i指從本地路由器O端口輸出的數(shù)據(jù)包等待下游路由器輸入方向i緩存空的時(shí)間,其值為下游路由器輸入端口i輸入緩存排空的時(shí)間,其值可近似為

(2)

(2)式中NBj指下游路由器端口j處的輸入緩存占用數(shù),j指端口i處的輸入緩存占用數(shù),fijp指輸入端口i與輸入端口j向同一端口p輸出的概率,其值為

fijp=fip×fjp,i≠j

(3)

圖3 路由器延遲模型Fig.3 Delay model of router

(4)

ρi2o′指數(shù)據(jù)微片平均等待得到下游路由器分配的輸出端口O′的時(shí)間,如果其輸出端口分配失敗就會被堵塞直至得到交叉開關(guān)的確認(rèn)信號.其值可表示為

(5)

在這里,因?yàn)橄掠温酚善鬏斎攵丝趇的微片的輸出端口O′固定,O′∈COC,所以fio′=1,則

(6)

COC′指下游節(jié)點(diǎn)候選輸出通道集合,N(COC′)為下游節(jié)點(diǎn)候選輸出通道的數(shù)量,NC代表除下游節(jié)點(diǎn)的輸入通道和候選輸出通道外的競爭通道的數(shù)量,一般為1/3.則路由器的延時(shí)可以描述為

dir={E,S,W,N,L}

(7)

其中O為本地路由器的輸出方向,i為與O相對的下游路由器的輸入方向,O′為下游路由器的輸出方向.

2.2.2 擁塞信息計(jì)算方案

本文利用下游路由器的延遲時(shí)間來衡量某一通道的擁塞程度,即對任一當(dāng)前節(jié)點(diǎn),分別計(jì)算出下游節(jié)點(diǎn)的預(yù)測延遲時(shí)間,選擇延遲時(shí)間最短的下游節(jié)點(diǎn)路由數(shù)據(jù)包.可通過(8)中判別式進(jìn)行判斷.

(8)

因?yàn)棣印?τ在路由器設(shè)計(jì)好后即為固定值,則(8)式可轉(zhuǎn)化為:

(9)

本文定義δo為某當(dāng)前節(jié)點(diǎn)輸出端口O的擁塞度量值,其值為

(10)

其中

o′∈coc′

為計(jì)算出當(dāng)前節(jié)點(diǎn)各端口的δo,各節(jié)點(diǎn)需實(shí)時(shí)獲得各方向下游節(jié)點(diǎn)的輸入緩存占用數(shù),需要增加多余的鏈路線來傳輸這些擁堵計(jì)算信息,其傳輸方法如圖4所示.

圖4 擁堵信息傳輸方法示意圖Fig.4 Schematic diagram of method for the fault information propagation

NB[i][j]為當(dāng)前節(jié)點(diǎn)方向i處的鄰節(jié)點(diǎn)的緩存占用信息,i指下游鄰節(jié)點(diǎn)的方向,i∈{E,S,W,N},j指位于下游鄰節(jié)點(diǎn)j方向的緩存數(shù),j∈{E,S,W,N,L},如圖所示,假設(shè)圖中R為當(dāng)前節(jié)點(diǎn),NB[E][E]_out指當(dāng)前節(jié)點(diǎn)向其E方向的鄰節(jié)點(diǎn)發(fā)送其E端口的緩存占用數(shù),NB[E][E]_in為當(dāng)前節(jié)點(diǎn)接收的在其E方向的鄰節(jié)點(diǎn)E端口的緩存占用數(shù),每條鏈路需增加2*5*log2(NS)的鏈路,NS為輸入FIFO中的緩沖槽數(shù)目,若NS為4,則每條鏈路共需增加20bits的線.通過這種擁堵信息傳輸方法,只需增加少量鏈路線并在路由器中增加少量計(jì)算單元,即可保證每個(gè)節(jié)點(diǎn)都實(shí)時(shí)掌握其鄰節(jié)點(diǎn)各輸入端口的緩存占用情況.

通過這種擁堵感知機(jī)制,擁堵選擇策略可建模為

SOC=argminδo,o∈COC

其中SOC代表當(dāng)前節(jié)點(diǎn)選擇的輸出通道(Selected Output Channel),COC代表當(dāng)前節(jié)點(diǎn)的候選輸出通道(Candidate Output Channel).每個(gè)節(jié)點(diǎn)在無故障的情況下,均可根據(jù)目的節(jié)點(diǎn)與當(dāng)前節(jié)點(diǎn)的關(guān)系,算出各個(gè)候選通道的擁堵度量值,并選擇擁塞程度低的端口路由數(shù)據(jù)包,能有效緩解擁堵情況.由文獻(xiàn)[19]可知,擁堵主要發(fā)生在本地區(qū)域的部分節(jié)點(diǎn),因此采用這種區(qū)域性擁塞感知機(jī)制可以覆蓋大部分的片上網(wǎng)絡(luò)擁堵情況,對于片上資源有限的多核互連結(jié)構(gòu)來說,這種方法是高效能的.

3 路由算法設(shè)計(jì)

3.1 算法描述

結(jié)合前文提出的故障及擁塞感知機(jī)制,本文實(shí)現(xiàn)了一種基于邏輯電路的擁堵感知的分布式容錯(cuò)路由算法,能同時(shí)處理故障以及擁塞情況,并且通過設(shè)置路由轉(zhuǎn)向允許位Rpq來避免網(wǎng)路死鎖的發(fā)生.算法主要思想是根據(jù)故障優(yōu)先級大于擁堵優(yōu)先級的原則,先利用故障邏輯電路處理片上故障情況,再通過擁塞處理模塊評估擁堵情況,最后得到數(shù)據(jù)包轉(zhuǎn)發(fā)方向.整個(gè)路由計(jì)算邏輯由組合電路構(gòu)成,主要分為故障處理邏輯和擁堵處理模塊,其整體框圖如圖5所示.

圖5 路由計(jì)算框圖Fig.5 Diagram of routing computing

故障處理邏輯根據(jù)當(dāng)前地址和目的地址的關(guān)系以及故障狀態(tài),得到數(shù)據(jù)包輸出的候選端口,再由擁塞處理模塊根據(jù)擁塞信息計(jì)算出最終的數(shù)據(jù)包轉(zhuǎn)發(fā)路徑.

其算法描述如圖6所示.算法輸入包括目的節(jié)點(diǎn)信息、當(dāng)前節(jié)點(diǎn)信息、鏈路故障信息以及路由轉(zhuǎn)向允許位,根據(jù)故障邏輯得出候選端口信息COC(N2,S2,W2,E2),N(COC)指候選端口數(shù)目,如果N(COC)為0,即因故障無可用輸出通道,則根據(jù)繞路邏輯采用非最短路徑路由數(shù)據(jù)包;如果N(COC)為1,即只有唯一的候選輸出通道,則無需考慮擁堵情況,以數(shù)據(jù)包能正確路由到目的節(jié)點(diǎn)為原則,選擇唯一可用的輸出通道;如果N(COC)為2,即存在兩個(gè)候選輸出通道,根據(jù)前文的擁堵度量方法,選擇擁堵值低的通道路由數(shù)據(jù)包,若擁堵值相同,任意選擇一候選通道路由數(shù)據(jù)包.

ProcedureoftheCAFTAlgorithm1CAFT(in：cur，des，F(xiàn)link，Rpqout：SQC)2{COC←Fault＿processing＿logic(cur，des，F(xiàn)link)3ifN(COC)=0 thenSOC←Deroute＿logic(cur，des)4ifN(COC)=1 thenSOC←Avaliable(COC)5ifN(COC)=26 δ[]←07 forallch1∈COCdo8 δo[ch1]←NBi9 COC＿d←Competingchannelsindownstreamrouter10 forallj∈COC＿ddo11 NBj←inputbufferdepthofjdirectionindownstreamrouter12 δ1[chl]+=(3/16+fjo′)×NBj13 endfor14 δ[ch1]=δo[ch1]+δ1[ch1]15 endfor16 C[]←chs．t．δ[ch]=min(δ[])17 ifC[]．size()=1 then SOC←C[0]18 elseSOC←Random()}

圖6 CAFT算法
Fig.6 Algorithm of CAFT

3.2 故障處理邏輯設(shè)計(jì)

故障處理邏輯首先提取出當(dāng)前節(jié)點(diǎn)及目標(biāo)節(jié)點(diǎn)的坐標(biāo)信息,經(jīng)由一個(gè)比較器電路計(jì)算出目標(biāo)節(jié)點(diǎn)與當(dāng)前節(jié)點(diǎn)的相對位置,其示意圖如圖7所示.

圖7 比較器電路Fig.7 Comparator circuit

此電路輸出8個(gè)位置信息,前四個(gè)信息dir1代表目的節(jié)點(diǎn)是否在當(dāng)前節(jié)點(diǎn)的dir方向且在dir方向上的距離差恰好為1,當(dāng)dir1為1時(shí)表示目的節(jié)點(diǎn)在當(dāng)前節(jié)點(diǎn)dir方向上且距離為1,否則為0;后四個(gè)信息dir′代表目的節(jié)點(diǎn)是否在當(dāng)前節(jié)點(diǎn)的dir方向,當(dāng)dir′為1表示目的節(jié)點(diǎn)在當(dāng)前節(jié)點(diǎn)dir方向上,否則為0.

故障處理邏輯最終是為了計(jì)算出候選端口N2、E2、S2、W2,而為了實(shí)現(xiàn)有效的路由轉(zhuǎn)向及避免死鎖,本文還在節(jié)點(diǎn)各端口增加路由轉(zhuǎn)向允許位(Routing bits),表示為Rpq,其代表從當(dāng)前節(jié)點(diǎn)p端口輸出的數(shù)據(jù)包是否可以在下游節(jié)點(diǎn)的q方向進(jìn)行轉(zhuǎn)向.當(dāng)Rpq為1時(shí),表示允許轉(zhuǎn)向,為0則表示禁止轉(zhuǎn)向.例如在某節(jié)點(diǎn)的N端口,存儲有RNW及RNE,其代表從當(dāng)前節(jié)點(diǎn)N端口輸出的數(shù)據(jù)包能否能在下一節(jié)點(diǎn)進(jìn)行向N或向E的轉(zhuǎn)向.

利用前文定義的故障信息及轉(zhuǎn)向允許位得到初步的無故障端口轉(zhuǎn)發(fā)信息,各端口具體邏輯如下.

圖8 N2端口故障處理邏輯Fig.8 Fault processing logic of N2 port

3.3 擁堵處理模塊

由故障處理模塊得到一個(gè)4比特的候選端口信息(Candidate Output Channel,COC),分別為N2、E2、S2、W2,為1表示可以轉(zhuǎn)發(fā),為0表示禁止轉(zhuǎn)發(fā).擁堵處理模塊的功能就是根據(jù)擁塞感知機(jī)制,計(jì)算出可轉(zhuǎn)發(fā)候選端口的各個(gè)方向的擁塞值,選擇擁堵程度最低的方向路由數(shù)據(jù)包,整個(gè)擁堵處理模塊示意圖如圖9所示.

圖中候選解碼模塊(Candidate Decoder,CD)用于解析COC信息,因?yàn)镃OC一共有三種狀態(tài),分別為全為0狀態(tài),只有一個(gè)為1的狀態(tài)及只有兩個(gè)為1的狀態(tài),當(dāng)COC出現(xiàn)全0時(shí)表示無可用轉(zhuǎn)發(fā)通道,則通過繞路由模塊選擇輸出通道;當(dāng)COC只有一個(gè)為1時(shí),選擇只能轉(zhuǎn)發(fā)的通道即圖中的C0進(jìn)行轉(zhuǎn)發(fā);當(dāng)COC只有兩個(gè)為1時(shí),由CD模塊選出為1的候選端口C1及C2,輸入到圖中虛線框內(nèi)的擁堵值計(jì)算模塊,選擇擁堵值最小的端口進(jìn)行數(shù)據(jù)包轉(zhuǎn)發(fā).

3.4 死鎖及活鎖避免方法

死鎖及活鎖避免是路由算法需要考慮的重要方面,本文通過設(shè)置路由轉(zhuǎn)向允許位來禁止一些特定的轉(zhuǎn)向以達(dá)到死鎖避免,主要方法是將轉(zhuǎn)向模型中一些禁止的轉(zhuǎn)向轉(zhuǎn)換成轉(zhuǎn)向允許位,1表示允許轉(zhuǎn)向,0表示禁止轉(zhuǎn)向,常用的轉(zhuǎn)向模型由XY轉(zhuǎn)向模型,OE轉(zhuǎn)向模型.為提高片上網(wǎng)絡(luò)性能本文利用文獻(xiàn)[22]提出的RTM轉(zhuǎn)向模型,列數(shù)非3能整除的列中的所有節(jié)點(diǎn)禁止NW和SW轉(zhuǎn)向,即設(shè)置這些節(jié)點(diǎn)的N端口的RNW及S端口的RSW為0,其余均為0;列數(shù)能被3整除的列中的所有節(jié)點(diǎn)禁止ES和EN轉(zhuǎn)向,即設(shè)置這些節(jié)點(diǎn)的E端口的RES及E端口的REN為1,其余均為0,通過這種方式可以大大增加因禁止轉(zhuǎn)向?qū)е碌钠暇W(wǎng)絡(luò)性能的損失.為了避免產(chǎn)生活鎖,本文在擁堵處理模塊中增加繞路由模塊(Deroute Logic),保證在無最短路由時(shí)通過采用非最短路由方式完成路由功能.

圖9 擁堵處理模塊示意圖Fig.9 Schematic diagram of congestion processing module

4 實(shí)驗(yàn)結(jié)果

在路由算法性能評估方面,本文修改了開源的周期精確的片上網(wǎng)絡(luò)仿真器作為實(shí)驗(yàn)平臺,搭建8*8的2D-mesh拓?fù)浣Y(jié)構(gòu),路由器設(shè)置為無虛通道,端口緩存深度為4個(gè)數(shù)據(jù)微片,數(shù)據(jù)包大小為8個(gè)微片,設(shè)置仿真總時(shí)間為23000個(gè)周期,前3000個(gè)周期為warmup時(shí)間;在路由器面積開銷方面,本文采用SMIC 55nm CMOS標(biāo)準(zhǔn)單元庫對本文所提出的路由器進(jìn)行綜合.

4.1 性能評估

本文實(shí)驗(yàn)對象主要是基準(zhǔn)XY維序路由算法,文獻(xiàn)[12]提出的NoP算法,文獻(xiàn)[13]提出的PCAS(DWSA)算法,文獻(xiàn)[7]提出的CERI算法,以及本文提出的(Congestion-aware Fault-Tolerant routing,CAFT)算法.實(shí)驗(yàn)方案為在不同故障模式下測試5種算法在不同流量場景下的平均延時(shí)和吞吐率.如圖10所示,為無故障、均勻流量模式下各算法的延遲和吞吐率對比圖.均勻流量模式一般在仿真時(shí)會用到,在實(shí)際的應(yīng)用中這種流量情況不會出現(xiàn),從圖10中可以看出,XY維序路由算法以及CERI-XY算法的性能最優(yōu),CAFT算法性能次之,NoP算法性能最差.這是因?yàn)楸M管XY維序路由算法不是自適應(yīng)的,但是在均勻流量模式下,各個(gè)節(jié)點(diǎn)的流量狀態(tài)相似,相當(dāng)于XY路由算法掌握了全局性的長遠(yuǎn)流量信息,并且其采取的先X方向后Y方向的路由方式使得片上的網(wǎng)絡(luò)流量分布更加均勻,減少了擁堵的發(fā)生.而CERI-XY算法在無故障下等效于XY算法,性能也較高,CAFT算法因?yàn)椴捎昧薘TM轉(zhuǎn)向模型,在一定程度上能均勻一定的流量,提高在均勻流量模式下的性能,且在低注入率下,CAFT算法的數(shù)據(jù)包平均延時(shí)還是比較小的.對于NoP和PCAS(DWSA)適應(yīng)性路由算法,其路徑較多采用了Z字形的路由方式,使得流量分布隨著注入率增加而越來越不均衡,增加了擁堵情況的發(fā)生進(jìn)而減小了性能.

圖10 無故障、uniform流量模式下延時(shí)與吞吐率對比圖Fig.10 Contrast diagram of delay and throughput in the mode of no-fault transope traffic

圖11是在無故障,transope流量模式下各算法的延時(shí)和吞吐率對比圖,transope是一種非均勻流量模式,源節(jié)點(diǎn)與目的節(jié)點(diǎn)的關(guān)系為Di=Si+b/2 mod b,其中Si(Di)指源地址(目的地址)的第ibits.從圖中可以看出,在非均勻流量模式下,XY和CERI-XY路由算法的性能最差,因?yàn)樗鼈內(nèi)鄙賹W(wǎng)絡(luò)擁堵狀態(tài)的感知,適應(yīng)度很低;NoP和PCAS(DWSA)算法的性能居中,因?yàn)槠淠芨兄骄W(wǎng)絡(luò)的擁堵狀態(tài),具有一定的自適應(yīng)度;CAFT算法的性能最佳,主要原因在于其考慮的擁堵因素比PCAS(DWSA)算法更充分,且采用了RTM轉(zhuǎn)向模型.CAFT算法相比較于NoP算法飽和吞吐率改善約為12.78%,相比較于PCAS(DWSA)算法飽和吞吐率改善約為3.34%.

圖11 無故障、transope流量模式下延時(shí)與吞吐率對比圖Fig.11 Contrast diagram of delay and throughput in the mode of no-fault transope traffic

為比較算法在故障模式下的適應(yīng)性,設(shè)定固定位置,固定數(shù)目的鏈路故障,并且假設(shè)故障已經(jīng)被檢測到且在系統(tǒng)運(yùn)行中不會改變,設(shè)定故障比例約為總鏈路的5%,同時(shí)為更接近于實(shí)際片上應(yīng)用環(huán)境,設(shè)定流量模式為transope.實(shí)驗(yàn)結(jié)果如圖12所示,從圖中可以看出,XY算法的性能最差,在實(shí)際的實(shí)驗(yàn)中也可以發(fā)現(xiàn)XY算法的丟包率非常嚴(yán)重,這是因?yàn)閄Y并未采取任何容錯(cuò)措施,適應(yīng)性最差,為體現(xiàn)CERI算法的容錯(cuò)性,選用CERI-OE,雖然其能容忍一定的錯(cuò)誤,但是性能還是不高,NoP和PCAS(DWSA)算法因?yàn)椴扇×艘欢ǖ膿矶屡袛啻胧?可以容忍部分的鏈路故障,但是性能仍然很差,對于CAFT算法,將故障和擁堵情況都考慮在內(nèi),其性能明顯優(yōu)于上述的算法.

圖12 5%鏈路故障,transope流量模式下延時(shí)與吞吐率對比圖Fig.12 Constrast diagram of delay and throughput in the mode of 5% fault transope traffic

4.2 面積開銷與分析

為實(shí)現(xiàn)本文所提出的路由算法,需要在路由器中增加相應(yīng)的故障與擁塞感知模塊以及相關(guān)的路由計(jì)算邏輯,在評估時(shí)不考慮故障實(shí)時(shí)檢測模塊.利用SMIC 55nm CMOS標(biāo)準(zhǔn)單元庫對路由器進(jìn)行綜合,與基準(zhǔn)路由器進(jìn)行比較,并計(jì)算出其與基準(zhǔn)路由器的相對面積比(Relative Area),其實(shí)驗(yàn)結(jié)果如表1所示.

表1 CAFT路由器面積開銷
Table 1 Comparison of different routing algrithms on area

RouterArea/μm2RelativeAreaXY15730．161CAFT20291．911．29

本文路由器面積開銷主要集中于故障感知模塊以及擁堵處理模塊,將本文所提路由器與NoP、PCAS(DWSA)、CERI路由器的面積開銷進(jìn)行對比,引入性能提高與面積開銷比(Ratio of Performance improvemet and Area overhead,RPA),其代表在不同模式下路由器相對于基準(zhǔn)路由器的性能提升百分比與面積開銷增加百分比的比值,性能比較對象是飽和吞吐率.注:本文路由器面積或性能對比都是相同的時(shí)鐘頻率下,其對比結(jié)果圖如表2所示.

表2 各路由器能效對比圖
Table 2 Comparison fo different routers on RPA

RouterRelativeAreaRPA1(transope，non?fault)RPA2(transope，5%?fault)XY100NoP1．241．311．12PCAS(DWSA)1．133．231．96CERI1．0306．41CAFT1．291．612．84

從表2中可以看出,CAFT算法在無故障和故障模式下都有著較好的性能提高與面積開銷比,是一種能適應(yīng)復(fù)雜模式的高效的自適應(yīng)容錯(cuò)路由算法.

5 結(jié) 語

本文選取片上網(wǎng)絡(luò)自適應(yīng)容錯(cuò)路由算法作為研究對象,針對目前片上路由算法處理復(fù)雜故障與擁堵情況能力不足且面積開銷大的缺點(diǎn),設(shè)計(jì)了節(jié)點(diǎn)周圍32條鏈路故障狀態(tài)感知的方法,并擴(kuò)展路由器延遲模型,根據(jù)鄰節(jié)點(diǎn)各端口的緩存占用數(shù),計(jì)算出當(dāng)前節(jié)點(diǎn)各候選通道的擁塞度量值,按照故障處理優(yōu)先級大于擁塞處理優(yōu)先級的順序,基于邏輯電路設(shè)計(jì)出高效的能適應(yīng)復(fù)雜片上狀態(tài)的路由算法.在無故障模式下,能確保數(shù)據(jù)包按擁堵值最低的方向路由;在故障模式下,以完成數(shù)據(jù)包正確路由為基本目標(biāo),能實(shí)現(xiàn)對片上故障的容忍,并在一定程度上均衡網(wǎng)絡(luò)流量,同時(shí)為節(jié)省片上資源,引入一種RTM轉(zhuǎn)向模型,在無虛通道的情況下既能保證算法無死鎖也能保證網(wǎng)絡(luò)性能達(dá)到最大.

[1] Ge Wei,Guo Li,Li Jing-hai,et al.The thinking about supercomputing development strategic direction[J].Proceedings of the Chinese Academy of Sciences,2016,31(6):614-623.

[2] Zhang Z,Greiner A,Taktak S.A reconfigurable routing algorithm for a fault-tolerant 2D-mesh network-on-chip[C].ACM/IEEE Design Automation Conference(DAC),Anaheim,California,USA,2008:441-446.

[3] Pratomo I,Pillement S.Gradient-an adaptive fault-tolerant routing algorithm for 2D mesh network-on-chips[C].Proceedings of the 2012 Conference on Design and Architectures for Signal and Image Processing(DASIP),Karlsruhe,Germany,2012.

[4] Fick D,Deorio A,Chen G,et al.A highly resilient routing algorithm for fault-tolerant NoCs[C].Design,Automation & Test in Europe Conference & Exhibition(DATE),Nice,France,2009:21-26.

[5] Feng C C,Lu Z H,Jantsc A,et al. FoN:fault-on neighbor aware routing algorithm for networks-on-chip[C].23rd IEEE International SOC Conference,2010:441-446.

[6] Rodrigo S,Flich J,Roca A,et al.Addressing manufacturing challenges with cost-efficient fault tolerant routing[C].NOCS 2010,Fourth ACM/IEEE International Symposium on Networks-On-Chip,Grenoble,France,2010:25-32.

[7] Bishnoi R,Laxmi V,Gaur M S,et al.CERI:cost-effective routing implementation technique for network-on-chip[C].International Conference on Vlsi Design,2015:59-64.

[8] Singh A,Dally W J,Gupta A K,et al.GOAL:a load-balanced adaptive routing algorithm for torus networks[C].Proceedings of the 30th Annual International Symposium on Computer Architecture(ISCA′03),2003:194-205.

[9] Hu J,Marculescu R.DyAD-smart routing for networks-on-chip[C].ACM/IEEE Design Automation Conference(DAC),San Diego,California,USA,2004:260-263.

[10] Lin Y,Xiang D.An effective congestion-aware selection function for adaptive routing in interconnection networks[C].International Conference on Parallel and Distributed Computing,Applications and Technologies,2010:156-165.

[11] Gratz P,Grot B,Keckler S W.Regional congestion awareness for load balance in networks-on-chip[C].IEEE 14th International Symposium on High Performance Computer Architecture(HPCA),2008:203-214.

[12] Ascia G,Catania V,Palesi M,et al.Implementation and analysis of a new selection strategy for adaptive routing in networks-on-chip[J].IEEE Transactions on Computers,2008,57(6):809-820.

[13] Chang E J,Hsin H K,Lin S Y,et al.Path-congestion-aware adaptive routing with a contention prediction scheme for network-on-chip systems[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,2014,33(1):113-126.

[14] Tsai P A,Kuo Y H,Chang E J,et al.Hybrid path-diversity-aware adaptive routing with latency prediction model in network-on-chip systems[C].International Symposium on Vlsi Design,Automation,and Test,2013:1-4.

[15] Ramakrishna M,Kodati V,Gratz P,et al.GCA:global congestion awareness for load balance in networks-on-chip[J].IEEE Transactions on Parallel & Distributed Systems,2016,27(7):2022-2035.

[16] Tang M,Lin X,Palesi M.Local congestion avoidance in network-on-chip[J].IEEE Transactions on Parallel & Distributed Systems,2016,27(7):2062-2073.

[17] Liu J,Harkin J,Li Y,et al.Fault-tolerant networks-on-chip routing with coarse and fine-grained look-ahead[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,2015,35(2):260-273.

[18] Gupta N,Sharma A,Laxmi V,et al.σnLBDR:generic congestion handling routing implementation for two-dimensional mesh network-on-chip [J].IET Computers & Digital Techniques,2016,10(5):226-232.

[19] Bahrebar P,Stroobandt D.Online reconfigurable routing method for handling link failures in NoC-based MPSoCs[C].International Symposium on Reconfigurable Communication-Centric Systems-on-Chip,2016:1-8.

[20] Ouyang Yi-ming,He Xin-cheng,Liang Hua-guo,et al.A fault-tolerant routing algorithm aiming at a path fault and local congestion in NoC[J].Acta Electronica Sinica,2016,44(4):920-925.

[21] Foroutan S,Thonnart Y,Petrot F.An iterative computational technique for performance evaluation of networks-on-chip[J].IEEE Transactions on Computers,2013,62(8):1641-1655.

[22] Tang M,Lin X,Palesi M.The repetitive turn model for adaptive routing[J].IEEE Transactions on Computers,2017,66(1):138-146.

[23] Tang M,Lin X,Palesi M.Routing pressure:a channel-related and traffic-aware metric of routing algorithm[J].IEEE Transactions on Parallel & Distributed Systems,2015,26(3):891-901.

[24] Tang M,Lin X,Palesi M.An offline method for designing adaptive routing based on pressure model[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,2015,34(2):307-320.

[25] Radetzki M,Feng C,Zhao X,et al.Methods for fault tolerance in networks-on-chip[J].Acm Computing Surveys,2013,46(1):28-36.

附中文參考文獻(xiàn)：

[1] 葛 蔚,郭 力,李靜海,等.關(guān)于超級計(jì)算發(fā)展戰(zhàn)略方向的思考[J].中國科學(xué)院院刊,2016,31(6):614-623.

[20] 歐陽一鳴,何鑫城,梁華國,等.針對路徑故障與局部擁塞的NoC容錯(cuò)路由算法[J].電子學(xué)報(bào),2016,44(4):920-925.