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

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

1 引言

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

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

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

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

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

2 研究背景

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

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

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

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

3 詳細設計

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

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

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

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

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

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

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

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

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

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)絡路由器四級流水線：RC(路由計算)、VA(輸出虛擬通道分配)、SA(開關(guān)分配)、ST(開關(guān)通過)、LT(鏈路傳輸)

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

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

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

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

3.3 快速通道

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

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

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

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

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

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

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

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

Figure 7 Fastchannel operation timing sequence圖7 快速通道操作時序

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

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

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

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

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

4 性能評估

4.1 實驗設置

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

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

4.2 實驗結(jié)果

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

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

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

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

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

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

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

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

對比結(jié)果顯示，在uniform流量模式下通道平均利用率提升最小，只有8.43%，且兩條快速通道和一條快速通道通道平均利用率相差不超過0.3%。在transpose和shuffle流量模式下通道平均利用率提升較大，均能提升18.77%～24.53%不等，這與網(wǎng)絡性能的提升是一致的，因為鏈路的更高效利用往往能夠帶來更高的網(wǎng)絡吞吐率、更低的數(shù)據(jù)包延遲。

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

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

5 結(jié)束語

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

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