摘  要： 針對陣列處理單元之間互連傳輸擁塞的問題，設(shè)計了一種在二維結(jié)構(gòu)中互連的虛通道路由器模型。采用改進的自適應XY路由算法，智能地分配虛通道空閑資源，從邏輯上減少擁塞和等待時間，多路選擇器交叉開關(guān)完成數(shù)據(jù)傳輸。通過ASIC設(shè)計，完成虛通道路由器硬件電路，應用Modesim工具進行仿真，達到網(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）采用共享總線方式通信，也同樣面臨著帶寬限制、信號延遲等問題。一些研究機構(gòu)借鑒網(wǎng)絡(luò)通信中的思路，提出基于網(wǎng)絡(luò)互連的NoC（Network-on-Chip）系統(tǒng)芯片架構(gòu)，其優(yōu)勢就是降低SoC的功耗和制造費用、提高性能等。

　　當前，以網(wǎng)絡(luò)互連為基礎(chǔ)的高性能的陣列處理器系統(tǒng)芯片成為人們研究的熱點。根據(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拓撲結(jié)構(gòu)基本原理

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

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

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

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

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

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

　　虛通道路由器軟核是應用于片上網(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è)計相同，便于復用。2D Mesh結(jié)構(gòu)中一個路由的輸出方向最多為4個（不會回頭），所以虛通道數(shù)[6]可以為4。

　　虛通道分配器（Vc_allactor）為路由邏輯中的主要部分，是給輸入緩存中的數(shù)據(jù)分配空閑的數(shù)據(jù)信道，根據(jù)路由算法選擇輸出方向，提供信號給交叉開關(guān)模塊。由于每個方向都有4個虛通道，多個方向向同一方向傳送數(shù)據(jù)時能夠充分傳輸，減少擁塞過程中的等待時間，增加吞吐量。但當同一方向的數(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和包負載數(shù)據(jù)payload組成。設(shè)計中采用16 bit寬度的包數(shù)據(jù)，在一定需求的情況下可以進行擴展。有4 bit控制信息，1 bit標志位，3 bit包尺寸；6 bit源地址信息；6 bit目標地址信息，高3位為X方向地址，低3位為Y方向地址。中間片flit都是16 bit數(shù)據(jù)的包負載。數(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)機實現(xiàn)。類似于IP網(wǎng)絡(luò)傳輸中的握手機制協(xié)議，請求與應答。虛通道緩存中只有在沒數(shù)據(jù)時才能接收數(shù)據(jù)，只有在目的緩存（下一級虛通道）準備好時才能輸出數(shù)據(jù)。內(nèi)部虛通道與路由邏輯之間也存在握手機制，只有在請求發(fā)送信號得到確認時才發(fā)送數(shù)據(jù)包頭數(shù)據(jù)，否則等待。

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

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

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

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

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

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

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

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

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

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

　　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ù)輸出到下一級的緩存中，達到最終的傳輸。

　　握手機制：首先向目標方向（下一級）發(fā)送輸出數(shù)據(jù)請求，得到下一級確認可以接收數(shù)據(jù)（下一級緩存為空）后，再發(fā)送讀信號給緩存模塊輸出數(shù)據(jù)，下一狀態(tài)crossbar發(fā)送寫狀態(tài)和數(shù)據(jù)給下一級緩存。當接收到來自本級緩存的清除信號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é)果顯示，自適應XY分配算法能夠避免死鎖、活鎖的現(xiàn)象。虛通道路由器的設(shè)計方法對后續(xù)SIMD PE陣列體系結(jié)構(gòu)的研究具有指導意義。

　　參考文獻

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

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

　　[3] 王芳莉，杜慧敏.片上網(wǎng)絡(luò)路由算法綜述[J].西安郵電學院學報，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].西安：西安電子科技大學，2012.

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

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