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

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

　　隨著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)芯片成為人們研究的熱點(diǎn)。根據(jù)計(jì)算機(jī)體系結(jié)構(gòu)的發(fā)展，共有10種體系結(jié)構(gòu)模型[2]。它們以指令流、數(shù)據(jù)流與構(gòu)令流計(jì)算為基礎(chǔ)，完成算法到體系結(jié)構(gòu)的時(shí)間、空間映射。一種新型的基于指令流的統(tǒng)一體系結(jié)構(gòu)模型Unified-ISA[2]被提出，使得所有的電路設(shè)計(jì)問題統(tǒng)一到基于指令流計(jì)算的SIMD PE陣列上的程序設(shè)計(jì)問題。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ò)中各個(gè)資源IP節(jié)點(diǎn)的分布與銜接。按照不同的系統(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é)點(diǎn)外，每個(gè)節(jié)點(diǎn)都連接著1個(gè)IP核單元和4個(gè)臨近的路由單元，每個(gè)節(jié)點(diǎn)對應(yīng)一個(gè)物理坐標(biāo)編號（x，y），每個(gè)節(jié)點(diǎn)能夠?qū)?shù)據(jù)從源地址傳送到目的地址（一個(gè)或多個(gè)）。IP核可以是處理器核、DSP核、專用硬件資源或各種硬件資源的集合等。

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

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

　　本設(shè)計(jì)中的算法結(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ù)較多時(shí)，如果目的地址是在右下方向，則可以先調(diào)整方向轉(zhuǎn)彎向下走，以減少擁塞。在具體設(shè)計(jì)過程中數(shù)據(jù)傳輸方向不會(huì)往回走，只會(huì)朝著目標(biāo)前進(jìn)，可以避免回環(huán)死鎖現(xiàn)象。另外在路由邏輯中還可以仲裁均衡每個(gè)方向的平等性。

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

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

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

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

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

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

　　為簡化設(shè)計(jì)，設(shè)計(jì)中每個(gè)方向的虛通道數(shù)為1，數(shù)據(jù)包packet結(jié)構(gòu)由包頭數(shù)據(jù)header和包負(fù)載數(shù)據(jù)payload組成。設(shè)計(jì)中采用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ù)整個(gè)路由節(jié)點(diǎn)的數(shù)據(jù)流和控制流兩個(gè)方向，將設(shè)計(jì)分為3大模塊：輸入緩存模塊、邏輯控制模塊和交叉開關(guān)模塊。數(shù)據(jù)從輸入緩存中流入，經(jīng)過控制模塊分配處輸出方向，交叉開關(guān)根據(jù)方向選擇緩存中的數(shù)據(jù)輸出。

　　3.1 輸入緩存模塊（FIFO）

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

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

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

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

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

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

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

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

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

　　（4）根據(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_*}。這里，會(huì)出現(xiàn)多個(gè)方向同時(shí)向同一個(gè)方向發(fā)出使能的情況，將進(jìn)入下一步輪詢仲裁。如圖6所示的W方向的輸出使能狀態(tài)，使能列表中有2個(gè)位為1。首先判斷路徑是否被占用，即是否有忙信號，當(dāng)有busy信號時(shí)考慮轉(zhuǎn)彎調(diào)整，當(dāng)2個(gè)使能方向路徑都被占用時(shí)，只能等待路徑的釋放，這里方向使能列表一直都在。空閑狀態(tài)下根據(jù)優(yōu)先級W>S>E>N>IP，W向使能方向發(fā)出預(yù)期的輸出使能w_to_*。

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

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

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

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

　　根據(jù)邏輯控制模塊仲裁的選通信號，5個(gè)五選一多路選擇器選擇輸出方向。隨后就是將本地緩存中的數(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 仿真驗(yàn)證

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

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

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

　　參考文獻(xiàn)

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

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

　　[3] 王芳莉，杜慧敏.片上網(wǎng)絡(luò)路由算法綜述[J].西安郵電學(xué)院學(xué)報(bào)，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é)報(bào)，2007，33（6）：743-747.

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