混合無線三維片網中無線路由節點分布研究*

丁盼盼，宋國治+，趙成龍，周一杰

1.天津工業大學 計算機科學與技術學院，天津 300387

2.史蒂文斯理工學院 計算機科學學院，美國 霍博肯07030

1 引言

目前，科學技術的發展非常迅速，芯片的集成度越來越高，片上系統（system-on-chip，SoC）中的功能單元數量越來越多，如何在這些功能單元之間進行通信已經成為一個重要的課題。傳統的共享總線體系結構[1]由于其固有的可擴展性和較低的通信效率已經不能滿足當前SoC設計的需要。而片上網絡[2-4]（network-on-chip，NoC）作為替代結構出現。

片上網絡作為復雜SoC 的一種新的互聯與通信架構[5]，當規模越來越復雜時，其自身所存在的功耗和延時問題嚴重限制了SoC 性能的進一步提升。傳統片上網絡中遠距離傳輸會帶來高延遲高能耗等問題，擴展性、空間等問題也是巨大的挑戰。為了緩和NoC 中復雜的通信問題，人們提出了一些新的互連結構，如3D片上網絡[6]、片上光網絡[7]、無線片上網絡[8]（wireless network-on-chip，WNoC）。

因為片上微型無線天線技術的實現，使得片上網絡的內部可以實現無線通信。混合無線片上網絡正是基于這一技術和為解決高集成度帶來的高功耗和高延遲難題而提出的新型的技術[9]。無線片上網絡作為其中一種新型的互連結構己經受到了廣泛的關注，已經有很多人提出了各種類型的WNoC 并進行研究。研究界提出無線片上網絡WNoC，希望用無線連接代替有線連接，在NoC節點間插入某種更快的傳輸信道，增加NoC節點的傳輸范圍，減小多核系統中信息傳輸路徑的跳數，達到減小系統延時和能耗，增加系統吞吐率的目的，進一步提高系統整體性能。

本文提出了一種正六面體的混合無線片上網絡架構。在這個正六面體的結構中，將無線節點放置在正六面體的頂點上。在本文提出的正六面體的拓撲結構中，存在無線節點的層間消息傳送就可以依靠無線路由器進行快速的數據包的傳輸。同時，對傳統的XYZ 路由算法進行了改進，使改進后的路由算法適應于此正六面體無線片上網絡架構。

2 拓撲結構

NoC 的拓撲結構決定了網絡的物理布局及節點和通道之間的連接。拓撲結構的設計對WNoC的網絡延遲、功耗、吞吐能力等性能指標均有直接的、重要的影響。無線NoC的拓撲中除了有線節點、鏈路的布局和互連方式外，其無線節點的數目、鏈路的放置以及信道的分配[10]對無線NoC的性能影響也至關重要。

文獻[11]中，Zhao 等人提出了一個基于Mesh 結構的純無線WNoC。在該結構中，所有的節點均為無線節點，任意兩個相鄰節點均通過無線鏈路通信，從而形成了一個無線的二維Mesh 結構。由于該WNoC是一個純無線網絡，因此節點之間的通信采用無線多跳的方式，從而導致整個網絡的面積開銷和功耗大大增加。文獻[12]為了解決在不同模塊之間進行芯片互聯信號的傳輸問題，提出了一個混合無線片上網絡結構。該結構是將二維片上網絡結構分成四個子網，并在每個子網的中心位置放置無線節點。該結構隨著網絡規模的逐漸增大，子網內部通信的路由距離也隨之增大，因此會造成一定程度的延時。哈爾濱工業大學呂鵬提出了一種2-Level Hybrid Mesh結構[13]，其是將整個有線Mesh 劃分成3×3 的子網，并將每個子網中心位置的節點換成無線節點。因此，它包含了一個下層有線Mesh和一個上層無線Mesh。雖然該結構降低了網絡延時和擁塞水平，但會造成一定的面積開銷。文獻[14]介紹了一種多級網狀拓撲結構，稱為MLM（multi-level mesh）的NoC 拓撲結構。如果令最下層的Mesh為有線Mesh結構，而其余的上層Mesh為無線Mesh結構，就可以得到一個基于MLM結構的混合WNoC。該結構中雖然無線節點分布比較均衡，能夠縮短節點間數據包傳輸的距離，但當該結構中無線Mesh 的層數過多時，無線節點數量的增長會導致網絡的功耗增加。在該拓撲結構的基礎上，提出將有線Mesh層和無線Mesh層交替形成一個4層的混合無線拓撲結構，對每一層進行子網的劃分，并在無線Mesh 層的各個子網的中心放置一個無線路由節點。通過改變無線路由節點的位置（無線節點的擺放位置有6種情況，分別為第0層和第1層、第0層和第2層、第0層和第3層、第1層和第2層、第1層和第3層、第2層和第3層）進行仿真實驗，結果表明在4層的混合無線NoC結構中，將無線節點均勻地放置在第0層和第3層的性能最優，此時無線路由節點的擺放位置恰好構成了正六面體的8 個頂點。在整個網絡中，無線節點的數量處于較低的水平，因此網絡的面積開銷和功耗可以得到有效的控制，使其保持在合理的范圍之內。

本文提出的是一個含有無線路由節點的8×8×4的混合無線片上網絡結構。在Noxim仿真器中現有的拓撲結構基礎上增加無線路由節點和無線連接構成正六面體結構，使其可以應用到混合無線片上網絡中。NoC的互聯結構如圖1所示。從中可以看出一個NoC系統由處理單元（processing element）、網絡接口（network interface，NI）、路由器（router）和數據通道組成，其中含有無線路由節點的Mesh結構如圖2所示。

Fig.1 Composition of NoC interconnection architecture圖1 片上網絡互聯結構的組成

Fig.2 Mesh structure with wireless routing nodes圖2 含有無線路由節點的Mesh結構

定義節點坐標為N（x,y,z）。其中第0 層和第3 層的節點坐標分別為（2,2,0）、（5,2,0)、（2,5,0）、（5,5,0）、（2,2,3）、（5,2,3）、（2,5,3）、（5,5,3），這8 個節點均為無線節點，分別記為WR0～WR7。該混合結構的中間兩層不存在無線節點，拓撲結構如圖3所示。

3 路由算法

Fig.3 Topology of 4 layer hybrid wireless NoC圖3 4層混合無線片上網絡的拓撲結構

目前，對于三維片上網絡的研究[15]主要集中在底層元器件、拓撲結構和路由算法三方面，其中以拓撲結構與路由算法的關系最為密切。一個優秀的路由算法可以充分發揮出拓撲結構的性能，而一個優秀的拓撲結構也可以使路由算法設計更加簡單有效。在片上網絡和無線片上網絡中，路由算法根據不同的分類標準分成不同的類別[16]。

在確定了WNoC 拓撲結構后，路由算法決定一個消息或者一個數據包從源節點傳輸到目標節點的路徑。路由算法應該基于網絡的拓撲結構，以合適的方式分布數據流，使得網絡中的數據流能很好地得到平衡，同時使網絡的延遲和吞吐量得到改善。

基于本文所提出的混合無線片上網絡拓撲結構，傳統的XYZ 路由算法顯然不適合該架構下的節點之間的數據包的傳遞[17]。因此給出了一種由維序XYZ 路由算法改進而來的，可以和本文提出的混合無線片上網絡架構相匹配的新型路由算法：WXYZ算法。在本文提出的WXYZ路由算法中，結合正六面立體結構的對稱性[18]，設立規則：無線路由節點之間只能在Z軸方向進行數據傳輸，算法流程如圖4所示。

WXYZ路由算法將有線傳輸與無線傳輸結合起來，實現了無線的高帶寬通信和無線傳輸的單跳低延遲特性[19]。這對降低功耗，提高片上網路的整體性能具有至關重要的作用。

算法具體描述如下：

Fig.4 Flow chart of WXYZ routing algorithm圖4 WXYZ路由算法流程圖

（1）判斷初始節點（S）和目的節點（D）是否在同一子網Mesh 中。如果在同一子網中，則用傳統的維序XY 路由算法，將初始節點的信息傳遞到目標節點。XY 路由算法的具體過程是：先沿X方向將數據發送至目標節點所在的列；再沿Y方向將數據發送至目標節點所在的行。這種算法很簡單地解決了不同維度上的死鎖。若不在，執行（2）。

（2）假設S和D不在同一個子網中，計算初始節點與目標節點之間的Z軸坐標之差是否大于1，即通過初始節點和目標節點的Z軸坐標之差得到。若層數之差大于1 執行第（3）步，若層數之差等于1，則通過傳統的維序XYZ路由算法將初始節點的信息傳遞至目標節點。子網內部的通信通過有線鏈路來完成。XYZ 路由算法是在XY 路由算法的基礎上增加了Z軸方向的數據傳輸，屬于靜態路由選擇策略，實現簡單且開銷較小。

（3）對于初始節點和目標節點層數之差大于1的情況，先找到距離初始節點最近的無線路由節點，然后將初始節點的信息轉發到該無線節點中，通過無線節點進行傳遞，傳輸至目標節點。此時，源節點和目的節點通過無線鏈路進行跨子網通信。無線節點之間的消息傳輸采用了單跳的模式，縮短了子網之間數據包的傳輸距離。由于無線節點在網絡中分布較為均衡，降低了網絡擁塞[20]的可能性。

節點之間的信息傳輸方式根據源節點與目的節點Z軸坐標之差可分為三種方式，一一舉例來說明。

對于實例1（即源節點和目的節點所在子網都存在無線路由節點的情況下），如圖5 所示。假設源節點坐標為A（2，1，0），目的節點坐標是B（1，1，3），那么信息傳輸的路徑就為A—WR0—WR4—B。其中節點WR0（2，2，0）到WR4（2，2，3）通過無線進行傳輸，節省了從第0 層慢慢地通過一個一個節點傳輸到第3層這個步驟，實現了無線網絡的單跳傳輸。當片上網絡規模較大的時候，會有效地降低延遲。

Fig.5 Example 1 transmission path圖5 實例1傳輸路徑

對于源節點和目的節點相隔一層的信息傳輸，使用傳統的XYZ路由算法。

對于實例2（即源節點和目的節點層數差為2），如圖6所示。從源節點M（1，1，1）要發送信息到N（2，0，3），根據文中提出的路由算法來計算|Mz-Nz|=2，此時Z軸的坐標差等于2，此時應該將源節點M的數據包首先傳輸到距離M較近的擁有無線節點的第0層，然后通過第0層的無線路由節點將數據信息傳輸到目的節點。傳輸路徑如下：M-WR0-WR2-WR6-WR4-N。

4 仿真實驗

Fig.6 Example 2 transmission path圖6 實例2傳輸路徑

本文給出的拓撲結構是在8×8×4 的混合無線片上網絡架構，有256個節點。仿真實驗是在Access Noxim v2.0 仿真器上實現的，運行于Ubuntu13 操作系統。該仿真器的默認架構是同構的3D-mesh架構，將其改成基于正六面體的混合無線的三維片上網絡結構。通過仿真實驗證明了本文提出的混合無線三維片上網絡拓撲架構在功耗和延遲方面與傳統的有線片上網絡架構相比有了顯著的性能改善。仿真實驗的參數設計上參考文獻[21-22]，具體實驗參數配置如表1所示。

Table 1 Parameters for simulation experiments表1 仿真實驗固定參數配置

4.1 網絡平均路由跳數

與傳統的有線三維片上網絡相比，平均路由跳數最能直觀地反映出無線節點在網絡中傳輸的優勢，同時還對比了將無線節點放置于其他層間的情況。通過仿真得出6 種不同拓撲結構的平均路由跳數，如圖7 所示。其中Average_hopcount表示平均路由跳數，N01表示將無線路由節點放置在第0層和第1層，其他同理，Wired NoC表示傳統有線片上網絡。

Fig.7 Average routing hop count圖7 平均路由跳數

由于本文采用的算法在一定通信量之內，可以避免網絡擁塞。平均路由跳數直接反映了片上網絡的性能。通過仿真數據可以看出將無線節點放置在相鄰的兩層幾乎和有線片上網絡的跳數相差不大，而將無線路由節點放置在第0層和第3層，平均路由跳數最低，性能最好。

4.2 網絡平均延遲

在片上網絡中，網絡延遲表示的是數據包從注入網絡開始，到成功送達目的節點結束，中間所經歷的總時間。網絡延遲包括了發送延遲、傳輸延遲和接收延遲。由于網絡中數據包源節點和目的節點的不同，經過的路徑不同，路由節點的阻塞狀況不同，導致每個數據包的網絡延遲也不盡相同。因此，一般采用平均延遲來衡量片上網絡的性能，如式（1）所示。

其中，Daverage表示網絡平均延遲，n表示網絡在一定時間內傳輸的數據包的個數，Di表示第i個數據包的延遲。在其他條件相同的情況下，平均延遲越小的網絡，其性能則越好。

在仿真實驗中，由于將無線節點放置在相鄰層的性能與有線片上網絡相差不大，因此只對比了將無線節點放置在第0層和第3層、第0層和第2層、第1層和第3 層的平均延時。通過改變無線節點的擺放位置，得出了在不同注入率條件下的混合無線片上網絡的平均時延，仿真結果如圖8 所示。此外，還將本文提出的混合無線三維片上網絡架構與有線三維片上網絡架構的平均延遲進行了對比，實驗結果如圖9所示。

Fig.8 Relation of packet injection rate and average delay for wireless node distribution圖8 不同無線節點分布，注入率與平均延遲關系圖

Fig.9 Average delay of NoC with uniform random distribution of packet injection rate圖9 注入率均勻隨機分布下的網絡平均延遲

從圖8 中可以看出，在注入率較低的情況下，即注入率在0.01～0.03 的范圍內，延遲變化不明顯。但隨著逐漸加大注入率，在注入率大于0.03 后無線拓撲結構N03的延時略優于無線拓撲結構N02和N13，大約有10%的性能提升，而在注入率加大到0.07 后，無線拓撲結構N03 的延時與無線拓撲結構N02 和N13 逐漸拉大，約有12%的性能提升。由此可以看出，三維無線片網中無線節點分布對于片網性能是有較大的影響。在原有的拓撲結構中加入無線路由器節點和無線通信信道，整個無線信道構成正六面體結構使得數據包在整個拓撲結構中的傳輸延遲有較明顯的降低。

圖9中，Hybrid NoC表示本文所提出的混合無線片上網絡結構，Wired NoC表示傳統的有線三維片上網絡。仿真實驗的結果表明，在注入率較低的情況下，性能并沒有顯著提升，但隨著注入率的逐漸增大，有線片上網絡的時延和無線片上網絡的時延差距越來越明顯，尤其是在注入率大于0.03后，改進后的混合無線片上網絡架構在延遲方面的性能表現明顯優于傳統的有線三維片上網絡拓撲結構。

4.3 網絡總功耗

NoC 系統功耗指的是在單位時間內網絡中處理數據和傳輸數據所引起的功率消耗。仿真實驗是在Ubuntu13 下進行的，其總功耗主要來自于處理機產生的功耗和片上網路中數據通信產生的功耗，如式（2）所示。

其中，P為總功耗值，PN為片上網絡中數據通信產生的耗能值，PPE為處理器產生的耗能值。

圖10的實驗結果表明，隨著注入率的逐漸增大，兩種結構的總功耗呈線性增加，且有線片上網絡架構的總功耗增加的幅度較大。當注入率在0.13 時，兩種結構的總功耗開始趨于穩定狀態，此時，混合無線片上網絡架構的網絡總功耗要遠小于有線片上網絡。

Fig.10 Total power consumption of NoC with uniform random distribution of packet injection rate圖10 注入率均勻隨機分布下的網絡總功耗

5 結束語

本文提出了一種混合無線片上網絡架構以及適應于該架構的路由算法，最后通過仿真實驗分別得出網絡平均延遲和網絡總功耗等性能參數。一方面，在8×8×4 的混合無線片上網絡的基礎上，改變無線路由節點的位置，探討了無線路由位置對于片網的性能的影響。另一方面，將該架構與傳統的有線三維片上網絡的性能進行了對比。實驗結果表明，本文所提出的混合無線片上網絡架構在平均延遲以及功耗方面有了很大改善。由于該架構中的無線節點占節點總數的比例較小，在大規模通信時，無線節點所承擔的通信量較大，在一定程度上會產生擁塞問題，接下來的工作將會重點集中在此。