摘  要： 針對陣列處理單元之間互連傳輸擁塞的問題，設(shè)計了一種在二維結(jié)構(gòu)中互連的虛通道路由器模型,。采用改進(jìn)的自適應(yīng)XY路由算法,，智能地分配虛通道空閑資源，從邏輯上減少擁塞和等待時間,，多路選擇器交叉開關(guān)完成數(shù)據(jù)傳輸,。通過ASIC設(shè)計，完成虛通道路由器硬件電路,，應(yīng)用Modesim工具進(jìn)行仿真,，達(dá)到網(wǎng)絡(luò)互連傳輸?shù)哪康摹?/p>

　　關(guān)鍵詞： 網(wǎng)絡(luò)互連；虛通道路由器,；路由算法,；ASIC設(shè)計

　　隨著SoC（System-on-Chip）技術(shù)研究的深入，IP核數(shù)不斷增加,，以總線結(jié)構(gòu)為通信技術(shù)的系統(tǒng)芯片面臨著功耗,、延遲、可靠性等方面的問題[1],。單芯片多處理器（CMP）采用共享總線方式通信,，也同樣面臨著帶寬限制、信號延遲等問題。一些研究機(jī)構(gòu)借鑒網(wǎng)絡(luò)通信中的思路,，提出基于網(wǎng)絡(luò)互連的NoC（Network-on-Chip）系統(tǒng)芯片架構(gòu),，其優(yōu)勢就是降低SoC的功耗和制造費(fèi)用、提高性能等,。

　　當(dāng)前，以網(wǎng)絡(luò)互連為基礎(chǔ)的高性能的陣列處理器系統(tǒng)芯片成為人們研究的熱點,。根據(jù)計算機(jī)體系結(jié)構(gòu)的發(fā)展,，共有10種體系結(jié)構(gòu)模型[2]。它們以指令流,、數(shù)據(jù)流與構(gòu)令流計算為基礎(chǔ),，完成算法到體系結(jié)構(gòu)的時間、空間映射,。一種新型的基于指令流的統(tǒng)一體系結(jié)構(gòu)模型Unified-ISA[2]被提出,，使得所有的電路設(shè)計問題統(tǒng)一到基于指令流計算的SIMD PE陣列上的程序設(shè)計問題。SIMD PE陣列中處理元PE之間數(shù)據(jù)傳輸?shù)膯栴}正是網(wǎng)絡(luò)互連中路由傳輸?shù)膯栴},。

1 2D Mesh拓?fù)浣Y(jié)構(gòu)基本原理

　　NoC內(nèi)集成了大量的資源IP核,，拓?fù)浣Y(jié)構(gòu)解決的是互連網(wǎng)絡(luò)中各個資源IP節(jié)點的分布與銜接。按照不同的系統(tǒng)性能需求,，可以有不同的拓?fù)浣Y(jié)構(gòu)解決方案,，如規(guī)則的2D Mesh網(wǎng)狀結(jié)構(gòu)、蜂窩結(jié)構(gòu),、樹狀結(jié)構(gòu)等,。

　　2D Mesh是NoC互連網(wǎng)絡(luò)中最簡單、最直觀,、應(yīng)用最廣的一種拓?fù)浣Y(jié)構(gòu),，如圖1所示的4×4網(wǎng)格，除了邊界節(jié)點外,，每個節(jié)點都連接著1個IP核單元和4個臨近的路由單元,，每個節(jié)點對應(yīng)一個物理坐標(biāo)編號（x，y）,，每個節(jié)點能夠?qū)?shù)據(jù)從源地址傳送到目的地址（一個或多個）,。IP核可以是處理器核、DSP核,、專用硬件資源或各種硬件資源的集合等,。

　　在NoC網(wǎng)絡(luò)中完成數(shù)據(jù)傳輸除了拓?fù)浣Y(jié)構(gòu)元素外，還有另一個重要元素——路由算法[1,，3-5],。路由算法解決的是數(shù)據(jù)傳輸過程中找到最佳的傳輸路徑，而簡單、靈活,、健壯,、低耗、穩(wěn)定的算法,，正是提高傳輸性能的關(guān)鍵,。

　　現(xiàn)實中路由算法有很多，每種算法對路由和資源的影響各不相同,，具體分為無關(guān)路由（oblivious）和自適應(yīng)路由（adaptive）,。無關(guān)路由分為確定性XY路由和隨機(jī)路由，自適應(yīng)路由有偽自適應(yīng)XY路由,、轉(zhuǎn)彎模型,、DyXY路由等。

　　本設(shè)計中的算法結(jié)合了轉(zhuǎn)彎,、XY-XY,、DyXY等路由算法的思想，解決了數(shù)據(jù)包傳輸中的擁塞阻塞問題,。從XY路由進(jìn)行演化,，用目的地址與當(dāng)前網(wǎng)絡(luò)物理地址進(jìn)行比較，遍歷所有的可能轉(zhuǎn)向,。例如目的地址為（X,，Y），當(dāng)前網(wǎng)絡(luò)地址為（X0,，Y0）,，兩者比較就有9種情況。根據(jù)每條數(shù)據(jù)鏈路的當(dāng)前傳輸狀況,，可以調(diào)整數(shù)據(jù)的方向,，比如向右方向數(shù)據(jù)較多時，如果目的地址是在右下方向,，則可以先調(diào)整方向轉(zhuǎn)彎向下走,，以減少擁塞。在具體設(shè)計過程中數(shù)據(jù)傳輸方向不會往回走,，只會朝著目標(biāo)前進(jìn),，可以避免回環(huán)死鎖現(xiàn)象。另外在路由邏輯中還可以仲裁均衡每個方向的平等性,。

2 虛通道路由器總體設(shè)計模型

　　虛通道路由器軟核是應(yīng)用于片上網(wǎng)絡(luò)（NoC）的一個包交換型路由器,，是NoC的重要基礎(chǔ)部件。其體系結(jié)構(gòu)框圖如圖2所示,。

　　5個相同的端口輸入模塊（Input）分別為東,、南、西、北4個方向和一個IP核方向,，每個端口有多個虛通道,，每個虛通道由不同深度的緩存模塊構(gòu)成，用同步FIFO或異步FIFO實現(xiàn),。5個緩存結(jié)構(gòu)設(shè)計相同,，便于復(fù)用。2D Mesh結(jié)構(gòu)中一個路由的輸出方向最多為4個（不會回頭）,，所以虛通道數(shù)[6]可以為4,。

　　虛通道分配器（Vc_allactor）為路由邏輯中的主要部分，是給輸入緩存中的數(shù)據(jù)分配空閑的數(shù)據(jù)信道,，根據(jù)路由算法選擇輸出方向,，提供信號給交叉開關(guān)模塊,。由于每個方向都有4個虛通道,，多個方向向同一方向傳送數(shù)據(jù)時能夠充分傳輸，減少擁塞過程中的等待時間,，增加吞吐量,。但當(dāng)同一方向的數(shù)據(jù)來源多于4個時，則需要交換分配器來控制,，可以根據(jù)優(yōu)先級或其他策略實現(xiàn),。

　　交叉開關(guān)模塊（Crossbar）根據(jù)路由邏輯中的方向選擇，完成數(shù)據(jù)的最后輸出,。

3 路由器模塊化設(shè)計

　　為簡化設(shè)計,，設(shè)計中每個方向的虛通道數(shù)為1，數(shù)據(jù)包packet結(jié)構(gòu)由包頭數(shù)據(jù)header和包負(fù)載數(shù)據(jù)payload組成,。設(shè)計中采用16 bit寬度的包數(shù)據(jù),，在一定需求的情況下可以進(jìn)行擴(kuò)展。有4 bit控制信息,，1 bit標(biāo)志位,，3 bit包尺寸；6 bit源地址信息,；6 bit目標(biāo)地址信息,，高3位為X方向地址，低3位為Y方向地址,。中間片flit都是16 bit數(shù)據(jù)的包負(fù)載,。數(shù)據(jù)格式如圖3所示。

　　根據(jù)整個路由節(jié)點的數(shù)據(jù)流和控制流兩個方向,，將設(shè)計分為3大模塊：輸入緩存模塊,、邏輯控制模塊和交叉開關(guān)模塊。數(shù)據(jù)從輸入緩存中流入，經(jīng)過控制模塊分配處輸出方向,，交叉開關(guān)根據(jù)方向選擇緩存中的數(shù)據(jù)輸出,。

　　3.1 輸入緩存模塊（FIFO）

　　路由傳輸中，把整個消息分為若干個數(shù)據(jù)包,，數(shù)據(jù)包存儲在虛通道緩存中,。

　　每個方向的輸入模塊都一樣。以本地路由方向W緩存為例,，如圖4所示,，采用ASM有限狀態(tài)機(jī)實現(xiàn)。類似于IP網(wǎng)絡(luò)傳輸中的握手機(jī)制協(xié)議,，請求與應(yīng)答,。虛通道緩存中只有在沒數(shù)據(jù)時才能接收數(shù)據(jù)，只有在目的緩存（下一級虛通道）準(zhǔn)備好時才能輸出數(shù)據(jù),。內(nèi)部虛通道與路由邏輯之間也存在握手機(jī)制,，只有在請求發(fā)送信號得到確認(rèn)時才發(fā)送數(shù)據(jù)包頭數(shù)據(jù)，否則等待,。

　　由于包尺寸大小決定了FIFO的深度,，并且在一次數(shù)據(jù)發(fā)送完畢后清除數(shù)據(jù)，釋放緩存空間,，因此不存在讀空寫滿的現(xiàn)象,，而且讀寫雙方在時間上不會沖突。

　　3.2 路由邏輯控制模塊（Routing Logic）

　　算法邏輯控制模塊的主要任務(wù)是對數(shù)據(jù)包的輸出方向進(jìn)行分配控制,?？煞譃?個小部分：包頭數(shù)據(jù)譯碼分析、輸出方向預(yù)處理和輪詢仲裁輸出方向,。

　　算法實現(xiàn)大致步驟如下（*為w,、s、e,、n,、ip的略寫，下同）：

　?。?）當(dāng)5個方向有傳輸請求syn_*,，并行確認(rèn)來自5個方向的發(fā)送請求ack_*；

　?。?）接收5個方向的包頭目標(biāo)地址數(shù)據(jù)data_head_*[5：0],；

　　（3）依據(jù)算法,，目標(biāo)地址與本地實際地址（X0,，Y0）進(jìn)行比較,，遍歷所有可能的輸出使能方向，如圖5所示,，判斷得到各種情況的輸出使能列表*_en_list=={*_en_w,，*_en_s，*_en_e,，*_en_n,，*_en_ip}。當(dāng)接收到清除信號clear時,，使能列表初始化,。在數(shù)據(jù)包沒有到達(dá)目標(biāo)節(jié)點時，方向使能列表中有2個位為1,，因此這里可以實現(xiàn)下一步的阻塞轉(zhuǎn)彎減少擁塞,。使能列表只有到達(dá)目標(biāo)地址時，才只有一個位為1,。

　?。?）根據(jù)使能列表（*_en_list）和本地路由所有路徑的忙碌狀態(tài)（w_busy_*，s_busy_*,，e_busy_*,，n_busy_*,，ip_busy_*）進(jìn)行自適應(yīng)方向調(diào)整,，忙狀態(tài)標(biāo)志來自仲裁部分，用來判斷是否方向轉(zhuǎn)彎操作,。在空閑狀態(tài)下用W>S>E>N>IP的優(yōu)先規(guī)則得到預(yù)期的輸出方向w_to_*,，s_to_*，e_to_*,，n_to_*,，ip_to_*，匯總得到初步輸出方向to_*={w_to_*,，s_to_*,，e_to_*，n_to_*,，ip_to_*},。這里，會出現(xiàn)多個方向同時向同一個方向發(fā)出使能的情況,，將進(jìn)入下一步輪詢仲裁,。如圖6所示的W方向的輸出使能狀態(tài)，使能列表中有2個位為1,。首先判斷路徑是否被占用,，即是否有忙信號,，當(dāng)有busy信號時考慮轉(zhuǎn)彎調(diào)整，當(dāng)2個使能方向路徑都被占用時,，只能等待路徑的釋放,，這里方向使能列表一直都在?？臻e狀態(tài)下根據(jù)優(yōu)先級W>S>E>N>IP,，W向使能方向發(fā)出預(yù)期的輸出使能w_to_*。

　?。?）最后進(jìn)入輪詢仲裁模塊[7],，沒有沖突的情況下可順利得到最終的控制方向ctrl_*和路徑忙信號*_busy_*，有沖突時根據(jù)輪詢優(yōu)先級產(chǎn)生最后的輸出方向控制信息,。在最高優(yōu)先級傳輸完數(shù)據(jù)時進(jìn)入下一個輪詢,，每一個方向都有公平輪詢的機(jī)會，能夠避免死鎖和長時間等待的情況,。圖7展示的是仲裁輸出示意圖,，當(dāng)前狀態(tài)優(yōu)先級為W>S>E>N>IP，下一個狀態(tài)就為S>E>N>IP>W,。

　?。?）當(dāng)清除信號來臨時，復(fù)位該方向的一切控制信息,，如上面的輸出使能方向,、預(yù)處理輸出方向和最終的輸出控制方向。至此控制模塊完成了工作,。

　　3.3 交叉開關(guān)輸出模塊（crossbar）

　　交叉開關(guān)crossbar[8],，實現(xiàn)與下一級的高效通信，也是NoC系統(tǒng)中的一個關(guān)鍵技術(shù),，來獲取更高的性能和效率,。本設(shè)計中采用多路選擇器來實現(xiàn)crossbar。有5個方向輸入和5個方向輸出,。

　　根據(jù)邏輯控制模塊仲裁的選通信號,，5個五選一多路選擇器選擇輸出方向。隨后就是將本地緩存中的數(shù)據(jù)輸出到下一級的緩存中,，達(dá)到最終的傳輸,。

　　握手機(jī)制：首先向目標(biāo)方向（下一級）發(fā)送輸出數(shù)據(jù)請求，得到下一級確認(rèn)可以接收數(shù)據(jù)（下一級緩存為空）后,，再發(fā)送讀信號給緩存模塊輸出數(shù)據(jù),，下一狀態(tài)crossbar發(fā)送寫狀態(tài)和數(shù)據(jù)給下一級緩存。當(dāng)接收到來自本級緩存的清除信號clear后,，讀寫都置0,，這樣在讀寫的有效控制下完成數(shù)據(jù)傳輸,。

　　3.4 仿真驗證

　　采用Modesim6.5工具仿真實現(xiàn)驗證。首先驗證路由器各個方向數(shù)據(jù)通路的流通性,；其次驗證擁塞狀況下數(shù)據(jù)的傳輸狀態(tài),；最后優(yōu)化設(shè)計，提高性能,。圖8,、圖9顯示的是擁塞狀態(tài)下仿真的數(shù)據(jù)輸入輸出結(jié)果。

　　仿真模擬4個方向同時競爭向E傳輸請求,，第一批E方向的數(shù)據(jù)正常向W傳輸,，W向E的數(shù)據(jù)方向調(diào)整向N，N方向占用信道向E傳輸,，IP向東,、北方向的E、N信道都被占用,，S向E傳輸?shù)却?。第二批S向E先占用信道，IP調(diào)整方向向N,。

　　設(shè)計實現(xiàn)的虛通道路由器的電路模型能夠?qū)崿F(xiàn)NoC網(wǎng)絡(luò)中的數(shù)據(jù)傳輸,，足夠的虛通道數(shù)提高并行傳輸?shù)耐掏侣省７抡娼Y(jié)果顯示,，自適應(yīng)XY分配算法能夠避免死鎖,、活鎖的現(xiàn)象。虛通道路由器的設(shè)計方法對后續(xù)SIMD PE陣列體系結(jié)構(gòu)的研究具有指導(dǎo)意義,。

　　參考文獻(xiàn)

　　[1] 劉有耀.片上網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)與通信方法的研究[D].西安：西安電子科技大學(xué),，2009.

　　[2] 沈緒榜,，劉澤響,，王茹.計算機(jī)體系結(jié)構(gòu)的統(tǒng)一模型[J].計算機(jī)學(xué)報，2007,，30（5）：729-736.

　　[3] 王芳莉,，杜慧敏.片上網(wǎng)絡(luò)路由算法綜述[J].西安郵電學(xué)院學(xué)報，2011,，16（1）：72-77.

　　[4] Liu Youyao,，Gao Meng. Mesh-conneted rings topology for network-on-chip[J]. Posts and Telecommunications， 2013,，20（5）：30-36.

　　[5] PUTHALL M K,， SINGH V， GAUR M S,， et al. C_Routing： an  adaptive hierarchical NoC routing methodology[C]. 2011 IEEE/IFIP 19th International  Conference on  VLSI and  System-on-Chip,， Kowloon,，Hong Kong，China,， 2011.

　　[6] 張香香.片上網(wǎng)絡(luò)虛通道分配算法研究[D].西安：西安電子科技大學(xué),，2012.

　　[7] 張哲，高小鵬,，龍翔.適用于虛通道路由器的高性能round-robin仲裁器[J].北京航空航天大學(xué)學(xué)報,，2007，33（6）：743-747.

　　[8] 付志洲,，凌翔.片上網(wǎng)絡(luò)路由器的交叉開關(guān)設(shè)計實現(xiàn)[J].中國集成電路,，2010，19（9）：63-68.