片上網(wǎng)絡(luò)路由器的交叉開(kāi)關(guān)設(shè)計(jì)實(shí)現(xiàn)

1、片上網(wǎng)絡(luò)路由器的交叉開(kāi)關(guān)設(shè)計(jì)實(shí)現(xiàn)摘要 :交叉開(kāi)關(guān)是片上網(wǎng)絡(luò)路由器的關(guān)鍵部分。 交叉開(kāi) 關(guān)的設(shè)計(jì)可以采用三態(tài)觸發(fā)器或多路復(fù)用器實(shí)現(xiàn)。本文針對(duì) 幾種不同形式的交叉開(kāi)關(guān)實(shí)現(xiàn)方案 ,比較了其面積和功耗的 開(kāi)銷 ,同時(shí)設(shè)計(jì)了基于 iSLIP 算法的交叉開(kāi)關(guān)調(diào)度機(jī)制。 通過(guò) 基本邏輯門搭建的多路復(fù)用器實(shí)現(xiàn)的交叉開(kāi)關(guān)相比于采用 三態(tài)門實(shí)現(xiàn)的交叉開(kāi)關(guān) ,在功耗、面積上有較大優(yōu)勢(shì)。采用 iSLIP 算法實(shí)現(xiàn)的片上網(wǎng)絡(luò)交叉開(kāi)關(guān) ,具有最高的工作頻率上 限。關(guān)鍵字 :片上網(wǎng)絡(luò) ,交叉開(kāi)關(guān) ,分布式多路復(fù)用器 ,iSLIP 算 法中圖分類號(hào) :TN919 文獻(xiàn)標(biāo)識(shí)碼 :AThe design and implemen

2、tation of crossbar switches of network-on-ship routersFU Zhi-zhou,LING Xiang(National Key Laboratory of Science and Technology onCommunications of UESTC Chengdu,611731,China)Abstract: The crossbar switch is one of the most important components in the router of network-on-chips. The crossbar switches

3、 could be design based on the tristate gates, or the multiplexers. This paperintroduces different ways to implement the crossbar switch, and compares the power consumption and area cost for these implementations. Furthermore, we implement the virtual channel scheduling mechanism of crossbar based on

4、 iSLIP algorithm. The crossbar which is implemented by multiplexer have more advance in power consumption and area cost than the tri-state-gate-based crossbar. The NoC crossbar implemented based on iSLIP algorithm has the maximum frequency than others.Key words: network-on-chips, crossbar switch, di

5、stributed multiplexer, iSLIP algorithm1 引言片上網(wǎng)絡(luò) (NoC) 中路由器的設(shè)計(jì)結(jié)構(gòu)中 ,交叉開(kāi)關(guān) (crossbar switch) 是關(guān)鍵的核心模塊 ,交叉開(kāi)關(guān)是在仲裁器以 及控制模塊的協(xié)同操作下對(duì)來(lái)自不同輸入端口數(shù)據(jù)選擇相 應(yīng)的輸出端口方向。 片上網(wǎng)絡(luò)路由器中 ,輸入端口控制器從數(shù) 據(jù)包頭部中提取出路由信息 ,通過(guò)路由查找表獲得輸出端口 信息 ,然后反饋給仲裁器 ,當(dāng)路由和仲裁確定以后 ,交叉開(kāi)關(guān)將 數(shù)據(jù)包中的一個(gè)數(shù)據(jù)微片從輸入端口傳送到輸出端口。交叉 開(kāi)關(guān)的帶寬、功耗和面積等在很大程度上影響片上網(wǎng)絡(luò)路由 器的性能 ,交叉開(kāi)關(guān)需要具有高速性能并提供

6、有效的競(jìng)爭(zhēng)解 決方案 2 。文獻(xiàn)3中介紹了一種稱為 FLEXBR 的 Crossbar Switch 路由結(jié)構(gòu)。 借鑒文中的思路 ,我們這里給出了一種交叉節(jié)點(diǎn)式 的Crossbar。文獻(xiàn)4中提出的分布式 Crossbar不能夠保證輸 入端口的公平性 ,我們?cè)谶@里也設(shè)計(jì)實(shí)現(xiàn)了以多路復(fù)用器作 為基本模塊的交叉開(kāi)關(guān)。此外,本文利用文獻(xiàn) 1 中提出的iSLIP算法設(shè)計(jì)了符合片上網(wǎng)絡(luò)的路由器的Crossbar結(jié)構(gòu),在輸入端口的和輸出端口分別利用了仲裁器,確保了數(shù)據(jù)包傳輸過(guò)程中的公平性。本文對(duì)三種不同結(jié)構(gòu)的crossbar進(jìn)行設(shè)計(jì)實(shí)現(xiàn)，同時(shí)分析了三種結(jié)構(gòu)的性能 , 包括工作頻率、資源開(kāi)銷等。2 交叉節(jié)點(diǎn)式

7、交叉開(kāi)關(guān)在參考文獻(xiàn)5中給出了傳統(tǒng)的數(shù)據(jù)包交換Crossbar結(jié)構(gòu),借鑒這種結(jié)構(gòu)我們?cè)O(shè)計(jì)了基于交叉節(jié)點(diǎn)式的交叉開(kāi)關(guān),這種結(jié)構(gòu)中利用了三態(tài)門控制數(shù)據(jù)通路的連通性。在圖 1 中給出了基于交叉節(jié)點(diǎn)方式的片上網(wǎng)絡(luò)crossbar輸入節(jié)點(diǎn)和輸出節(jié)點(diǎn)通過(guò)在交叉結(jié)點(diǎn)處建立互連而實(shí)現(xiàn)選擇性的連通。圖 1 中給出的是5X 5的基于交叉節(jié)點(diǎn)的交叉開(kāi)關(guān)。這里有5個(gè)輸入端口和 5個(gè)輸出端口 ,對(duì)應(yīng)著 5條輸入線和 5條輸出線 , 在每個(gè)交叉節(jié)點(diǎn)處 ,輸入和輸出進(jìn)行互連。這時(shí)采用的數(shù)據(jù)交換方式為交叉開(kāi)關(guān)方式 ,數(shù)據(jù)從輸入端口進(jìn)入后 ,通過(guò)交換結(jié) 構(gòu)的調(diào)度 ,從輸出端口輸出。交叉節(jié)點(diǎn)交換器將n個(gè)輸入端口和m個(gè)輸出端口直接進(jìn)

8、 行互連 ,而無(wú)需中間過(guò)程。 多數(shù) crossbar 是成正方形的 ,即 m = n;也有crossbar的m工n。交叉節(jié)點(diǎn)由三態(tài)門決定 ，而三態(tài)門 的控制電平可以由相應(yīng)的仲裁器或控制邏輯決定,一旦交叉節(jié)點(diǎn)處于激活狀態(tài)時(shí) ,輸入便連接到相應(yīng)的輸出端口,例如圖1 中虛線框處的 cross point 處于激活狀態(tài)時(shí) ,由 East 端口輸入 的數(shù)據(jù)便可送出到 North 端口。圖 1 中三態(tài)門的控制信號(hào)構(gòu)成一個(gè)控制矩陣 ,矩陣中每 一列元素狀態(tài)可以采用獨(dú)熱碼進(jìn)行編碼。由于獨(dú)熱碼在硬件 實(shí)現(xiàn)時(shí)相比較其他的編碼方式能夠減少設(shè)計(jì)中的資源開(kāi)銷 , 可以減少控制各個(gè)端口動(dòng)態(tài)方向所使用的寄存器數(shù)量。經(jīng)過(guò) 仲

9、裁以后得到控制矩陣中的獨(dú)熱碼 ,改變數(shù)據(jù)流的傳輸順序 , 將突發(fā)錯(cuò)誤隨機(jī)化 ,提高糾錯(cuò)編碼的有效性。 當(dāng)三態(tài)門的控制 信號(hào)為高時(shí)選擇相應(yīng)輸入端口的數(shù)據(jù)輸出,否則輸出為高阻狀態(tài)。如果某一列元素中出現(xiàn)多個(gè)高電平,那么在輸出線中會(huì)出現(xiàn)對(duì)總線競(jìng)爭(zhēng)的情況 ,即多個(gè)輸入端口爭(zhēng)用一個(gè)輸入端口 ,這時(shí)可考慮在相應(yīng)輸入端口增加緩沖單元,依據(jù)仲裁機(jī)制延遲數(shù)據(jù)傳向輸出端口。3 基于多路復(fù)用器的交叉開(kāi)關(guān)在采用多路復(fù)用器設(shè)計(jì) crossbar 時(shí),可以采用基本的邏輯 門來(lái)設(shè)計(jì)輸入端口的選通電路,如圖 2 中,5 端口的 crossbar 每個(gè)端口的選通電路采用基本的邏輯與、或門實(shí)現(xiàn)。對(duì)輸入的 數(shù)據(jù)采用并行處理，提高數(shù)據(jù)

10、的吞吐量。Input(0:4)為來(lái)自5個(gè) 不同輸入端口的串行數(shù)據(jù)，經(jīng)過(guò)選通電路，由Select的選通信 號(hào)作用下根據(jù)路由查找表 ,從數(shù)據(jù)頭部獲得目的地址將數(shù)據(jù) 送達(dá)相應(yīng)輸出端口。 Select 選通信號(hào)由調(diào)度器以及 Round-robin 仲裁器決定。 此設(shè)計(jì)將串并轉(zhuǎn)換電路與選通電路 結(jié)合起來(lái) ,減少數(shù)據(jù)的處理以及鏈路的傳輸時(shí)間。串行數(shù)據(jù)中每個(gè)端口經(jīng)過(guò)與門的選通 ,再經(jīng)過(guò)或門進(jìn)行或運(yùn)算便可傳遞 到輸出端口。 Select選通信號(hào)在 Roun-robin的控制下可以靈 活改變各個(gè)輸入端口的數(shù)據(jù)的優(yōu)先權(quán) ,在調(diào)度器的控制下改 變數(shù)據(jù)流的傳遞方向。圖2顯示的是以基本邏輯門為單元搭建的crossbar

11、模塊,設(shè)計(jì)中也可以采用多路復(fù)用器的模塊實(shí)現(xiàn)不同端口的選通 ; 圖3描述了基于多路復(fù)用器的crossbar,由控制信號(hào)控制多路復(fù)用器的選通 ,實(shí)現(xiàn)相應(yīng)端口信號(hào)的選通 ,為每個(gè)多路復(fù)用的輸入端口信號(hào)選通與相應(yīng)的輸出端口連接,從而建立 switch的互連。本文為全文原貌 未安裝 PDF 瀏覽器用戶請(qǐng)先下載安裝 原 版全文 在試驗(yàn)結(jié)果的分析中表明 :這種同步 多路復(fù)用器形式的交叉開(kāi)關(guān)適用于較低操作頻率的路由器 設(shè)計(jì)方案中。4 基于 i-SLIP 算法的交叉開(kāi)關(guān)設(shè)計(jì)i-SLIP 算法使用多次迭代找出路徑以盡可能多地利用輸 入和輸出端口 ,直到再也找不到相匹配的輸入和輸出端口。 在 設(shè)計(jì)中我們采用了 5端

12、口的路由器 ,并且每一端口有 4 個(gè)虛通 道 (virtual channel), 這樣一個(gè)路由器共有 20 個(gè)虛通道 ,每個(gè)虛 通道都能夠接收數(shù)據(jù)包并通過(guò)路由器傳送。當(dāng)有多個(gè)虛通道 請(qǐng)求同一輸出信道時(shí) ,我們需要有虛擬信道的分配機(jī)制以解 決擁塞和能夠保證完整的數(shù)據(jù)包傳輸過(guò)程的分配問(wèn)題。虛擬信道的分配問(wèn)題可以看作輸入 /輸出之間的匹配問(wèn) 題,并且分為 3 個(gè)階段 ,請(qǐng)求、授予、接受。為了更容易解釋 我們仲裁器的優(yōu)先權(quán)的定義和機(jī)制。所有的輸入輸出在初始 時(shí)刻都是不匹配的 ,在每次迭代的三個(gè)階段中 ,輸入和輸出之 間的匹配以并行的方式進(jìn)行 ,三個(gè)階段的過(guò)程如下 :(1) 請(qǐng)求階段 如圖4(a)，每

13、個(gè)有待發(fā)送數(shù)據(jù)的未能匹配的 輸入端口向輸出端口發(fā)出請(qǐng)求 ;在圖4中(b)授予階段，每個(gè)未匹配的輸出端口依據(jù)輪 詢仲裁調(diào)度中的優(yōu)先權(quán)指針 ,選擇下一個(gè)請(qǐng)求輸入端口。 有兩 個(gè)輸入虛擬信道分別請(qǐng)求輸出虛擬信道 2和 4(1,3請(qǐng)求 2,3,4 請(qǐng)求4),由于當(dāng)前仲裁器的優(yōu)先權(quán)指針g2=1,輸出端口 2授予給輸入端口 1,然后仲裁器的優(yōu)先權(quán)需要更新。接受階段 如圖4中(c)所示，每個(gè)輸出端口選擇至多 一個(gè)輸出端口 ,由于輸入端口 1 中優(yōu)先權(quán)指針 =1,將輸入端口 1 接受輸出端口 1,當(dāng)仲裁完成后 ,輸入和輸出之間建立了匹配 的關(guān)系 , 同時(shí)更新仲裁優(yōu)先權(quán)。利用 iSLIP 算法,因?yàn)樵O(shè)計(jì)的片上網(wǎng)

14、絡(luò)路由器是五個(gè)端口 并且假設(shè)每個(gè)端口的虛擬信道數(shù)量是 4,我們給出一種數(shù)據(jù)的 請(qǐng)求傳送方式 :在這里我們假設(shè)每個(gè)物理信道上的接受和授 予仲裁器的均采用輪詢仲裁器,并且設(shè)定優(yōu)先權(quán)為1234,IIIIIIIV ,輸入和輸出端口的仲裁器的初始優(yōu)先權(quán)均如此。在請(qǐng)求階段(圖5),East輸入端口的虛擬信道1、2、3、4分別請(qǐng)求 West輸出端口的l,IV信道、North端口的II信道、 south端口的IV信道，其余各個(gè)物理信道上的虛擬信道請(qǐng)求類 似。在授予階段 ,根據(jù)輸出端口授予仲裁器的初始優(yōu)先權(quán) ,將輸出端口的物理信道中虛擬信道與輸入端口中的虛擬信道 建立互連關(guān)系。 由于有三個(gè)輸入虛擬信道請(qǐng)求輸出端

15、口 West 的 I、II 、IV 虛擬信道 ,這樣依據(jù)輸出物理信道中授予仲裁器 的優(yōu)先權(quán) ,將虛擬信道 I 授予給 Ei 的輸入虛擬信道 1。其他物 理端口信道按照同樣的道理操作。在接受階段 (圖 7),物理信道 Ei 的輸入虛擬信道 1 接受物 理信道 Wo 的虛擬信道 I 的授予。而在物理信道 Wi 中兩個(gè) 虛擬信道 2、 3 都接受到輸出虛擬信道授予信號(hào)反饋,因而依據(jù)接受仲裁器(accept arbiter)的優(yōu)先權(quán)，虛擬信道2的優(yōu)先權(quán) 高，而將輸入2與South輸出II相連。5 仿真結(jié)果以及數(shù)據(jù)分析我們分析并且比較了幾種不同形式的crossbar設(shè)計(jì)，對(duì)基于三態(tài)門實(shí)現(xiàn)的 crossb

16、ar、多路復(fù)用器實(shí)現(xiàn)的 crossbar、以及 iSLIP算法實(shí)現(xiàn)時(shí)5輸入端口的 Crossbar在ASIC面積,cells 數(shù)量和時(shí)鐘頻率等幾個(gè)方面進(jìn)行的分析、驗(yàn)證。下面就幾種 方案進(jìn)行分析比較 :經(jīng)過(guò) Design Compiler 綜合,比較三種不同的實(shí)現(xiàn)方案 , 基于多路復(fù)用器、基于三態(tài)門和采用 iSLIP 算法實(shí)現(xiàn)的 Crossbar使用的cells數(shù)量相接近，但采用iSLIP算法時(shí)占用的 面積較大，而利用iSLIP算法實(shí)現(xiàn)的Crossbar時(shí)鐘頻率相較前 兩者更要高一些。圖中給出的 iSLIP 算法的數(shù)據(jù)是在每個(gè)端口數(shù)量虛擬信道數(shù)量為 5 時(shí)的情況。如果在 FPGA 上實(shí)現(xiàn) ,相比

17、較而言 ,使用 iSLIP 算法實(shí)現(xiàn)片 上網(wǎng)絡(luò)互連時(shí) ,占用的資源相比于另外兩種方式要多一些。此外基于 iSLIP 算法時(shí)考慮到各個(gè)物理信道中的虛擬信道的數(shù) 量,并且基于輪詢調(diào)度算法的基礎(chǔ)增強(qiáng)了各個(gè)虛擬信道的公 平性。接下來(lái)我們分析使用 iSLIP 算法時(shí) ,虛擬信道數(shù)量變化時(shí) 的 Crossbar 的性能以及功耗情況。在采用三維片上網(wǎng)絡(luò)拓?fù)?結(jié)構(gòu)或者 butterfly 拓?fù)浣Y(jié)構(gòu)時(shí) ,每個(gè)端口需要更多的虛通道。 當(dāng)每個(gè)端口虛信道數(shù)為5 時(shí) ,可以達(dá)到的最大工作頻率為139.104MHz; 當(dāng)每個(gè)端口虛信道數(shù)量為 8 時(shí),最大工作頻率為 116.844MHz, 工作頻率下降 19.05% 。當(dāng)

18、端口虛信道數(shù)為 5 時(shí),交叉開(kāi)關(guān)功耗303mW,端口虛信道數(shù)為8的功耗317mW, 功耗略有增加。 仿真表明采用 iSLIP 算法時(shí) ,隨著各端口虛擬 信道數(shù)量的增加 ,硬件實(shí)現(xiàn)的最高時(shí)鐘頻率下降 ,資源開(kāi)銷增 加,詳見(jiàn)圖 9。如果采用ASIC實(shí)現(xiàn)，選用SMIC 0.18um工藝庫(kù)，DC綜 合后得到面積以及功耗結(jié)果見(jiàn)圖1 0。由圖可見(jiàn) ,隨虛擬信道數(shù)量增加 ,基于 iSLIP 實(shí)現(xiàn)的功耗、面積開(kāi)銷增加。在仲裁的設(shè)計(jì)實(shí)現(xiàn)部分 ,我們可以采用輪詢仲裁器 ,也 可以采用 Matrix 形式的仲裁器來(lái)進(jìn)行實(shí)現(xiàn) ,本文只討論了簡(jiǎn) 單輪詢仲裁機(jī)制。 在 i-SLIP 算法中輸入端口的優(yōu)先權(quán)更新與輸出端口的

19、優(yōu)先權(quán)更新是相互獨(dú)立的 ,提高了傳輸過(guò)程中 VC 調(diào)度的公平性。6 總結(jié)本論文討論了片上網(wǎng)絡(luò)路由器中的核心部分 crossbar 的 實(shí)現(xiàn)結(jié)構(gòu) ,并且采用 iSLIP 算法對(duì)片上網(wǎng)絡(luò)交叉開(kāi)關(guān)進(jìn)行了設(shè) 計(jì)實(shí)現(xiàn)。綜合結(jié)果表明 ,采用 iSLIP 算法實(shí)現(xiàn)的 crossbar 占用 了較大的面積 ,但相比于另外兩種實(shí)現(xiàn)方式 ,交換處理速度更 快,并且在輸入端采用的輪詢仲裁具有更好的公平性。此外隨著虛擬信道端口數(shù)目的增加 ,資源開(kāi)銷增加的同時(shí)工作時(shí)鐘 有所下降。本論文中提到的基于 iSLIP 算法設(shè)計(jì) Crossbar 時(shí) ,在輸 入、輸出端采用的是基于輪詢仲裁的 Round-robin 方式。還 可

20、以采用具有固定優(yōu)先權(quán)的仲裁 (fixed-priority arbitration) 或 者 matrix-arbiter 等不同的仲裁方式進(jìn)行設(shè)計(jì)實(shí)現(xiàn) , 這些將在 未來(lái)的研究中分析。 同時(shí) ,輸入端口虛擬信道的分布問(wèn)題也是 需要進(jìn)一步深入研究。參考文獻(xiàn)1 Nick McKeown.The iSLIP Scheduling Algorithm for Input-Queued Switches IEEE/ACM TRANSACTIONS ONNETWORKING, VOL. 7, NO. 2, APRIL 1999,188-2002 Sundar Iyer and Nick McKeown.Techniques for Fast Shared Memory Switches, STANFORD HPNG TECHNICAL REPORT TR01-HPNG-0815013 Jacob Changy_ , Srivaths Raviz, and Anand Raghunathanz FLEXBAR: A crossbar switching fabric with improved performance and utilization4 Kangmin Lee, Se-Joong Lee, and Hoi-Jun Yo0,A