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

1.天津工業(yè)大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，天津 300387

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

1 引言

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

片上網(wǎng)絡(luò)作為復(fù)雜SoC 的一種新的互聯(lián)與通信架構(gòu)[5]，當(dāng)規(guī)模越來越復(fù)雜時，其自身所存在的功耗和延時問題嚴(yán)重限制了SoC 性能的進(jìn)一步提升。傳統(tǒng)片上網(wǎng)絡(luò)中遠(yuǎn)距離傳輸會帶來高延遲高能耗等問題，擴展性、空間等問題也是巨大的挑戰(zhàn)。為了緩和NoC 中復(fù)雜的通信問題，人們提出了一些新的互連結(jié)構(gòu)，如3D片上網(wǎng)絡(luò)[6]、片上光網(wǎng)絡(luò)[7]、無線片上網(wǎng)絡(luò)[8]（wireless network-on-chip，WNoC）。

因為片上微型無線天線技術(shù)的實現(xiàn)，使得片上網(wǎng)絡(luò)的內(nèi)部可以實現(xiàn)無線通信?；旌蠠o線片上網(wǎng)絡(luò)正是基于這一技術(shù)和為解決高集成度帶來的高功耗和高延遲難題而提出的新型的技術(shù)[9]。無線片上網(wǎng)絡(luò)作為其中一種新型的互連結(jié)構(gòu)己經(jīng)受到了廣泛的關(guān)注，已經(jīng)有很多人提出了各種類型的WNoC 并進(jìn)行研究。研究界提出無線片上網(wǎng)絡(luò)WNoC，希望用無線連接代替有線連接，在NoC節(jié)點間插入某種更快的傳輸信道，增加NoC節(jié)點的傳輸范圍，減小多核系統(tǒng)中信息傳輸路徑的跳數(shù)，達(dá)到減小系統(tǒng)延時和能耗，增加系統(tǒng)吞吐率的目的，進(jìn)一步提高系統(tǒng)整體性能。

本文提出了一種正六面體的混合無線片上網(wǎng)絡(luò)架構(gòu)。在這個正六面體的結(jié)構(gòu)中，將無線節(jié)點放置在正六面體的頂點上。在本文提出的正六面體的拓?fù)浣Y(jié)構(gòu)中，存在無線節(jié)點的層間消息傳送就可以依靠無線路由器進(jìn)行快速的數(shù)據(jù)包的傳輸。同時，對傳統(tǒng)的XYZ 路由算法進(jìn)行了改進(jìn)，使改進(jìn)后的路由算法適應(yīng)于此正六面體無線片上網(wǎng)絡(luò)架構(gòu)。

2 拓?fù)浣Y(jié)構(gòu)

NoC 的拓?fù)浣Y(jié)構(gòu)決定了網(wǎng)絡(luò)的物理布局及節(jié)點和通道之間的連接。拓?fù)浣Y(jié)構(gòu)的設(shè)計對WNoC的網(wǎng)絡(luò)延遲、功耗、吞吐能力等性能指標(biāo)均有直接的、重要的影響。無線NoC的拓?fù)渲谐擞芯€節(jié)點、鏈路的布局和互連方式外，其無線節(jié)點的數(shù)目、鏈路的放置以及信道的分配[10]對無線NoC的性能影響也至關(guān)重要。

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

本文提出的是一個含有無線路由節(jié)點的8×8×4的混合無線片上網(wǎng)絡(luò)結(jié)構(gòu)。在Noxim仿真器中現(xiàn)有的拓?fù)浣Y(jié)構(gòu)基礎(chǔ)上增加無線路由節(jié)點和無線連接構(gòu)成正六面體結(jié)構(gòu)，使其可以應(yīng)用到混合無線片上網(wǎng)絡(luò)中。NoC的互聯(lián)結(jié)構(gòu)如圖1所示。從中可以看出一個NoC系統(tǒng)由處理單元（processing element）、網(wǎng)絡(luò)接口（network interface，NI）、路由器（router）和數(shù)據(jù)通道組成，其中含有無線路由節(jié)點的Mesh結(jié)構(gòu)如圖2所示。

Fig.1 Composition of NoC interconnection architecture圖1 片上網(wǎng)絡(luò)互聯(lián)結(jié)構(gòu)的組成

Fig.2 Mesh structure with wireless routing nodes圖2 含有無線路由節(jié)點的Mesh結(jié)構(gòu)

定義節(jié)點坐標(biāo)為N（x,y,z）。其中第0 層和第3 層的節(jié)點坐標(biāo)分別為（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 個節(jié)點均為無線節(jié)點，分別記為WR0～WR7。該混合結(jié)構(gòu)的中間兩層不存在無線節(jié)點，拓?fù)浣Y(jié)構(gòu)如圖3所示。

3 路由算法

Fig.3 Topology of 4 layer hybrid wireless NoC圖3 4層混合無線片上網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)

目前，對于三維片上網(wǎng)絡(luò)的研究[15]主要集中在底層元器件、拓?fù)浣Y(jié)構(gòu)和路由算法三方面，其中以拓?fù)浣Y(jié)構(gòu)與路由算法的關(guān)系最為密切。一個優(yōu)秀的路由算法可以充分發(fā)揮出拓?fù)浣Y(jié)構(gòu)的性能，而一個優(yōu)秀的拓?fù)浣Y(jié)構(gòu)也可以使路由算法設(shè)計更加簡單有效。在片上網(wǎng)絡(luò)和無線片上網(wǎng)絡(luò)中，路由算法根據(jù)不同的分類標(biāo)準(zhǔn)分成不同的類別[16]。

在確定了WNoC 拓?fù)浣Y(jié)構(gòu)后，路由算法決定一個消息或者一個數(shù)據(jù)包從源節(jié)點傳輸?shù)侥繕?biāo)節(jié)點的路徑。路由算法應(yīng)該基于網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，以合適的方式分布數(shù)據(jù)流，使得網(wǎng)絡(luò)中的數(shù)據(jù)流能很好地得到平衡，同時使網(wǎng)絡(luò)的延遲和吞吐量得到改善。

基于本文所提出的混合無線片上網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，傳統(tǒng)的XYZ 路由算法顯然不適合該架構(gòu)下的節(jié)點之間的數(shù)據(jù)包的傳遞[17]。因此給出了一種由維序XYZ 路由算法改進(jìn)而來的，可以和本文提出的混合無線片上網(wǎng)絡(luò)架構(gòu)相匹配的新型路由算法：WXYZ算法。在本文提出的WXYZ路由算法中，結(jié)合正六面立體結(jié)構(gòu)的對稱性[18]，設(shè)立規(guī)則：無線路由節(jié)點之間只能在Z軸方向進(jìn)行數(shù)據(jù)傳輸，算法流程如圖4所示。

WXYZ路由算法將有線傳輸與無線傳輸結(jié)合起來，實現(xiàn)了無線的高帶寬通信和無線傳輸?shù)膯翁脱舆t特性[19]。這對降低功耗，提高片上網(wǎng)路的整體性能具有至關(guān)重要的作用。

算法具體描述如下：

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

（1）判斷初始節(jié)點（S）和目的節(jié)點（D）是否在同一子網(wǎng)Mesh 中。如果在同一子網(wǎng)中，則用傳統(tǒng)的維序XY 路由算法，將初始節(jié)點的信息傳遞到目標(biāo)節(jié)點。XY 路由算法的具體過程是：先沿X方向?qū)?shù)據(jù)發(fā)送至目標(biāo)節(jié)點所在的列；再沿Y方向?qū)?shù)據(jù)發(fā)送至目標(biāo)節(jié)點所在的行。這種算法很簡單地解決了不同維度上的死鎖。若不在，執(zhí)行（2）。

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

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

節(jié)點之間的信息傳輸方式根據(jù)源節(jié)點與目的節(jié)點Z軸坐標(biāo)之差可分為三種方式，一一舉例來說明。

對于實例1（即源節(jié)點和目的節(jié)點所在子網(wǎng)都存在無線路由節(jié)點的情況下），如圖5 所示。假設(shè)源節(jié)點坐標(biāo)為A（2，1，0），目的節(jié)點坐標(biāo)是B（1，1，3），那么信息傳輸?shù)穆窂骄蜑锳—WR0—WR4—B。其中節(jié)點WR0（2，2，0）到WR4（2，2，3）通過無線進(jìn)行傳輸，節(jié)省了從第0 層慢慢地通過一個一個節(jié)點傳輸?shù)降?層這個步驟，實現(xiàn)了無線網(wǎng)絡(luò)的單跳傳輸。當(dāng)片上網(wǎng)絡(luò)規(guī)模較大的時候，會有效地降低延遲。

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

對于源節(jié)點和目的節(jié)點相隔一層的信息傳輸，使用傳統(tǒng)的XYZ路由算法。

對于實例2（即源節(jié)點和目的節(jié)點層數(shù)差為2），如圖6所示。從源節(jié)點M（1，1，1）要發(fā)送信息到N（2，0，3），根據(jù)文中提出的路由算法來計算|Mz-Nz|=2，此時Z軸的坐標(biāo)差等于2，此時應(yīng)該將源節(jié)點M的數(shù)據(jù)包首先傳輸?shù)骄嚯xM較近的擁有無線節(jié)點的第0層，然后通過第0層的無線路由節(jié)點將數(shù)據(jù)信息傳輸?shù)侥康墓?jié)點。傳輸路徑如下：M-WR0-WR2-WR6-WR4-N。

4 仿真實驗

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

本文給出的拓?fù)浣Y(jié)構(gòu)是在8×8×4 的混合無線片上網(wǎng)絡(luò)架構(gòu)，有256個節(jié)點。仿真實驗是在Access Noxim v2.0 仿真器上實現(xiàn)的，運行于Ubuntu13 操作系統(tǒng)。該仿真器的默認(rèn)架構(gòu)是同構(gòu)的3D-mesh架構(gòu)，將其改成基于正六面體的混合無線的三維片上網(wǎng)絡(luò)結(jié)構(gòu)。通過仿真實驗證明了本文提出的混合無線三維片上網(wǎng)絡(luò)拓?fù)浼軜?gòu)在功耗和延遲方面與傳統(tǒng)的有線片上網(wǎng)絡(luò)架構(gòu)相比有了顯著的性能改善。仿真實驗的參數(shù)設(shè)計上參考文獻(xiàn)[21-22]，具體實驗參數(shù)配置如表1所示。

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

4.1 網(wǎng)絡(luò)平均路由跳數(shù)

與傳統(tǒng)的有線三維片上網(wǎng)絡(luò)相比，平均路由跳數(shù)最能直觀地反映出無線節(jié)點在網(wǎng)絡(luò)中傳輸?shù)膬?yōu)勢，同時還對比了將無線節(jié)點放置于其他層間的情況。通過仿真得出6 種不同拓?fù)浣Y(jié)構(gòu)的平均路由跳數(shù)，如圖7 所示。其中Average_hopcount表示平均路由跳數(shù)，N01表示將無線路由節(jié)點放置在第0層和第1層，其他同理，Wired NoC表示傳統(tǒng)有線片上網(wǎng)絡(luò)。

Fig.7 Average routing hop count圖7 平均路由跳數(shù)

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

4.2 網(wǎng)絡(luò)平均延遲

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

其中，Daverage表示網(wǎng)絡(luò)平均延遲，n表示網(wǎng)絡(luò)在一定時間內(nèi)傳輸?shù)臄?shù)據(jù)包的個數(shù)，Di表示第i個數(shù)據(jù)包的延遲。在其他條件相同的情況下，平均延遲越小的網(wǎng)絡(luò)，其性能則越好。

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

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

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

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

圖9中，Hybrid NoC表示本文所提出的混合無線片上網(wǎng)絡(luò)結(jié)構(gòu)，Wired NoC表示傳統(tǒng)的有線三維片上網(wǎng)絡(luò)。仿真實驗的結(jié)果表明，在注入率較低的情況下，性能并沒有顯著提升，但隨著注入率的逐漸增大，有線片上網(wǎng)絡(luò)的時延和無線片上網(wǎng)絡(luò)的時延差距越來越明顯，尤其是在注入率大于0.03后，改進(jìn)后的混合無線片上網(wǎng)絡(luò)架構(gòu)在延遲方面的性能表現(xiàn)明顯優(yōu)于傳統(tǒng)的有線三維片上網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。

4.3 網(wǎng)絡(luò)總功耗

NoC 系統(tǒng)功耗指的是在單位時間內(nèi)網(wǎng)絡(luò)中處理數(shù)據(jù)和傳輸數(shù)據(jù)所引起的功率消耗。仿真實驗是在Ubuntu13 下進(jìn)行的，其總功耗主要來自于處理機產(chǎn)生的功耗和片上網(wǎng)路中數(shù)據(jù)通信產(chǎn)生的功耗，如式（2）所示。

其中，P為總功耗值，PN為片上網(wǎng)絡(luò)中數(shù)據(jù)通信產(chǎn)生的耗能值，PPE為處理器產(chǎn)生的耗能值。

圖10的實驗結(jié)果表明，隨著注入率的逐漸增大，兩種結(jié)構(gòu)的總功耗呈線性增加，且有線片上網(wǎng)絡(luò)架構(gòu)的總功耗增加的幅度較大。當(dāng)注入率在0.13 時，兩種結(jié)構(gòu)的總功耗開始趨于穩(wěn)定狀態(tài)，此時，混合無線片上網(wǎng)絡(luò)架構(gòu)的網(wǎng)絡(luò)總功耗要遠(yuǎn)小于有線片上網(wǎng)絡(luò)。

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

5 結(jié)束語

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