三維片上網(wǎng)絡(luò)高維超立方裂變拓?fù)浣Y(jié)構(gòu)研究*

梁華林，張大坤

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

+通訊作者E-mail:zhangdakun2018@163.com

1 引言

現(xiàn)代芯片需要將大量的功能和存儲核心（也稱IP 核，intellectual property block），如音頻和視頻處理器、存儲器、I/O外設(shè)和硬件加速器等，集成到一個芯片上進(jìn)行交換數(shù)據(jù)以實現(xiàn)多媒體和網(wǎng)絡(luò)服務(wù)。早期的IP 核通訊由于缺少合理的設(shè)計限制了芯片的性能。在這種情況下片上系統(tǒng)（system-on-chip，SoC）和二維片上網(wǎng)絡(luò)（two-dimensional network-on-chip，2D NoC）應(yīng)運(yùn)而生。然而，隨著2D NoC 的發(fā)展，其在規(guī)模、性能和布線方面都出現(xiàn)了瓶頸[1]。三維片上網(wǎng)絡(luò)（three dimensional network-on-chip，3D NoC）在這種情況下被提出，近年來國內(nèi)外學(xué)者對其進(jìn)行了廣泛的研究[2-5]。

在3D NoC研究中，拓?fù)浣Y(jié)構(gòu)是關(guān)鍵問題之一[6]；關(guān)于片上網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的研究主要有兩方向：其一，對已有三維片上網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的改進(jìn)與優(yōu)化；其二，研究新型網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。目前，關(guān)于經(jīng)典三維片上網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)路由算法改進(jìn)的研究較多，如Ashokkumar等人提出了通過編碼解碼方法對3D Mesh 的路由算法進(jìn)行優(yōu)化[7]；上海交通大學(xué)Yao 等人設(shè)計了路由尋路單元對3D Torus尋路進(jìn)行了優(yōu)化[8]；而對于新型拓?fù)浣Y(jié)構(gòu)的研究報道較少，與經(jīng)典拓?fù)浣Y(jié)構(gòu)相比，新型拓?fù)浣Y(jié)構(gòu)更能適應(yīng)特定情況下的特殊要求，而且一部分針對經(jīng)典拓?fù)浣Y(jié)構(gòu)的路由算法也可以移植到新型拓?fù)浣Y(jié)構(gòu)中，如北德克薩斯大學(xué)Mohanty等人提出了改進(jìn)3D NoC 蝶形胖樹網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)[9]；Chen 等人提出的基于De Bruijn圖的新型3D NoC拓?fù)浣Y(jié)構(gòu)[10]；湖南大學(xué)賀旭等人提出了三維超立方體片上網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)[11]；西安電子科技大學(xué)劉有耀等人根據(jù)Torus拓?fù)浣Y(jié)構(gòu)提出了新型拓?fù)浣Y(jié)構(gòu)及其路由算法等[12]。其中，超立方體拓?fù)浣Y(jié)構(gòu)具有對稱性好、網(wǎng)絡(luò)直徑短、可擴(kuò)展性高等優(yōu)點(diǎn)。然而，隨著超立方體維度的增加，其節(jié)點(diǎn)間連線數(shù)量急劇增加，因而出現(xiàn)通訊瓶頸。在國家自然科學(xué)基金（課題號：61272006）研究過程中發(fā)現(xiàn)，將三維模型裂變思想用到超立方體拓?fù)浣Y(jié)構(gòu)中能夠有效地克服超立方體拓?fù)浣Y(jié)構(gòu)的缺點(diǎn)。本文提出了三維片上網(wǎng)絡(luò)五維超立方裂變拓?fù)浣Y(jié)構(gòu)，該拓?fù)浣Y(jié)構(gòu)對超立方體結(jié)構(gòu)使用“裂變”方法來增加節(jié)點(diǎn)，代替以往網(wǎng)絡(luò)規(guī)模擴(kuò)大時從邊緣增加節(jié)點(diǎn)的“加法”操作，既保留了超立方體拓?fù)浣Y(jié)構(gòu)的優(yōu)點(diǎn)，又解決了高維超立方體拓?fù)浣Y(jié)構(gòu)的通訊瓶頸問題。

2 超立方體裂變拓?fù)浣Y(jié)構(gòu)的提出與分析

2.1 三維模型裂變思想

在國家自然科學(xué)基金課題“基于柏拉圖立體多級裂變模型的三維片上網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)”研究中，提出了柏拉圖立體多級裂變模型的思想：將三維模型的每個節(jié)點(diǎn)沿相關(guān)聯(lián)的邊移動一段距離后生成新的節(jié)點(diǎn)，三維模型的規(guī)模得到擴(kuò)大，使三維片上網(wǎng)絡(luò)規(guī)模的擴(kuò)大由一般的增加行或列的“加法”變成了從內(nèi)部生成新節(jié)點(diǎn)的“裂變”。本文將該模型裂變思想應(yīng)用于超立方體拓?fù)浣Y(jié)構(gòu)中。

2.2 超立方體拓?fù)浣Y(jié)構(gòu)簡介

三維片上網(wǎng)絡(luò)超立方拓?fù)浣Y(jié)構(gòu)具有對稱性好、可擴(kuò)展性高以及網(wǎng)絡(luò)直徑短等優(yōu)點(diǎn)[11]。三維超立方體節(jié)點(diǎn)數(shù)較少，應(yīng)用受到限制，而四維、五維等高維超立方體保持了良好的對稱性，節(jié)點(diǎn)數(shù)增多，應(yīng)用范圍擴(kuò)大，但是節(jié)點(diǎn)度數(shù)也隨之增加。在五維超立方體結(jié)構(gòu)中，包含32 個節(jié)點(diǎn)，80 條邊，每個節(jié)點(diǎn)的節(jié)點(diǎn)度數(shù)為5，如圖1所示。

Fig.1 Five-dimensional hypercube topology圖1 五維超立方體拓?fù)浣Y(jié)構(gòu)

2.3 超立方裂變拓?fù)浣Y(jié)構(gòu)的定義及生成

本文將三維模型裂變思想用于高維超立方體中，以五維超立方體為例，提出了五維超立方裂變拓?fù)浣Y(jié)構(gòu)，該拓?fù)浣Y(jié)構(gòu)既保留了超立方體拓?fù)浣Y(jié)構(gòu)原有的優(yōu)點(diǎn)，又解決了高維超立方體結(jié)構(gòu)的通訊瓶頸問題。

2.3.1 超立方裂變拓?fù)浣Y(jié)構(gòu)的定義

超立方體維度增加時，節(jié)點(diǎn)間連線數(shù)量急劇增加，路由算法復(fù)雜度也隨之增加。本文將三維模型裂變思想用到超立方體拓?fù)浣Y(jié)構(gòu)中。超立方裂變拓?fù)浣Y(jié)構(gòu)是由超立方體拓?fù)浣Y(jié)構(gòu)通過兩步生成的，第一步是“裂變”，第二步是“互連”。

2.3.2 超立方裂變拓?fù)浣Y(jié)構(gòu)的生成

三維片上網(wǎng)絡(luò)中的節(jié)點(diǎn)一般都包含一個路由器和固定數(shù)量的IP 核，IP 核一般是處理器中的功能部件，核之間通過路由器進(jìn)行路由通訊，以節(jié)點(diǎn)0 的裂變?yōu)槔f明超立方裂變拓?fù)浣Y(jié)構(gòu)的生成過程。將節(jié)點(diǎn)0裂變?yōu)?個子節(jié)點(diǎn)，分別編號00、01、02、03和04，然后順時針連接這5 個子節(jié)點(diǎn)，從而形成一個閉環(huán)，再將原節(jié)點(diǎn)0 刪除，這樣就形成了一個小的裂變簇。將剩下的31 個節(jié)點(diǎn)做同樣的處理，就形成了五維超立方的裂變拓?fù)浣Y(jié)構(gòu)。具體的裂變過程如圖2所示，其中的圓圈代表網(wǎng)絡(luò)節(jié)點(diǎn)。

Fig.2 Fission process of node 0圖2 節(jié)點(diǎn)0的裂變過程

裂變簇之間的連接過程如下，以0號節(jié)點(diǎn)對應(yīng)的裂變簇0為例，將裂變簇0中的子節(jié)點(diǎn)與其關(guān)聯(lián)的其余5個裂變簇中對應(yīng)的子節(jié)點(diǎn)用物理鏈路進(jìn)行連接，例如：節(jié)點(diǎn)00 與節(jié)點(diǎn)10、20、40、80 和160 進(jìn)行相連。于是便完成了裂變簇0 與其相關(guān)聯(lián)裂變簇之間的連接。裂變簇0 最終的連接結(jié)果如圖3 所示。對其余裂變簇中的子節(jié)點(diǎn)都進(jìn)行如上的操作，最后就形成了五維超立方裂變拓?fù)浣Y(jié)構(gòu)。

Fig.3 Connection relationship between node 0 and its associated fission nodes圖3 節(jié)點(diǎn)0及其關(guān)聯(lián)裂變節(jié)點(diǎn)的連接關(guān)系

2.4 超立方裂變拓?fù)浣Y(jié)構(gòu)與經(jīng)典拓?fù)浣Y(jié)構(gòu)對比

在相同節(jié)點(diǎn)數(shù)情況下，從網(wǎng)絡(luò)對分帶寬和最大節(jié)點(diǎn)度兩個方面，將高維超立方裂變拓?fù)浣Y(jié)構(gòu)與3D Mesh 的結(jié)構(gòu)特征進(jìn)行比較。首先，高維超立方裂變拓?fù)浣Y(jié)構(gòu)的對分帶寬明顯高于3D Mesh 結(jié)構(gòu)的對分帶寬。

以五維超立方裂變結(jié)構(gòu)為例：在160個節(jié)點(diǎn)規(guī)模情況下，五維超立方裂變拓?fù)浣Y(jié)構(gòu)的對分帶寬為80，而3D Mesh 結(jié)構(gòu)的對分帶寬為40，五維超立方裂變拓?fù)浣Y(jié)構(gòu)的對分帶寬恰好為3D Mesh 對分帶寬的2倍；其次，對最大節(jié)點(diǎn)度進(jìn)行對比，3D Mesh結(jié)構(gòu)的最大節(jié)點(diǎn)度為4，而高維超立方裂變拓?fù)浣Y(jié)構(gòu)的節(jié)點(diǎn)度為N+2。具體性能指標(biāo)對比如表1所示。

Table 1 Comparison of performance between hypercube fission topology and classical one表1 超立方裂變結(jié)構(gòu)與經(jīng)典結(jié)構(gòu)性能指標(biāo)對比

3 超立方裂變拓?fù)浣Y(jié)構(gòu)編碼和路由設(shè)計

3.1 節(jié)點(diǎn)編碼

考慮到存儲的占用，對于超立方裂變拓?fù)浣Y(jié)構(gòu)的編碼采用格雷碼編碼機(jī)制。高維超立方裂變拓?fù)浣Y(jié)構(gòu)中節(jié)點(diǎn)的編碼分為兩部分：簇內(nèi)編碼和簇外編碼。其中簇外編碼所占位數(shù)與簇個數(shù)的關(guān)系為：

其中，NoutCode為簇外編碼所占位數(shù)，NoutNode為簇個數(shù)。簇內(nèi)編碼所占位數(shù)與裂變節(jié)點(diǎn)個數(shù)的關(guān)系為：

其中，NinCode為簇內(nèi)編碼所占位數(shù)，NinNode為裂變節(jié)點(diǎn)個數(shù)。下面以五維超立方裂變拓?fù)浣Y(jié)構(gòu)為例說明高維超立方裂變拓?fù)浣Y(jié)構(gòu)編碼格式及路由算法。編碼分為兩步：首先，對五維超立方節(jié)點(diǎn)進(jìn)行編碼，每個超立方節(jié)點(diǎn)需要5 位編碼長度；其次，對裂變之后的子節(jié)點(diǎn)進(jìn)行編碼，由于一個裂變簇包含5 個子節(jié)點(diǎn)，因此每個子節(jié)點(diǎn)需要3位編碼長度。之后將兩步編碼進(jìn)行組合，將超立方節(jié)點(diǎn)編碼向左移3位再加上裂變簇的子節(jié)點(diǎn)3位編碼，組合之后形成的8位編碼就是五維超立方裂變拓?fù)浣Y(jié)構(gòu)中一個節(jié)點(diǎn)的編碼，其編碼方式如表2 所示。采用這種編碼方式能夠降低路由協(xié)議的復(fù)雜度，從而達(dá)到提高網(wǎng)絡(luò)性能，降低網(wǎng)絡(luò)延時的目的。

3.2 路由器結(jié)構(gòu)設(shè)計

在五維超立方裂變拓?fù)浣Y(jié)構(gòu)中，每個網(wǎng)絡(luò)節(jié)點(diǎn)中的路由器有7 個與之相鄰網(wǎng)絡(luò)節(jié)點(diǎn)連接的端口和若干個本地端口，本仿真實驗設(shè)計中每個節(jié)點(diǎn)搭載4個IP 核，故需要4 個本地端口，本地端口的一端與路由器相連，另一端與本地IP 核相連。每個端口包括輸入通道和輸出通道，每個通道可以從相連接的路由器或者IP核接收數(shù)據(jù)包或者發(fā)送數(shù)據(jù)包。其中每個物理通道又被劃分為多個虛通道，一般被劃分為2個、4 個或8 個，本仿真實驗選取4 個虛通道，以便有效地避免死鎖。路由器中包括路由邏輯、交換開關(guān)和虛通道仲裁單元等，通過路由算法把網(wǎng)絡(luò)節(jié)點(diǎn)接收的數(shù)據(jù)包發(fā)送到正確的輸出通道上，物理通道被各個虛通道采用輪轉(zhuǎn)法使用。高維超立方裂變拓?fù)浣Y(jié)構(gòu)的最大節(jié)點(diǎn)度數(shù)隨著維數(shù)的增加而增加，導(dǎo)致路由器結(jié)構(gòu)也隨節(jié)點(diǎn)度數(shù)的增加而變得更加復(fù)雜。

Table 2 Encoding of cluster 0 and its adjacent cluster表2 簇0及其相鄰簇編碼

3.3 路由算法設(shè)計

由于高維超立方裂變拓?fù)浣Y(jié)構(gòu)編碼的前半部分是裂變簇的編號，后半部分是簇內(nèi)節(jié)點(diǎn)的編號，因此路由算法的設(shè)計思路是先將數(shù)據(jù)包路由到目的裂變簇，等到數(shù)據(jù)包到達(dá)目的簇內(nèi)再對簇內(nèi)節(jié)點(diǎn)進(jìn)行路由，最后由目的節(jié)點(diǎn)將數(shù)據(jù)包發(fā)送到指定IP 核。參數(shù)dest是目標(biāo)地址，IPcoreBits是常數(shù)，表示的是IP核的編碼位數(shù)。具體路由算法如下：

步驟1當(dāng)超立方裂變拓?fù)浣Y(jié)構(gòu)中節(jié)點(diǎn)接收到數(shù)據(jù)包后，計算目的節(jié)點(diǎn)的路由地址destSwitch=dest＞＞IPcoreBits（取目的地址的路由位）。

步驟2判斷目的節(jié)點(diǎn)的路由地址與當(dāng)前路由地址是否相同（destSwitch和currSwitch是否相等），若相同則轉(zhuǎn)向步驟7，否則繼續(xù)執(zhí)行。

步驟3分別計算目的路由器和當(dāng)前路由器的簇內(nèi)地址和簇外地址。

步驟4判斷當(dāng)前的路由和目的路由是否在同一簇內(nèi)（flag=destCluster⊕currCluster，其中⊕為異或運(yùn)算符），若在同一簇內(nèi)（flag值為0），則繼續(xù)執(zhí)行，否則轉(zhuǎn)向步驟6。

步驟5根據(jù)當(dāng)前簇內(nèi)地址的值（currClusterInner）和目的簇內(nèi)地址的值（destClusterInner）進(jìn)行物理信道的選取，將數(shù)據(jù)包發(fā)送到相應(yīng)節(jié)點(diǎn)并將其節(jié)點(diǎn)地址更新為當(dāng)前節(jié)點(diǎn)currSwitch地址值，轉(zhuǎn)向步驟1。

步驟6將當(dāng)前路由簇地址值與目標(biāo)簇地址值從右起第一個不同的位置，記為m（m=destClusterInner⊕currClusterInner）。根據(jù)m的值設(shè)置物理信道，并將數(shù)據(jù)包發(fā)送到相應(yīng)的節(jié)點(diǎn)上，更新當(dāng)前節(jié)點(diǎn)currSwitch地址值，轉(zhuǎn)向步驟1。

步驟7數(shù)據(jù)包到達(dá)目標(biāo)節(jié)點(diǎn)，將數(shù)據(jù)包發(fā)送到對應(yīng)的IP核。

4 超立方體裂變拓?fù)浣Y(jié)構(gòu)性能仿真

4.1 仿真實驗設(shè)計

4.1.1 仿真平臺與實驗方案

本仿真實驗以美國Rochester 大學(xué)Hossain 等人研發(fā)的gpNoCsim[13]仿真平臺為基礎(chǔ)，并對其進(jìn)行了三維擴(kuò)充，實現(xiàn)了五維超立方裂變拓?fù)浣Y(jié)構(gòu)和3D Mesh 拓?fù)浣Y(jié)構(gòu)及路由算法仿真。根據(jù)仿真實驗結(jié)果，對兩種拓?fù)浣Y(jié)構(gòu)的吞吐量、平均延時和平均跳數(shù)進(jìn)行了對比分析。五維超立方裂變拓?fù)浣Y(jié)構(gòu)有160個網(wǎng)絡(luò)節(jié)點(diǎn)，由于需要比較的兩種結(jié)構(gòu)的規(guī)模應(yīng)該相同，因此將3D Mesh拓?fù)浣Y(jié)構(gòu)的網(wǎng)絡(luò)規(guī)模大小設(shè)置為8×4×5。每個網(wǎng)絡(luò)節(jié)點(diǎn)中路由器與4個IP核相連，故兩種拓?fù)浣Y(jié)構(gòu)搭載的IP 核數(shù)都是640 個。在本仿真實驗中，3D Mesh的路由算法采用XYZ路由算法[14-15]，而五維超立方裂變拓?fù)浣Y(jié)構(gòu)則采用3.3 節(jié)中所設(shè)計的路由算法。仿真實驗對于局部負(fù)載和均勻負(fù)載分別進(jìn)行了仿真實驗，均勻負(fù)載下，每個節(jié)點(diǎn)接收數(shù)據(jù)包的概率都相同；局部負(fù)載下，網(wǎng)絡(luò)中70%的數(shù)據(jù)包都在單個節(jié)點(diǎn)簇內(nèi)進(jìn)行流動，30%的數(shù)據(jù)包則隨機(jī)發(fā)送到簇外節(jié)點(diǎn)。

4.1.2 參數(shù)配置

GpNoCsim仿真器中主要的參數(shù)配置如下：虛擬通道數(shù)設(shè)置為4，每個緩存的微片數(shù)設(shè)置為4 flit，平均消息長度設(shè)置為160字節(jié)，微片長度設(shè)置為64位，IP核數(shù)設(shè)置為640，仿真實驗每次運(yùn)行20 000個時鐘周期，其中預(yù)熱期設(shè)置為10%，運(yùn)行次數(shù)設(shè)置為20。

4.2 吞吐量對比分析

4.2.1 均勻負(fù)載模式下的吞吐量對比分析

通過仿真實驗，在均勻負(fù)載模式下，得到了超立方裂變拓?fù)浣Y(jié)構(gòu)和3D Mesh 兩種拓?fù)浣Y(jié)構(gòu)的網(wǎng)絡(luò)吞吐量仿真實驗數(shù)據(jù)。五維超立方裂變拓?fù)浣Y(jié)構(gòu)和3D Mesh 兩種拓?fù)浣Y(jié)構(gòu)在均勻負(fù)載模式下吞吐量與注入率的關(guān)系曲線如圖4所示。

Fig.4 Contrast of throughput under uniform pattern圖4 均勻負(fù)載模式下吞吐量的對比

由圖4可見，當(dāng)注入率小于0.006時，在相同注入率下，兩種拓?fù)浣Y(jié)構(gòu)都沒有出現(xiàn)擁塞，吞吐量基本相同；當(dāng)注入率到達(dá)0.006時，3D Mesh拓?fù)浣Y(jié)構(gòu)首先出現(xiàn)了擁塞現(xiàn)象，說明其達(dá)到了飽和狀態(tài)，此時吞吐量為0.11；當(dāng)注入率達(dá)到0.016左右時，五維超立方裂變拓?fù)浣Y(jié)構(gòu)達(dá)到了飽和狀態(tài)，此時其吞吐量為0.28，3D Mesh 拓?fù)浣Y(jié)構(gòu)的吞吐量為0.07；五維超立方裂變拓?fù)浣Y(jié)構(gòu)達(dá)到飽和時的吞吐量比相同狀態(tài)下3D Mesh拓?fù)浣Y(jié)構(gòu)的吞吐量高300%。仿真實驗結(jié)果表明，五維超立方裂變拓?fù)浣Y(jié)構(gòu)在均勻負(fù)載模式下，吞吐量明顯高于3D Mesh拓?fù)浣Y(jié)構(gòu)的吞吐量。

4.2.2 局部負(fù)載模式下的吞吐量對比分析

在局部負(fù)載下，得到了五維超立方裂變拓?fù)浣Y(jié)構(gòu)和3D Mesh 兩種拓?fù)浣Y(jié)構(gòu)的網(wǎng)絡(luò)吞吐量與注入率關(guān)系的仿真實驗數(shù)據(jù)，如圖5所示。

Fig.5 Contrast of throughput under localized pattern圖5 局部負(fù)載模式下吞吐量的對比

由圖5可知，當(dāng)注入率小于0.013時，在同樣的注入率下，兩種拓?fù)浣Y(jié)構(gòu)的局部負(fù)載吞吐量相差很小；當(dāng)注入率達(dá)到0.013時，3D Mesh網(wǎng)絡(luò)達(dá)到飽和狀態(tài)，此時吞吐量為0.28，繼續(xù)增大注入率，則其吞吐量開始降低，這是由于發(fā)生了網(wǎng)絡(luò)堵塞；而五維超立方裂變拓?fù)浣Y(jié)構(gòu)的吞吐量在仿真實驗范圍內(nèi)未出現(xiàn)飽和狀態(tài)。

4.3 平均延時對比分析

4.3.1 均勻負(fù)載模式下平均延時對比分析

由仿真實驗數(shù)據(jù)得到了超立方裂變拓?fù)浣Y(jié)構(gòu)和3D Mesh 在均勻負(fù)載下平均延時與注入率之間的關(guān)系曲線，如圖6所示。

Fig.6 Contrast of average latency under uniform pattern圖6 均勻負(fù)載下平均延時對比

由圖6可知，在均勻負(fù)載下，當(dāng)注入率大于0.005時，相對于五維超立方裂變拓?fù)浣Y(jié)構(gòu)，3D Mesh 拓?fù)浣Y(jié)構(gòu)的平均延時有一個階梯式的增長，而隨著注入率的增加，這種差距更加明顯。這是由于當(dāng)注入率不斷增加時，3D Mesh網(wǎng)絡(luò)中的靠外層的節(jié)點(diǎn)數(shù)量不足，使得信息無法傳遞到里層節(jié)點(diǎn)，導(dǎo)致了網(wǎng)絡(luò)阻塞，從而需要大量的時間去處理；當(dāng)注入率增長到0.012 時，五維超立方裂變拓?fù)浣Y(jié)構(gòu)平均延時出現(xiàn)了上升的趨勢，此時五維超立方裂變拓?fù)浣Y(jié)構(gòu)的平均延時比3D Mesh拓?fù)浣Y(jié)構(gòu)低85.1%。

4.3.2 局部負(fù)載模式下平均延時對比分析

由仿真實驗數(shù)據(jù)得到了五維超立方裂變拓?fù)浣Y(jié)構(gòu)與3D Mesh拓?fù)浣Y(jié)構(gòu)在局部負(fù)載模式下，平均延時與注入率之間的關(guān)系曲線，如圖7所示。

Fig.7 Contrast of average latency under localized pattern圖7 局部負(fù)載下平均延時的對比

由圖7可知，在局部負(fù)載下，當(dāng)注入率小于0.013時，五維超立方裂變拓?fù)浣Y(jié)構(gòu)和3D Mesh拓?fù)浣Y(jié)構(gòu)的平均延時都較小，且基本一致；當(dāng)注入率達(dá)到0.014～0.016 區(qū)間時，3D Mesh 拓?fù)浣Y(jié)構(gòu)的平均延時呈現(xiàn)階梯式增長，從注入率達(dá)到0.014開始，3D Mesh拓?fù)浣Y(jié)構(gòu)就逐漸達(dá)到了飽和狀態(tài)；當(dāng)注入率達(dá)到0.016 時，五維超立方裂變拓?fù)浣Y(jié)構(gòu)的平均延時比3D Mesh 拓?fù)浣Y(jié)構(gòu)的平均延時低79.1%。

4.4 平均跳數(shù)對比分析

4.4.1 均勻負(fù)載模式下平均跳數(shù)對比分析

由仿真實驗得到了均勻負(fù)載下，五維超立方裂變拓?fù)浣Y(jié)構(gòu)網(wǎng)絡(luò)和3D Mesh 拓?fù)浣Y(jié)構(gòu)網(wǎng)絡(luò)的接收數(shù)據(jù)包總數(shù)和平均跳數(shù)的數(shù)據(jù)，如表3所示。

Table 3 Contrast under uniform pattern表3 均勻負(fù)載模式下的對比

由表3可知，在均勻負(fù)載下，當(dāng)注入率小于0.007時，五維超立方裂變拓?fù)浣Y(jié)構(gòu)和3D Mesh拓?fù)浣Y(jié)構(gòu)接收包總數(shù)都呈線性增長；當(dāng)注入率達(dá)到0.007 附近時，3D Mesh 拓?fù)浣Y(jié)構(gòu)達(dá)到飽和，五維超立方裂變拓?fù)浣Y(jié)構(gòu)在仿真實驗數(shù)據(jù)范圍內(nèi)沒有達(dá)到飽和；當(dāng)注入率超過0.007時，由于網(wǎng)絡(luò)堵塞，3D Mesh出現(xiàn)大量丟包現(xiàn)象，五維超立方裂變拓?fù)浣Y(jié)構(gòu)的平均跳數(shù)比3D Mesh拓?fù)浣Y(jié)構(gòu)少21.5%。

4.4.2 局部負(fù)載模式下平均跳數(shù)對比分析

由仿真實驗得到了局部負(fù)載下，五維超立方裂變拓?fù)浣Y(jié)構(gòu)網(wǎng)絡(luò)和3D Mesh 拓?fù)浣Y(jié)構(gòu)網(wǎng)絡(luò)的接收數(shù)據(jù)包總數(shù)和平均跳數(shù)的數(shù)據(jù)，如表4所示。

Table 4 Contrast under localized pattern表4 局部負(fù)載模式下的對比

根據(jù)仿真實驗數(shù)據(jù)可知，在局部負(fù)載下，注入率小于0.015時，兩種網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)接收包數(shù)呈線性增長；而當(dāng)注入率達(dá)到0.016 時，3D 拓?fù)浣Y(jié)構(gòu)開始出現(xiàn)大量丟包現(xiàn)象，而五維超立方裂變拓?fù)浣Y(jié)構(gòu)則仍然保持線性增長，五維超立方裂變拓?fù)浣Y(jié)構(gòu)的平均跳數(shù)比3D Mesh少13.3%。

5 結(jié)束語

基于高維超立方拓?fù)浣Y(jié)構(gòu)的片上網(wǎng)絡(luò)布局和連線都很復(fù)雜，節(jié)點(diǎn)度數(shù)隨著維數(shù)的增加而增加，網(wǎng)絡(luò)通訊性能隨之下降。為了解決這一瓶頸問題，本文對超立方片上網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)進(jìn)行了改造，提出一種三維片上網(wǎng)絡(luò)新型拓?fù)浣Y(jié)構(gòu)——三維片上網(wǎng)絡(luò)五維超立方裂變拓?fù)浣Y(jié)構(gòu)。與相同規(guī)模的超立方網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)進(jìn)行了比較，五維超立方裂變拓?fù)浣Y(jié)構(gòu)在保留超立方網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)優(yōu)點(diǎn)的同時，連線更少、更規(guī)則。但是高維超立方裂變拓?fù)浣Y(jié)構(gòu)相對于3D Mesh 拓?fù)浣Y(jié)構(gòu)來說物理鏈路較為復(fù)雜，在實際生產(chǎn)芯片時，需要對芯片網(wǎng)絡(luò)布線技術(shù)有一定的要求。仿真實驗結(jié)果表明，本文提出的三維片上網(wǎng)絡(luò)五維超立方裂變拓?fù)浣Y(jié)構(gòu)與經(jīng)典3D Mesh網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)相比，具有更大的吞吐量、更大的網(wǎng)絡(luò)流量及更低的平均延時。