摘  要： 針對陣列處理單元之間互連傳輸擁塞的問題，設計了一種在二維結構中互連的虛通道路由器模型。采用改進的自適應XY路由算法，智能地分配虛通道空閑資源，從邏輯上減少擁塞和等待時間，多路選擇器交叉開關完成數據傳輸。通過ASIC設計，完成虛通道路由器硬件電路，應用Modesim工具進行仿真，達到網絡互連傳輸的目的。

　　關鍵詞： 網絡互連；虛通道路由器；路由算法；ASIC設計

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

　　當前，以網絡互連為基礎的高性能的陣列處理器系統芯片成為人們研究的熱點。根據計算機體系結構的發展，共有10種體系結構模型[2]。它們以指令流、數據流與構令流計算為基礎，完成算法到體系結構的時間、空間映射。一種新型的基于指令流的統一體系結構模型Unified-ISA[2]被提出，使得所有的電路設計問題統一到基于指令流計算的SIMD PE陣列上的程序設計問題。SIMD PE陣列中處理元PE之間數據傳輸的問題正是網絡互連中路由傳輸的問題。

1 2D Mesh拓撲結構基本原理

　　NoC內集成了大量的資源IP核，拓撲結構解決的是互連網絡中各個資源IP節點的分布與銜接。按照不同的系統性能需求，可以有不同的拓撲結構解決方案，如規則的2D Mesh網狀結構、蜂窩結構、樹狀結構等。

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

　　在NoC網絡中完成數據傳輸除了拓撲結構元素外，還有另一個重要元素——路由算法[1，3-5]。路由算法解決的是數據傳輸過程中找到最佳的傳輸路徑，而簡單、靈活、健壯、低耗、穩定的算法，正是提高傳輸性能的關鍵。

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

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

2 虛通道路由器總體設計模型

　　虛通道路由器軟核是應用于片上網絡（NoC）的一個包交換型路由器，是NoC的重要基礎部件。其體系結構框圖如圖2所示。

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

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

　　交叉開關模塊（Crossbar）根據路由邏輯中的方向選擇，完成數據的最后輸出。

3 路由器模塊化設計

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

　　根據整個路由節點的數據流和控制流兩個方向，將設計分為3大模塊：輸入緩存模塊、邏輯控制模塊和交叉開關模塊。數據從輸入緩存中流入，經過控制模塊分配處輸出方向，交叉開關根據方向選擇緩存中的數據輸出。

　　3.1 輸入緩存模塊（FIFO）

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

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

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

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

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

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

　　（1）當5個方向有傳輸請求syn_*，并行確認來自5個方向的發送請求ack_*；

　　（2）接收5個方向的包頭目標地址數據data_head_*[5：0]；

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

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

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

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

　　3.3 交叉開關輸出模塊（crossbar）

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

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

　　握手機制：首先向目標方向（下一級）發送輸出數據請求，得到下一級確認可以接收數據（下一級緩存為空）后，再發送讀信號給緩存模塊輸出數據，下一狀態crossbar發送寫狀態和數據給下一級緩存。當接收到來自本級緩存的清除信號clear后，讀寫都置0，這樣在讀寫的有效控制下完成數據傳輸。

　　3.4 仿真驗證

　　采用Modesim6.5工具仿真實現驗證。首先驗證路由器各個方向數據通路的流通性；其次驗證擁塞狀況下數據的傳輸狀態；最后優化設計，提高性能。圖8、圖9顯示的是擁塞狀態下仿真的數據輸入輸出結果。

　　仿真模擬4個方向同時競爭向E傳輸請求，第一批E方向的數據正常向W傳輸，W向E的數據方向調整向N，N方向占用信道向E傳輸，IP向東、北方向的E、N信道都被占用，S向E傳輸等待。第二批S向E先占用信道，IP調整方向向N。

　　設計實現的虛通道路由器的電路模型能夠實現NoC網絡中的數據傳輸，足夠的虛通道數提高并行傳輸的吞吐率。仿真結果顯示，自適應XY分配算法能夠避免死鎖、活鎖的現象。虛通道路由器的設計方法對后續SIMD PE陣列體系結構的研究具有指導意義。

　　參考文獻

　　[1] 劉有耀.片上網絡拓撲結構與通信方法的研究[D].西安：西安電子科技大學，2009.

　　[2] 沈緒榜，劉澤響，王茹.計算機體系結構的統一模型[J].計算機學報，2007，30（5）：729-736.

　　[3] 王芳莉，杜慧敏.片上網絡路由算法綜述[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] 張香香.片上網絡虛通道分配算法研究[D].西安：西安電子科技大學，2012.

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

　　[8] 付志洲，凌翔.片上網絡路由器的交叉開關設計實現[J].中國集成電路，2010，19（9）：63-68.