方 磊，董德尊，吳 際，夏 軍，王克非

(國防科學(xué)技術(shù)大學(xué)計(jì)算機(jī)學(xué)院，湖南 長沙 410073)

1 引言

未來片上多核體系結(jié)構(gòu)的發(fā)展需要片上互連網(wǎng)絡(luò)NoC(Network-on-Chip)提供更高的通信帶寬、更好的可擴(kuò)展性。片上網(wǎng)絡(luò)技術(shù)的發(fā)展面臨的一個(gè)主要問題是怎樣有效利用片上網(wǎng)絡(luò)所提供的帶寬資源[1]。片上網(wǎng)絡(luò)的帶寬資源可分為兩類，一類是路由器內(nèi)部帶寬資源，另一類是路由器外部帶寬資源[1]。內(nèi)部帶寬資源的高效利用可以采用高效的路由算法[2,3]、先進(jìn)的流控機(jī)制[4]等來實(shí)現(xiàn)。在普通的片上網(wǎng)絡(luò)中，外部帶寬資源是由連接路由器之間的兩條單向鏈路帶寬所決定的，通常每一條鏈路只傳輸一個(gè)方向的數(shù)據(jù)報(bào)文。研究發(fā)現(xiàn)[5]，網(wǎng)絡(luò)流量在網(wǎng)絡(luò)中通常不對(duì)稱分布[6]，導(dǎo)致兩個(gè)相連路由器之間在多數(shù)情況下僅會(huì)出現(xiàn)單向傳輸?shù)那闆r，這造成另一條負(fù)責(zé)反方向傳輸?shù)逆溌烦Ｌ幱诳臻e狀態(tài)，鏈路帶寬資源得不到充分的利用。圖1是我們利用BookSim[7]模擬器對(duì)4×4的Mesh網(wǎng)絡(luò)測試不同的合成負(fù)載所獲得的鏈路平均利用率的統(tǒng)計(jì)結(jié)果。可以看出，在uniform流量模式下，鏈路帶寬資源利用相對(duì)較為平均，鏈路的平均利用率能達(dá)到60%左右，然而在transpose流量模式下，鏈路的平均利用率的差異尤為巨大，甚至多條鏈路始終處于空閑狀態(tài)。

Figure 1 4×4 Mesh network link utilization(the deeper the color the link utilization ratio is lower)圖1 4×4 Mesh網(wǎng)絡(luò)鏈路利用率(顏色越深鏈路的利用率越低)

為了實(shí)現(xiàn)鏈路資源的動(dòng)態(tài)分配，將鏈路資源按需分配，文獻(xiàn)[5,8,9]等提出了各自的鏈路方向調(diào)度機(jī)制。目前,雙向鏈路調(diào)度的難點(diǎn)是怎樣在長傳輸報(bào)文的路徑中進(jìn)行盡可能多跳的雙向通道傳輸，建立端到端之間的數(shù)據(jù)傳輸通道，以減少局部單條鏈路傳輸對(duì)緩沖區(qū)帶來的壓力。在之前的研究中，只針對(duì)單跳路由器進(jìn)行雙向通道分配策略制定，而沒有全局進(jìn)行鏈路帶寬資源分配以實(shí)現(xiàn)在數(shù)據(jù)包的整個(gè)路徑上調(diào)度鏈路資源。

本文中，我們首次嘗試在數(shù)據(jù)包的端到端多跳傳輸路徑上實(shí)現(xiàn)雙向鏈路調(diào)度機(jī)制，盡可能為端到端的傳輸建立更多的雙向鏈路通路。我們提出了一種全新的雙向鏈路調(diào)度算法，該算法與已有的各種調(diào)度算法的關(guān)鍵不同之處在于，路由器的每一個(gè)端口均設(shè)置了一條享有最高輸出使用權(quán)的輸出主通道，路由器使用自己的輸出主通道無需申請(qǐng)，同時(shí)還設(shè)置了一條和主通道對(duì)應(yīng)的輸出副通道，其使用只需要簡單查詢即可。

本文提出了一種低開銷的路由器內(nèi)部通路動(dòng)態(tài)加寬機(jī)制。為了實(shí)現(xiàn)端到端的多跳雙向鏈路通路，需要加寬該路徑通過路由器時(shí)的傳輸通路，否則標(biāo)準(zhǔn)的路由器通路將成為帶寬瓶頸。在已有的雙向鏈路方案中，無一例外均在路由器內(nèi)部使用了輸入端口加速(Speedup)和交叉開關(guān)加速的方法。根據(jù)已有的相關(guān)研究成果[9,10]，交叉開關(guān)以及輸入緩沖的面積和功耗往往占據(jù)了NoC路由器面積和功耗的90%以上，如果選擇增加交叉開關(guān)端口數(shù)，端口數(shù)由n變?yōu)?n時(shí)，交叉開關(guān)的面積將由n2變成4n2，這些機(jī)制還將面臨鏈路兩頭的切片重排序問題。而且，雙向通道的同時(shí)同向傳輸并不是在多數(shù)情況下出現(xiàn)，這就會(huì)造成預(yù)置的多余資源多數(shù)時(shí)間處于空閑狀態(tài)。我們根據(jù)相關(guān)旁路設(shè)計(jì)思想[11]，在原有交叉開關(guān)數(shù)據(jù)通路之外重新設(shè)置一條低開銷的旁路數(shù)據(jù)傳輸通道。該數(shù)據(jù)通路能夠允許數(shù)據(jù)不經(jīng)過開關(guān)仲裁只需一個(gè)時(shí)鐘就能路由通過，并將該通路命名為快速通道FC(Fast Channel)。

我們?cè)谄暇W(wǎng)絡(luò)模擬器BookSim[7]上實(shí)現(xiàn)了本文所設(shè)計(jì)的雙向鏈路路由器，并在Mesh網(wǎng)絡(luò)中評(píng)估了雙向鏈路路由器的性能，網(wǎng)絡(luò)模擬的結(jié)果顯示，使用該雙向鏈路路由器比使用一般的單向鏈路路由器能提高60%左右的網(wǎng)絡(luò)吞吐率。通道平均利用率能夠得到20%以上的提升。

2 研究背景

提升片上網(wǎng)絡(luò)的性能有兩種方法，一種是提供更多的網(wǎng)絡(luò)資源，第二種是高效地利用片上網(wǎng)絡(luò)已有的資源。第一種方法，在面積、功耗等日益受限的情況下變得越來越不可取。據(jù)相關(guān)研究，片上網(wǎng)絡(luò)已經(jīng)占據(jù)了芯片功耗的30%左右[10]，因此必須研究各種能夠更加高效地利用片上網(wǎng)絡(luò)資源的方法。

鏈路資源同片上網(wǎng)絡(luò)路由器中的其他帶寬資源一樣，對(duì)網(wǎng)絡(luò)性能的提升至關(guān)重要。在芯片日益微小化的未來，硅片面積資源將變得十分緊缺，然而在采用片上網(wǎng)絡(luò)的片上多核體系結(jié)構(gòu)中，更多的連線將帶來更復(fù)雜的布線工作，同時(shí)系統(tǒng)也將變得更加脆弱。并且，如圖1所示，目前一般的單向鏈路路由器所組成的網(wǎng)絡(luò)中，即使在網(wǎng)絡(luò)達(dá)到飽和的情況下，鏈路資源的利用率平均最高只能達(dá)到60%，網(wǎng)絡(luò)中的鏈路資源在很多流量模式下處于嚴(yán)重的使用不平衡狀態(tài)。目前已有相關(guān)研究鏈路帶寬資源動(dòng)態(tài)調(diào)度。

文獻(xiàn)[8]首次提出了一種雙向鏈路的動(dòng)態(tài)調(diào)度方法。它在一條鏈路的兩頭分別設(shè)置一個(gè)擁有三種狀態(tài)的有限狀態(tài)機(jī)FSM(Finite Stete Machine)以控制鏈路的傳輸方向。該機(jī)制是一種基于申請(qǐng)和應(yīng)答的方法，鏈路兩頭的路由器分別通過一條信號(hào)線向另一頭的鏈路控制FSM請(qǐng)求鏈路使用權(quán)。由于需要等待應(yīng)答，這種方法中狀態(tài)機(jī)由輸入狀態(tài)向輸出狀態(tài)翻轉(zhuǎn)必須由一個(gè)計(jì)數(shù)器來控制，該計(jì)數(shù)器記錄未收到輸入請(qǐng)求的時(shí)鐘數(shù)，這使得鏈路常需要至少四個(gè)時(shí)鐘周期才能改變傳輸方向，并且這種調(diào)度方法將會(huì)出現(xiàn)兩條鏈路均向一個(gè)方向傳輸而另一方向的數(shù)據(jù)包需等待鏈路可用的情形。文獻(xiàn)[9]提出了一種更加細(xì)粒度的通道資源分配機(jī)制，它將數(shù)據(jù)切片分成更小的傳輸單元phit，將鏈路分成更小的多條lane。以鏈路兩頭的請(qǐng)求數(shù)量來按一定的比例分配帶寬資源，即lane的數(shù)量。該方案中數(shù)據(jù)切片在鏈路的兩頭需要復(fù)雜的flit切分與組裝機(jī)制，這不僅增加了數(shù)據(jù)包的網(wǎng)絡(luò)延遲、又需要輸出緩沖，大大地降低了資源的利用率。除此之外，文獻(xiàn)[5]也提出了類似于文獻(xiàn)[8]的雙向通道方案。這些方案具有共同的特點(diǎn)，即都加寬了基礎(chǔ)路由器的原有數(shù)據(jù)通路，例如交叉開關(guān)的帶寬、輸入緩沖區(qū)帶寬等，基于請(qǐng)求應(yīng)答的通道調(diào)度不能有效保障服務(wù)質(zhì)量的同時(shí)，還給鏈路方向轉(zhuǎn)換帶來了不必要的等待時(shí)間。

基于上述背景，本文設(shè)計(jì)了一種新的雙向通道調(diào)節(jié)機(jī)制，該機(jī)制不需要請(qǐng)求應(yīng)答。每條雙向鏈路僅需一條傳輸電平信號(hào)的信號(hào)線就已足夠交互鏈路使用信息。路由器為每個(gè)輸出端口均設(shè)置了一條叫做輸出主鏈路的雙向鏈路，路由器對(duì)自己的輸出主鏈路享有最高的使用權(quán)限，這樣保證了路由器隨時(shí)可以使用鏈路發(fā)送數(shù)據(jù)包。為了支持兩倍鏈路帶寬，該設(shè)計(jì)不加寬路由器內(nèi)部交叉開關(guān)的帶寬，而是采用旁路的思想，設(shè)置一條不需要經(jīng)過原有交叉開關(guān)的通道——快速通道，該通道動(dòng)態(tài)連接輸入端口和可用的輸出副鏈路。由于采用了一種簡單的查詢機(jī)制，不需要復(fù)雜的仲裁，使用該通道的切片僅需要一個(gè)周期便能夠從輸出副通道流出。并且，該路由器的快速通道調(diào)度機(jī)制利用了一定的全局信息，提升雙輸入端口的優(yōu)先級(jí)，使得使用兩條鏈路同向傳輸?shù)臄?shù)據(jù)包將會(huì)有更大的概率再次使用兩條同向傳輸，該數(shù)據(jù)包的傳輸路徑上將會(huì)建立更長的兩倍帶寬。

3 詳細(xì)設(shè)計(jì)

本節(jié)將基于Mesh網(wǎng)絡(luò)拓?fù)溆懻摫疚乃O(shè)計(jì)路由器的詳細(xì)構(gòu)造和工作機(jī)制。并以文獻(xiàn)[1]所提出的虛通道片上網(wǎng)絡(luò)路由器為基礎(chǔ)。該路由器擁有四級(jí)流水線，分別是路由計(jì)算(RC)、虛通道分配(VA)、開關(guān)分配(SA)以及交叉開關(guān)通過(ST)階段。每一級(jí)流水線需要一個(gè)時(shí)鐘周期。同時(shí)假設(shè)Mesh網(wǎng)絡(luò)的鏈路延遲為一個(gè)時(shí)鐘周期，并根據(jù)文獻(xiàn)[1]將鏈路傳輸階段記為LT。為了便于描述，首先將引入輸出主鏈路和副鏈路的概念。然后基于這兩個(gè)概念介紹鏈路方向調(diào)度算法。第3.3節(jié)將介紹快速通道的結(jié)構(gòu)與工作原理，第3.4節(jié)將給出支持同時(shí)讀取和寫入兩個(gè)數(shù)據(jù)切片的輸入緩沖區(qū)結(jié)構(gòu)以及流控。

3.1 輸出主鏈路與輸出副鏈路

一般的單向鏈路網(wǎng)絡(luò)中，路由器之間由兩條單向鏈路連接。圖2是普通網(wǎng)絡(luò)中相連的路由器A和B。路由器A的南輸入端口與西輸入端口競爭東輸出，最終南輸入端口建立了一條與東輸出端口的虛鏈路連接。由于其余各端口無數(shù)據(jù)發(fā)送，鏈路C2等一直處于空閑狀態(tài)。如果此時(shí)A能夠利用空閑的輸入鏈路C2作為輸出鏈路，這將大大提高網(wǎng)絡(luò)的性能。在圖3中，路由器A、B之間的單向鏈路被雙向鏈路所替代，并且路由器內(nèi)部結(jié)構(gòu)已經(jīng)加上了支持利用雙向鏈路的功能模塊。

Figure 2 Unidirectional network圖2 單向鏈路網(wǎng)絡(luò)

Figure 3 Bidirectional network圖3 雙向鏈路網(wǎng)絡(luò)

路由器對(duì)端口間的兩條雙向鏈路的其中一條享有最高的輸出使用優(yōu)先權(quán)，并將此鏈路叫做該路由器的輸出主鏈路，而另外一條只有在其空閑的時(shí)候才能用作輸出的鏈路叫做輸出副鏈路。為了簡化鏈路方向調(diào)節(jié)機(jī)制，所有輸出主鏈路空閑時(shí)均默認(rèn)為輸入狀態(tài)，并通過多路選擇器連接到對(duì)應(yīng)的輸入端口。在圖3中，鏈路C1為路由器A的輸出主鏈路，因?yàn)锳需要使用輸出端口，故將其傳輸方向改為輸出；鏈路C2為路由器B的輸出主鏈路、路由器A的輸出副鏈路，由于路由器B的西向無數(shù)據(jù)需要輸出，故A可以將其申請(qǐng)作為輸出。在圖3的情形中，路由器的東端口贏得了輸出副鏈路，并通過鏈路C2建立了一條連接路由器B東輸入端口的數(shù)據(jù)通路。

引入輸出主鏈路和副鏈路機(jī)制保證了任何路由器在需要發(fā)送數(shù)據(jù)的時(shí)候均有鏈路可用，而無需等待鏈路空閑。當(dāng)路由器的某端口同時(shí)收到兩個(gè)數(shù)據(jù)切片，并且這兩個(gè)數(shù)據(jù)切片均來自同一個(gè)數(shù)據(jù)包時(shí)，輸入端口默認(rèn)將輸出副鏈路收到的切片放在輸出主鏈路收到的數(shù)據(jù)切片之前。

3.2 鏈路方向控制協(xié)議

鏈路方向控制協(xié)議將根據(jù)輸出請(qǐng)求和輸出副通道的可用狀態(tài)來調(diào)節(jié)鏈路的傳輸方向，是一種基于請(qǐng)求和查詢的方法。

Figure 4 Pipeline of NOC router:RC(Routing Computation) VA(Virtual Channel Allocation),SA(Switch Allocation),ST(Switch Traversal), and LT(Link Traversal)圖4 片上網(wǎng)絡(luò)路由器四級(jí)流水線：RC(路由計(jì)算)、VA(輸出虛擬通道分配)、SA(開關(guān)分配)、ST(開關(guān)通過)、LT(鏈路傳輸)

圖4是經(jīng)典路由器的四級(jí)流水線流程。數(shù)據(jù)包的頭切片將經(jīng)由RC、VA、SA和ST四個(gè)流水級(jí)再加上一個(gè)鏈路傳輸LT總共是五級(jí)流水才進(jìn)入下一跳路由。在Mesh網(wǎng)絡(luò)中，這通常需要五個(gè)時(shí)鐘周期。在流水線的RC階段路由器就能夠知道該數(shù)據(jù)包所需的輸出端口，基于信用的流控中，在SA階段的末尾輸入端口將檢查相應(yīng)端口的信用情況，確定是否可以申請(qǐng)交叉開關(guān)。

在本文所設(shè)計(jì)的協(xié)議中，鏈路方向的調(diào)整同樣需要相連路由器之間交換有關(guān)鏈路的使用信息，與已有的方法相比，通道請(qǐng)求不再由輸入端口發(fā)出，代替的是為每一個(gè)輸出端口設(shè)置一個(gè)請(qǐng)求數(shù)寄存器來記錄該輸出端口的請(qǐng)求數(shù)量。路由器為每個(gè)輸出端口的輸出主鏈路設(shè)置一個(gè)方向控制器，該方向控制器監(jiān)控輸出端口請(qǐng)求寄存器中相應(yīng)端口的寄存器值。同時(shí)也為輸出副鏈路設(shè)置了一個(gè)方向寄存器，接收對(duì)方路由器輸出主鏈路方向控制器所發(fā)出的電平信號(hào)。在已有的方法中，請(qǐng)求信號(hào)到達(dá)相連路由器的方向控制器需要兩個(gè)時(shí)鐘，然而在本文提出的信息傳輸由于方向控制器與輸出請(qǐng)求并行工作，所以只需要一個(gè)鏈路延遲就能夠?qū)㈡溌房捎眯畔鬟f到相連路由器。

圖5是本文所設(shè)計(jì)的鏈路接口邏輯框圖。圖中Main為輸出主鏈路，Sub為輸出副鏈路。VA、SA、ST表示數(shù)據(jù)切片經(jīng)過的三個(gè)流水線階段(沒有畫出RC)。輸出副鏈路狀態(tài)寄存器Dir_reg，輸出主鏈路方向控制器Dir_controller，輸出端口請(qǐng)求數(shù)寄存器 Outputs_req Register。輸出主鏈路在輸出空閑的時(shí)候均用作輸入，而輸出副鏈路在Dir_reg值為零時(shí)用作輸出。鏈路方向控制的工作過程如下：在每一個(gè)頭切片成功完成虛通道(VC)分配以后，對(duì)應(yīng)的輸出端口請(qǐng)求寄存器加1，輸出主鏈路方向控制器(Dir_controller)一旦發(fā)現(xiàn)相應(yīng)的寄存器值不為零，首先將data_out信號(hào)線拉高以通知相連路由器，并在兩個(gè)時(shí)鐘之后將方向設(shè)置為輸出，因?yàn)閮蓚€(gè)時(shí)鐘周期之后申請(qǐng)輸出的數(shù)據(jù)切片剛好穿過交叉開關(guān)到達(dá)輸出端口。只要輸出端口請(qǐng)求數(shù)目不變?yōu)榱悖较蚩刂破饕恢本S持端口的輸出狀態(tài)。為了降低硬件復(fù)雜度，同一個(gè)數(shù)據(jù)包只有在尾切片SA成功的時(shí)候才將輸出端口的請(qǐng)求撤銷，如果此時(shí)輸出請(qǐng)求寄存器的值變成了零，輸出主鏈路方向控制器將Data_out信號(hào)線拉低，并在兩個(gè)時(shí)鐘周期之后將主輸出鏈路的方向設(shè)置為輸入狀態(tài)。在很大程度上路由器只負(fù)責(zé)調(diào)節(jié)自己各端口的輸出主鏈路的傳輸方向。輸出副鏈路的使用主要靠快速通道控制器來調(diào)度。

Figure 5 Bidirectional link scheduling interface圖5 雙向鏈路調(diào)度接口

3.3 快速通道

圖6是本文所設(shè)計(jì)的交叉開關(guān)旁路結(jié)構(gòu)框圖，F(xiàn)C表示快速通道(Fast Channel)。假設(shè)該路由器有四個(gè)端口，輸入端口緩沖的兩個(gè)輸出分別連接交叉開關(guān)和一個(gè)4到1的多路選擇器，多路選擇器的輸出再連接到一個(gè)1到4的多路選擇器。多路選擇器的四個(gè)輸出分別連接到每個(gè)輸出端口的輸出副鏈路。每一條VC分配成功的非空輸入VC均可向FC控制器(FC Controller)申請(qǐng)快速通道的使用權(quán)，F(xiàn)C控制器根據(jù)輸出副鏈路可用狀態(tài)來屏蔽輸出副鏈路不可用以及所申請(qǐng)的輸出端只有一個(gè)待發(fā)送數(shù)據(jù)切片的請(qǐng)求。FC控制器每個(gè)時(shí)鐘周期只選擇一個(gè)請(qǐng)求。過程如下：

(1)首先確定輸出副鏈路的可用狀態(tài)，屏蔽不滿足條件的申請(qǐng)；

(2)找到同時(shí)接收兩個(gè)切片的VC(雙輸入VC)，給予其最高的優(yōu)先級(jí)；

(3)尋找雙輸入VC失敗，找到輸入緩沖占用率最高的VC，給予FC使用權(quán)；

(4)如遇到占用率相同的VC，選出輸出端口最為擁擠的申請(qǐng)，即比較輸出端口請(qǐng)求數(shù)。

Figure 6 Crossbar bypass structure圖6 交叉開關(guān)旁路結(jié)構(gòu)框圖

FC控制器將會(huì)利用各輸出端口以及VC中的循環(huán)優(yōu)先級(jí)寄存器來最終確定獲勝的VC。通常在大部分情況下總能找到一個(gè)占用率最高的VC。為了在數(shù)據(jù)包傳輸?shù)穆窂缴峡梢允褂酶嗟膬杀稁?，所以如果某輸入虛通道在同一時(shí)鐘收到了兩個(gè)數(shù)據(jù)切片，則增加其申請(qǐng)快速通道的優(yōu)先級(jí)。這樣在這個(gè)數(shù)據(jù)包的整個(gè)傳輸路徑上將會(huì)有更多的機(jī)會(huì)形成一條更長的兩倍帶寬的路徑，加寬端到端的鏈路帶寬。同時(shí)給予較擁堵VC較高優(yōu)先級(jí)，能加快其數(shù)據(jù)流出，這往往能夠解決在單向鏈路網(wǎng)絡(luò)中所遇到的鏈路擁塞問題。通過在模擬器上對(duì)各種方案進(jìn)行對(duì)比，這樣的方案能夠獲得最好的性能。

圖7在一般路由器流水線的基礎(chǔ)上展示了快速通道的操作時(shí)序。結(jié)合圖5，它的工作原理如下：在cycle1時(shí)，路由器A收到了第一個(gè)數(shù)據(jù)包頭切片并完成了路由計(jì)算，輸出VC分配成功之后，在cycle2申請(qǐng)輸出主鏈路，輸出主鏈路方向控制器在cycle5將方向設(shè)置為輸出。尾切片在cycle5Switch分配成功并將輸出請(qǐng)求減1使得請(qǐng)求數(shù)變?yōu)?，輸出主鏈路方向控制器在兩個(gè)周期之后將鏈路設(shè)置為輸入。鏈路另一頭的路由器B，其FC控制器在cycle3檢測出副輸出通道可用，并讓一個(gè)目的端口為該端口的切片flit1獲得了快速通道的使用權(quán)而進(jìn)入FC流水級(jí)，在cycle4使用副輸出鏈路傳輸?shù)铰酚善鰽中。在cycle4輸出副鏈路不可用，flit2不能進(jìn)入快速通道，直到cycle7收到輸出副鏈路的釋放信號(hào)。從框圖可以看出，兩個(gè)路由器對(duì)鏈路方向的調(diào)節(jié)可以使鏈路時(shí)分復(fù)用,高效地使用鏈路帶寬資源。

Figure 7 Fastchannel operation timing sequence圖7 快速通道操作時(shí)序

3.4 緩沖區(qū)管理及流控

(1)輸入緩沖管理。有緩沖路由比無緩沖路由有無可比擬的性能優(yōu)勢，所以本設(shè)計(jì)仍然采用有緩沖路由器。雙向鏈路路由器的輸入緩沖必須支持同時(shí)寫入和讀取兩個(gè)數(shù)據(jù)切片。參考文獻(xiàn)[5]使用了類似參考文獻(xiàn)[6]在異構(gòu)片上網(wǎng)絡(luò)中采用的將輸入緩沖分成兩部分的設(shè)計(jì)方法，在他們的基礎(chǔ)上，本文設(shè)計(jì)了一種同樣基于將緩沖分成兩部分的組織結(jié)構(gòu)。

Figure 8 Structure of input port圖8 輸入端口結(jié)構(gòu)

圖8a為雙向鏈路路由器的輸入緩沖結(jié)構(gòu)。設(shè)每一個(gè)輸入端口的VC數(shù)量為v，每個(gè)端口需要兩個(gè)1到v的多路選擇器，第一條連接到副輸出通道(sub_out)，第二條連接到主輸出通道(main_out)。每一條VC需要一個(gè)組裝器，用于將收到的切片寫入緩沖區(qū)，組裝器會(huì)將從副輸出通道收到的數(shù)據(jù)切片放在主輸出通道收到的切片之前。VC緩沖分成兩部分，分別命名為主緩沖區(qū)和副緩沖區(qū)，數(shù)據(jù)包頭切片只能存放在主緩沖區(qū)，數(shù)據(jù)包體切片依次交錯(cuò)存放在主副緩沖區(qū)中，如圖中切片頭切片a，體切片b、c、d、e和尾切片f。除了參考文獻(xiàn)[1]中路由器輸入端口VC所需要的幾組標(biāo)志寄存器外，增加一個(gè)標(biāo)志位F，用于指示目前該VC中最靠前的切片是處于主緩沖區(qū)還是副緩沖區(qū)，F(xiàn)位為0表示最靠前切片位于主緩沖區(qū)，為1表示位于副緩沖區(qū)。增加標(biāo)志位D指示該VC是否同時(shí)收到兩個(gè)數(shù)據(jù)切片。當(dāng)輸入端口單獨(dú)獲得交叉開關(guān)或者快速通道的時(shí)候，只需要將標(biāo)志位F所指定的緩沖區(qū)頭切片發(fā)送出去即可。如果同時(shí)需要讀取兩個(gè)切片，則將最靠前的切片發(fā)送到Crossbar、將接下來的切片發(fā)送到快速通道。圖8b為組裝器的內(nèi)部結(jié)構(gòu)，它使用來自副輸出鏈路的數(shù)據(jù)有效信號(hào)(Data_valid)和標(biāo)志位F信號(hào)控制數(shù)據(jù)的寫入位置。Main buffer和Sub buffer分別表示主和副緩沖區(qū)。

(2)流控。雙向鏈路路由器的流控機(jī)制采用片上網(wǎng)絡(luò)中常用的基于信用(Credit)的流控機(jī)制。由于快速通道和交叉開關(guān)并行工作，且有可能會(huì)同時(shí)傳輸同一數(shù)據(jù)包的兩個(gè)切片，所以FC控制器需要兩個(gè)信用才能向輸出副通道發(fā)送數(shù)據(jù)。同時(shí)為每一條雙向鏈路設(shè)置兩條信用通道，分別用來傳送相反方向的信用。路由計(jì)算模塊等其他模塊功能不變，并由它們解決諸如死鎖避免等問題。相關(guān)內(nèi)容請(qǐng)參考文獻(xiàn)[2,3]等。

4 性能評(píng)估

4.1 實(shí)驗(yàn)設(shè)置

本文在片上網(wǎng)絡(luò)模擬器BookSim[7]中實(shí)現(xiàn)了本文提出的雙向鏈路路由器。實(shí)驗(yàn)使用的拓?fù)錇镸esh。實(shí)驗(yàn)發(fā)現(xiàn)，在不同的路由器資源下性能提升具有相似的趨勢，單一網(wǎng)絡(luò)資源配置并未失去一般性，所以在此處本文的實(shí)驗(yàn)討論的配置為：路由器每一個(gè)輸入端口均有四個(gè)虛擬通道(VC)，VC深度為8 flit。每個(gè)數(shù)據(jù)包由10個(gè)flit構(gòu)成，每一個(gè)切片的大小為128 bit。Mesh網(wǎng)絡(luò)使用DOR路由，采用基于信用的流控機(jī)制。一般路由器使用單向鏈路。實(shí)驗(yàn)評(píng)估了4×4 和 8×8兩種不同網(wǎng)絡(luò)規(guī)模下雙向鏈路路由器的性能。同時(shí)，本文在一條交叉開關(guān)旁路的基礎(chǔ)上又另外實(shí)現(xiàn)了一種擁有兩條交叉開關(guān)旁路(即快速通道)雙向鏈路路由器。每一個(gè)輸入端口仍然最多只能同時(shí)發(fā)送兩個(gè)數(shù)據(jù)切片。兩條快速通道的實(shí)現(xiàn)中FC控制器采用了隨機(jī)選擇的方法。除此之外三種不同的路由器均采用相同的配置。

在已有的幾種雙向鏈路調(diào)度機(jī)制中，比如文獻(xiàn)[5,8,9]等，它們均采用了直接加寬路由器內(nèi)部數(shù)據(jù)通路的做法，比如加寬輸入緩沖的帶寬，同時(shí)加倍交叉開關(guān)的輸入和輸出端口數(shù)等。一方面，它們使用了比我們的方案更多的硬件資源和硅片面積，另一方面它們所使用的方案與我們的理念不同。比如文獻(xiàn)[9]使用的是切片切分的方法。我們的方案是追求空閑資源的高效利用，并在一定程度上站在全局的角度調(diào)度雙向鏈路的使用。所以，在性能比較方面，我們的方案與之前的方案沒有直接比較的意義。但是，根據(jù)這些論文里面實(shí)驗(yàn)的設(shè)置來測試我們的設(shè)計(jì)發(fā)現(xiàn)，在同等設(shè)置條件下，我們的設(shè)計(jì)性能不低于上述設(shè)計(jì)方案。在實(shí)驗(yàn)中，我們采用了多種不同合成負(fù)載來評(píng)估各種配置網(wǎng)絡(luò)的性能，由于篇幅所限，我們將重點(diǎn)討論uniform、transpose、shuffle 流量模型下網(wǎng)絡(luò)的性能。

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

(1)網(wǎng)絡(luò)吞吐率性能比較。

圖9為4×4和 8×8兩種不同規(guī)模的Mesh網(wǎng)絡(luò)中網(wǎng)絡(luò)性能的評(píng)估結(jié)果。Baseline表示使用單向鏈路的基礎(chǔ)路由器，CbRouter-1fc表示一條快速通道的雙向鏈路路由器，CbRouter-2fc表示擁有兩條快速通道的雙向鏈路路由器。由實(shí)驗(yàn)結(jié)果可以看出，在網(wǎng)絡(luò)資源相同時(shí)，雙向鏈路路由器在uniform流量模式下所獲得的性能提升是三種流量下最少的，卻仍然能夠獲得16.67%(4×4)和10.8%(8×8)左右的性能提升。因?yàn)閡niform流量模式下，節(jié)點(diǎn)向網(wǎng)絡(luò)中任意節(jié)點(diǎn)發(fā)送數(shù)據(jù)包可能性相同，各自輸出主鏈路的空閑狀態(tài)出現(xiàn)概率小，并且網(wǎng)絡(luò)規(guī)模越大雙向鏈路發(fā)揮的余地越少。然而，在大多數(shù)流量模式下雙向鏈路路由器都能夠發(fā)揮良好的性能。比如在transpose和shuffle流量模式下，與基礎(chǔ)路由器相比，8×8 Mesh網(wǎng)絡(luò)中一條快速通道能分別獲得83.3%和73%左右的性能提升，飽和吞吐率差不多是基礎(chǔ)路由器的兩倍。

從實(shí)驗(yàn)數(shù)據(jù)可以看出，雙向鏈路路由器在更大規(guī)模的Mesh網(wǎng)絡(luò)中往往能夠獲得更好的性能，比如，transpose流量下一條快速通道在4×4 Mesh比基礎(chǔ)路由器性能提升65.71%，在8×8 Mesh網(wǎng)絡(luò)中能夠獲得73%的性能提升。這是因?yàn)椋瑪?shù)據(jù)包在更大的網(wǎng)絡(luò)中傳輸將會(huì)獲得更多的機(jī)會(huì)，同時(shí)使用兩條同方向傳送的鏈路，而且越大規(guī)模的網(wǎng)絡(luò)往往能夠使更多的數(shù)據(jù)包使用空閑的輸出主鏈路。這說明雙向鏈路路由器具有良好的可擴(kuò)展性。

同時(shí)，實(shí)驗(yàn)數(shù)據(jù)表明設(shè)置兩條快速通道所獲得的性能提升有限。在最好的shuffle流量模式下，兩條快速通道最多也只能比一條快速通道性能提高8.23% 。因?yàn)樵诙鄶?shù)情況下并不會(huì)出現(xiàn)多個(gè)端口的輸出副鏈路同時(shí)可用的情況。并且由于兩條雙向鏈路路由器的FC控制器需要更長的時(shí)鐘周期來完成FC比較，加上需要更多的資源，導(dǎo)致其并不會(huì)有多大的優(yōu)勢。所以，一條快速通道將是資源效率折衷的最佳選擇。

(2)通道利用率以及實(shí)現(xiàn)代價(jià)分析。

Figure 9 Latency versus injection rate results obtained by running uniform, transpose, shuffle traffics圖9 uniform、transpose、shuffle流量模式下不同注入率與數(shù)據(jù)包延遲的對(duì)比曲線

Figure 10 Comparison of link utilization圖10 鏈路平均利用率對(duì)比

圖10為在4×4的Mesh網(wǎng)絡(luò)中鏈路平均利用率提升對(duì)比結(jié)果。

對(duì)比結(jié)果顯示，在uniform流量模式下通道平均利用率提升最小，只有8.43%，且兩條快速通道和一條快速通道通道平均利用率相差不超過0.3%。在transpose和shuffle流量模式下通道平均利用率提升較大，均能提升18.77%～24.53%不等，這與網(wǎng)絡(luò)性能的提升是一致的，因?yàn)殒溌返母咝Ю猛軌驇砀叩木W(wǎng)絡(luò)吞吐率、更低的數(shù)據(jù)包延遲。

(3)面積功耗開銷分析。

同一般的單向鏈路路由器相比，我們的設(shè)計(jì)需要增加一定的面積功耗開銷，這些開銷主要來自交叉開關(guān)旁路和快速通道仲裁所需要的控制邏輯等所帶來的面積功耗開銷。根據(jù)上文的分析可知，交叉開關(guān)旁路通道中兩個(gè)多路器所需要的面積與功耗開銷一定會(huì)少于已有雙向鏈路調(diào)度機(jī)制所需要的面積功耗開銷，因?yàn)樗鼈兙捎昧思颖督徊骈_關(guān)輸入輸出端口數(shù)量的方法。并且，根據(jù)第3節(jié)的分析可知，我們的雙向鏈路調(diào)度機(jī)制能保證增加的資源處于較高的利用狀態(tài)。分析可知，其他雙向鏈路路由器為每個(gè)輸入輸出端口增加的帶寬資源只有在同時(shí)使用兩條雙向鏈路的時(shí)候才發(fā)揮作用，然而無論在什么情況下，這些增加的帶寬資源最大只能達(dá)到50%的利用率，比如在四端口路由器中兩個(gè)端口輸入和兩個(gè)端口作為輸出的情況。

5 結(jié)束語

本文為鏈路方向動(dòng)態(tài)可調(diào)設(shè)計(jì)了一種新型的調(diào)度算法，并設(shè)計(jì)了對(duì)應(yīng)的新型路由器。該雙向鏈路路由器不是簡單增加原有數(shù)據(jù)通道的帶寬，而是在考慮鏈路資源和實(shí)現(xiàn)代價(jià)的基礎(chǔ)上設(shè)計(jì)了一條叫做快速通道的數(shù)據(jù)旁路，該數(shù)據(jù)通路采用了一種簡單的查詢比較機(jī)制，從而能夠使得數(shù)據(jù)切片只需要一個(gè)時(shí)鐘周期就可以路由通過。同時(shí)，為了支持兩個(gè)切片的同時(shí)讀寫，我們根據(jù)已有的相關(guān)設(shè)計(jì)提出了一種新的輸入緩沖組織結(jié)構(gòu)。綜合流量模式下的模擬結(jié)果顯示，本文所設(shè)計(jì)的雙向鏈路路由器能夠高效利用鏈路資源而獲得較高的性能提升。本文中，我們只在Mesh網(wǎng)絡(luò)上討論了本文所設(shè)計(jì)的方案，但通過適當(dāng)修改該方案也可以應(yīng)用在其他網(wǎng)絡(luò)拓?fù)渲小?/p>

[1] Dally W, Towles B. Principles and practices of interconnection networks[M]. Burlington:Morgan Kaufmann Publishers Inc, 2003.

[2] Cho M H, Lis M, Shim K S, et al. Oblivious routing in on-chip bandwidth-adaptive networks[C]∥Proc of the 2009 18th International Conference on Parallel Architectures and Compilation Techniques, 2009:181-190.

[3] Zhen Z, Greiner A, Taktak S. A reconfigurable routing algorithm for a fault-tolerant 2D-Mesh Network-on-Chip[C]∥Proc of the 45th Conference on Design Automation, 2008:441-446.

[4] Chen L,Pinkston T M.Worm-bubble flow control[C]∥Proc of High Performance Computer Architecture, 2013:366-377.

[5] Qian Zhi-liang, Ying Fei Teh, Chi-Ying Tsui, et al. A flit-level speedup scheme for network-on-chip using self-reconfigurable bi-directional channels[C]∥Proc of Design, Automation Test in Europe Conference, 2012:1295-1300.

[6] Mishra A K, Vijaykrishnan N, Das C R. A case for heterogeneous on-chip interconnects for CMPs[C]∥Proc of the 38th Annual International Symposium on Computer Architecture, 2011:389-400.

[7] Jiang N,Becker D U,Michelogiannakis G,et al. A detailed and flexible cycle-accurate network-on-chip simulator[C]∥Proc of Performance Analysis of Systems and Software, 2013:86-96.

[8] Lan Ying-Cherng,Lin Hsiao-An,Shih-Hsin Lo,et al. BiNoC:A bidirectional NoC architecture with dynamic self-reconfigurable channel[C]∥Proc of the 3rd IEEE/ACM International Symposium on Networks on Chip, 2009:266-275.

[9] Hesse R, Nicholls J, Jerger N. Fine-grained bandwidth adaptivity in networks-on-chip using bidirectional channels[C]∥Proc of the 6th IEEE/ACM International Symposium on Networks on Chip, 2012:132-141.

[10] Moscibroda T, Mutlu O. A case for bufferless routing in on-chip networks[C]∥Proc of the 36th Annual International Symposium on Computer Architecture, 2009:196-207.

[11] Koibuchi M, Matsutani H, Amano H, et al. A lightweight fault-tolerant mechanism for network-on-chip[C]∥Proc of the 2nd ACM/IEEE International Symposium on Networks-on-Chip, 2008:13-22.

[12] Faruque A, Ebi M A T, Henkel J. Configurable links for runtime adaptive on-chip communication[C]∥Proc of Design, Automation Test in Europe Conference, 2009:256-261.

[13] Kim J, DallyW J, Abts D. Flattened butterfly：A cost-efficient topology for high-radix networks[C]∥Proc of the 34th Annual International Symposium on Computer Architecture, 2007:126-137．

[14] Dally W J, Towles B. Route packets, not wires:On-chipinterconnection networks[C]∥Proc of the 38th Conference on Design Automation, 2001:684-689.

[15] Michelogiannakis G,Balfour J,Dally W.Elastic-buffer flow control for on-chip networks[C]∥Proc of the High Performance Computer Architecture, 2009:151-162.