硅通孔負載全局均衡的3D NoC延遲上界優(yōu)化方法

王曉蕾　胡　巧　杜高明　張多利　歐陽一鳴

(合肥工業(yè)大學微電子設計研究所, 合肥 230009)(合肥工業(yè)大學教育部IC設計網(wǎng)上合作研究中心, 合肥 230009)

三維集成技術日漸成熟,以它為基礎的三維片上網(wǎng)絡(3D NoC)成為片上網(wǎng)絡領域研究中的主要方向[1-2]．與二維片上網(wǎng)絡(NoC)相比,3D NoC具有全局互連短、封裝密度高、體積小等優(yōu)勢,在降低芯片功耗的同時提高了網(wǎng)絡的平均通信性能[3]．

對于NoC上的實時應用而言,不僅需要保證其平均通信性能,而且需要保證最差情形(如網(wǎng)絡擁塞時)下的通信性能．但由于窮舉、仿真等方法耗時耗力,且無法得到有效延遲上界,因此片上網(wǎng)絡延遲上界研究成為NoC研究中的難點之一．李洋[4]針對不同業(yè)務,在確保網(wǎng)絡服務質量的基礎上分析優(yōu)化了網(wǎng)絡的通信延遲．Ahmed等[5]提出了一種新型的LA-XYZ路由算法．虞瀟等[6]提出了一種面向功耗的免死鎖三維全動態(tài)3D NoC路由算法,通過引入三維空間中6個方向的功耗比較,實現(xiàn)三維全動態(tài)路由功能,大大降低了整個系統(tǒng)的功耗．上述文獻通過改進路由算法來優(yōu)化通訊延遲、吞吐量和功耗等,取得了較好的效果,但是其考慮的延遲為平均延遲,而在很多領域,最差性能時延才是產(chǎn)品性能和可靠性的關鍵保障．

錢悅等[7]對比分析了k-ary-2-mesh網(wǎng)絡及其對應的三維網(wǎng)絡在最差情形下的通信性能,發(fā)現(xiàn)三維網(wǎng)絡的平均通信性能雖然更優(yōu),但受垂直信道影響,其最差情形下的通信性能可能劣于其對應的二維網(wǎng)絡,且指出垂直通道(即硅通孔)是影響性能(如延遲上界)的關鍵因素,但未提出解決方案．文獻[8]采用一種沖突矩陣來表征網(wǎng)絡的擁堵情況,提出了一種二維片上網(wǎng)絡延遲上界的分析方法,但所用沖突矩陣復雜度高,對沖突的表達不夠直觀．

針對上述問題,本文提出了一種硅通孔負載全局均衡的3D NoC延遲上界優(yōu)化方法．根據(jù)低復雜度的基于度的沖突矩陣,采用硅通孔負載全局均衡的3D NoC延遲上界優(yōu)化方法,優(yōu)化業(yè)務流延遲上界,提升網(wǎng)絡性能．

1　問題描述

1.1　垂直鏈路特殊性問題

圖1為4×3×3大小的3D-NoC結構示意圖．主體為二維網(wǎng)格結構,分為3層,每層包含4×3個節(jié)點,每個節(jié)點包含路由節(jié)點和計算節(jié)點．其中,每個路由節(jié)點最多由東(E)、南(S)、西(W)、北(N)、上(U)、下(D)和本地(L)7個通道組成,上下通道采用TSV進行通信[9],其余通道采用片上互連線．

TSV成品率隨著TSV數(shù)目的增多而顯著降低．圖1中TSV數(shù)量相對較少,成品率較高．但對于更大的網(wǎng)絡規(guī)模,TSV需求較多,成品率會顯著下降,垂直帶寬可能會成為3D-NoC的通訊瓶頸．因此,進行性能分析時必須考慮垂直鏈路特殊性．

圖1　3D-NoC結構示意圖

1.2　業(yè)務流沖突

目前,基于片上網(wǎng)絡的性能分析方法大多采用比較簡單的路由算法,例如單路采用XY方式、隨機路由等．這些路由算法設計簡單,資源消耗較小,但是數(shù)據(jù)在網(wǎng)絡傳輸效率較低,擁塞情況嚴重,會導致延遲上界增大、存儲緩存空間增大、局部熱點等問題[10]．

圖2給出了一個簡化的3×3×3大小的三維網(wǎng)格．將節(jié)點分別標記為v1～v27．圖中共有f1,f2兩條業(yè)務流,且f1，f2均流向同一個目的節(jié)點v26．若采用單路徑路由,則業(yè)務流沖突明顯,網(wǎng)路延遲較大．針對此問題,本文對業(yè)務流采取全拆分策略,以分散負載,分析業(yè)務流延遲上界,優(yōu)化網(wǎng)絡性能．

圖2　3×3×3結構的多路徑路由示意圖

2　硅通孔負載全局均衡的延遲上界優(yōu)化方法

基于廣泛采用的三維網(wǎng)絡結構NoC,研究硅通孔負載全局均衡的3D NoC延遲上界優(yōu)化方法,建立三維坐標系,其中X方向和Y方向為水平平面方向,Z方向為垂直方向,并且Z方向為硅通孔的抽象．

3D NoC中目標流定義為所需要研究的業(yè)務流,沖突流定義為對目標流造成沖突的業(yè)務流,子流為全拆分情況下所產(chǎn)生的所有子流．全拆分是指在每個路由節(jié)點都進行拆分,且業(yè)務流拆分后可能方向上的流量是均勻的,規(guī)定業(yè)務流在源節(jié)點未拆分時的流量總和為1．網(wǎng)絡中的業(yè)務流采用最小多路徑路由的傳輸方式,即業(yè)務流從源節(jié)點到目的節(jié)點經(jīng)過路由節(jié)點最少的路徑．

2.1　優(yōu)化步驟

以網(wǎng)絡演算工具[8,11]為網(wǎng)絡性能模型分析基礎,提出硅通孔負載全局均衡的3D NoC延遲上界優(yōu)化方法．圖3為該優(yōu)化方法流程圖,根據(jù)該流程圖完成三維片上網(wǎng)絡的延遲上界優(yōu)化問題．

圖3　硅通孔負載全局均衡的3D NoC延遲上界優(yōu)化方　 　 法流程圖

2.2　路徑搜索

采用業(yè)務流均勻拆分策略,搜索整個網(wǎng)絡,找出網(wǎng)絡中所有業(yè)務流的源節(jié)點和目的節(jié)點之間所有可行路徑．從源節(jié)點開始,在X,Y,Z三個方向上開始拆分,給定每個方向的業(yè)務流拆分比,即節(jié)點拆分比．業(yè)務流流經(jīng)所有節(jié)點的節(jié)點拆分比的乘積即為鏈路拆分比．定義每條子流的到達曲線為主流到達曲線乘以該子流的鏈路拆分比．

以圖2網(wǎng)絡中的2條流f1,f2為例,f1從源節(jié)點v2流向目的節(jié)點v26,f2從源節(jié)點v5流向目的節(jié)點v26．進行業(yè)務流全拆分時,首先優(yōu)化業(yè)務流f1,將其設為目標流,則f2為沖突流．采用樹的遍歷算法分別搜索業(yè)務流f1,f2源節(jié)點到目的節(jié)點的所有可行路徑．如圖4所示,目標流f1共有6條可行路徑,沖突流f2共有3條可行路徑,每條路徑對應1條子流,目標子流與沖突子流經(jīng)過相同的鏈路節(jié)點,即目標流和沖突流在路徑1,2,3上產(chǎn)生沖突．

(a)f1(目標流)

(b)f1可行路徑

(c)f2(沖突流)

(d)f2可行路徑

圖4路徑搜索

2.3　基于度的矩陣

2.3.1基于度的鄰接矩陣

通過樹的遍歷算法,不僅能夠求出每條業(yè)務流所有子流的到達曲線,也可得到每條子流需要流經(jīng)的所有鏈路．由此便可推出每條子流在每條鏈路上的節(jié)點拆分比,得到業(yè)務流基于度的鄰接矩陣．

對于圖1中的三維片上網(wǎng)絡結構,網(wǎng)絡中路由節(jié)點的度為6,即網(wǎng)絡中的節(jié)點最多和6個方向的節(jié)點相鄰,分別為東(E)、西(W)、南(S)、北(N)、上(U)、下(D)．按上述方向順序,鄰接矩陣的每一列對應一個方向,建立基于度的鄰接矩陣Asi,di為

(1)

式中,si,di分別為業(yè)務流i的源節(jié)點和目的節(jié)點;v為網(wǎng)絡的路由節(jié)點總數(shù);w為網(wǎng)絡中路由節(jié)點的度;pmn為業(yè)務流i在第m個節(jié)點n方向上的節(jié)點拆分比,且

(2)

式中,pav為該業(yè)務流到達路由節(jié)點v的所有拆分比之和;pv_w為該業(yè)務流在節(jié)點v的w方向上的流量與該業(yè)務流從節(jié)點v流出的總流量的比值．

2.3.2基于度的沖突矩陣

通過基于度的鄰接矩陣建立基于度的沖突矩陣,以表征網(wǎng)絡的沖突情況．若網(wǎng)絡中存在k條業(yè)務流,則每條業(yè)務流都有一個屬于自己的鄰接矩陣．遍歷所有業(yè)務流,可得到整個網(wǎng)絡的業(yè)務流分配信息．定義目標流l基于度的沖突矩陣Csl,dl為

(As1,d1+As2,d2+…+Ask,dk)∧Asl,dl-Asl,dl

(3)

式中,cmn為路由節(jié)點m指向n方向的相鄰節(jié)點的路徑鏈路沖突系數(shù),利用鏈路沖突系數(shù)可以描述整個網(wǎng)絡中的路徑?jīng)_突大小;∧運算定義為

假設矩陣A,B均為2×2大小的矩陣,且

則有

(4)

圖2中沖突流f2源節(jié)點為v5,其在節(jié)點v5上的總拆分比為1．在節(jié)點v5進行均勻拆分,則北(N)和上(U)方向的拆分比均為0.5．采用最小多路徑路由方式,沖突流f2在節(jié)點v8處只能流向上(U)方向,因此,沖突流在節(jié)點v8的U方向上拆分比為0.5．同理可得其他節(jié)點的拆分比．定義業(yè)務流在不經(jīng)過節(jié)點方向上的拆分比為0,便可得出該沖突流基于度的鄰接矩陣,如圖5(a)所示．根據(jù)式(3),進而得到基于度的沖突矩陣,如圖5(b)所示．

圖5基于度的沖突矩陣實例

2.4　TSV沖突系數(shù)

由已得的沖突矩陣,依次求出每條目標子流的TSV沖突系數(shù)．以圖5(b)中的沖突矩陣為例,對于目標流f1,它共有6條子流．路徑1經(jīng)過2條TSV鏈路,即v8→v17和v17→v26,這2條鏈路在目標流基于度的沖突矩陣中分別對應于節(jié)點v8的上(U)方向和節(jié)點v17的上(U)方向．而在沖突矩陣中,這2個位置的元素值分別為0.50和0.75,因此可以得到2條鏈路的TSV沖突系數(shù)分別為0.50和0.75．選擇較大的數(shù)值,得出路徑1的TSV沖突系數(shù)為0.75．同理可以求出其余5條鏈路的TSV沖突系數(shù),即路徑2～路徑6的TSV沖突系數(shù)分別為0.50,0.75, 0.75, 0.25和0．

2.5　業(yè)務流流量新分配

得到每條目標子流對應的TSV沖突系數(shù)后,選擇TSV沖突系數(shù)最小的路徑作為最優(yōu)路徑,其次為次優(yōu)路徑,以此類推．按照路徑的TSV沖突系數(shù)大小把目標流的流量分配到部分最優(yōu)路徑上,沖突系數(shù)大的路徑流量分配少,沖突系數(shù)小路徑流量分配多．此例中路徑6的TSV沖突系數(shù)最小為0,對應路徑為最優(yōu)路徑,路徑5為次優(yōu)路徑,以此類推,路徑3和路徑4的TSV沖突系數(shù)相同且都為最大值,因而對應路徑均為最差路徑．由此可知,目標流流量按路徑v2→v11→v20→v23→v26分配,其余路徑不分配流量．

由此便可完成目標流f1的優(yōu)化．隨后,變換目標流,將業(yè)務流f2作為目標流,根據(jù)圖3對f2進行優(yōu)化．本例中,優(yōu)化業(yè)務流f1后,業(yè)務流f2中所有子流的TSV沖突系數(shù)都為0,已經(jīng)是最優(yōu)路徑,故無需進行流量再分配．

2.6　算法復雜度分析

假設子流fp經(jīng)過的節(jié)點總數(shù)為j,網(wǎng)絡中所有業(yè)務流(包括沖突流和目標流)經(jīng)過的節(jié)點總數(shù)為r,則計算單條目標子流的等價服務曲線的時間復雜度為O((j(j+1)/2)r)．設h為目標子流數(shù),則計算目標流的延遲上界的時間復雜度為O(h(j(j+1)/2)r)．

3　實驗結果及分析

3.1　參數(shù)設置

通過實驗驗證3D NoC中延遲上界與業(yè)務流拆分比的關系,證明所提方法的正確性和有效性．

以SoCLib[12]中的DSPIN片上網(wǎng)絡為基礎,搭建了一個3×3×3大小的3D NoC仿真模型(見圖6)．網(wǎng)絡中所有路由器是統(tǒng)一的,具有相同的服務性能．設路由節(jié)點均提供延遲-速率函數(shù)的服務曲線β(t)=0.33(t-3)+,其中t表示時間．該服務曲線表示路由節(jié)點每3個時鐘周期轉發(fā)1個微包,路由器進行路由轉發(fā)時有3個時鐘周期的最大處理延遲．配置網(wǎng)絡中的流發(fā)包器每40個周期發(fā)送4個微包,且這4個數(shù)據(jù)包是被連續(xù)發(fā)送的．根據(jù)漏桶模型[8],目標流和沖突流都滿足到達曲線α(t)=0.1t+3.7．設該3D NoC中有3條業(yè)務流,業(yè)務流f1為目標流,則f2和f3為沖突流,目標流和沖突流都采用全拆分策略．

圖6　3×3×3三維片上網(wǎng)絡目標流優(yōu)化示例

3.2　延遲與業(yè)務流拆分比的關系

3.2.1延遲與沖突流拆分比的關系

采用控制變量法,將目標流拆分比設為固定值,設目標流X方向拆分比為0.3,Y,Z方向拆分比分別為0.3和0.4,實驗結果見圖7．其中,沖突流在X,Y,Z方向的流量總拆分比為1．

圖7　延遲與沖突流拆分比的關系

由圖7可知,當X方向拆分比或Y方向拆分比為0,或者兩者都為0時,目標流延遲上界較小;當它們均不為0時,目標流延遲上界較大,但比較穩(wěn)定．X方向拆分比和Y方向拆分比變化時,延遲上界變化較小,即在沖突流全拆分情況下,延遲上界對拆分比不敏感．

3.2.2延遲與目標流拆分比例的關系

固定沖突流的拆分比,設X,Y方向拆分比均為0.3,Z方向拆分比為0.4,實驗結果見圖8．

圖8　延遲與目標流拆分比的關系

由圖8可知,當目標流X,Y方向拆分比至少有一個為0時,目標流延遲上界較?。擷,Y方向拆分比均不為0時,目標流延遲上界較大,但較穩(wěn)定．當X,Y方向拆分比總和為1時,延遲上界偏大,這是因為此時Z方向拆分比為0,所有目標子流通過同一條TSV通道,加大了此通道的負擔,同時此TSV通道的沖突也較大,導致延遲上界偏大．

3.3　模擬分析

對圖9中目標流f1進行優(yōu)化．假設對于每個路由節(jié)點,非優(yōu)化情況下目標流X,Y方向拆分比都為0.3,Z方向拆分比為0.4．對于優(yōu)化和非優(yōu)化情況,沖突流X方向拆分比設為0.1．

圖9　目標流f1的子流

采用樹的遍歷法搜索目標流和沖突流中每一條子路徑,得到?jīng)_突流f2共包含90條子流,沖突流f3共包含6條子流,目標流共包含12條子流,搜索路徑見圖6,具體路徑見圖9．根據(jù)TSV沖突系數(shù)分配目標流流量,改變沖突流Y方向上的拆分比,分析利用本文方法優(yōu)化前、后的延遲上界,結果見圖10和圖11．

圖10　優(yōu)化對比實驗

圖11　優(yōu)化效率

由圖10和圖11可知,對于任意的沖突流Y方向拆分比,優(yōu)化后的延遲上界均小于優(yōu)化前的延遲上界．但是對于不同的沖突流Y方向拆分比,利用本文方法對延遲上界的優(yōu)化效果卻差別很大．這是因為不同的沖突流Y方向拆分比會得到不同的TSV沖突系數(shù),導致每次選擇的流量分配路徑不相同,從而產(chǎn)生不同的優(yōu)化效果．實驗結果表明,利用本文方法對延遲上界優(yōu)化效果明顯,且最大延遲上界優(yōu)化了58.9%．

3.4　算法性能比較

與文獻[8]中方法相比,本文方法的主要優(yōu)勢在于:① 利用網(wǎng)絡演算將2D NoC拓展到3D NoC．② 提出的基于度的沖突矩陣不僅能直觀地表現(xiàn)網(wǎng)絡的沖突狀態(tài),還能大大降低空間存儲復雜度．以3×3×3大小的網(wǎng)絡為例,利用文獻[8]中的沖突矩陣,最多需要使用(3×3×3)2=729個元素來表現(xiàn)網(wǎng)絡中的沖突狀態(tài),而本文方法只需要使用(3×3×3)×6=162個元素,所占存儲空間僅為原沖突矩陣的22.2%,存儲復雜度從O(n2)降為O(n),大大減少了所需的存儲空間．

4　結語

1) 針對3D NoC中的硅通孔特殊結構,提出一種負載全局均衡的3D NoC延遲上界優(yōu)化方法．

2) 所提的基于度的沖突矩陣可以清晰直觀地表現(xiàn)出業(yè)務流在網(wǎng)絡中的沖突情況．對于3×3×3大小的網(wǎng)絡,采用基于度的沖突矩陣可將存儲空間降低為文獻[8]中沖突矩陣的22.2%,存儲復雜度從O(n2)降為O(n)．

3) 實驗結果表明,采用硅通孔負載全局均衡的3D NoC延遲上界優(yōu)化方法可以有效減少傳輸延遲、優(yōu)化業(yè)遲上界,最大的優(yōu)化效果將延遲上界減小了58.9%．

參考文獻(References)

[1] Gaur M S, Laxmi V, Zwolinski M, et al. Network-on-chip: Current issues and challenges[C]//2015IEEEComputerSociety,InternationalSymposiumonVlSIDesignandTest. Ahmedabad, India, 2015:1-3.

[2] Katabami H, Saito H, Yoneda T. Design of a GALS-NoC using soft-cores on FPGAs[C]//2013IEEE7thInternationalSymposiumonEmbeddedMulticoreSocs. Tokyo, Japan, 2013:31-36. DOI:10.1109/mcsoc.2013.35.

[3] Khayambashi M, Yaghini P M, Eghbal A, et al. Analytical reliability analysis of 3D NoC under TSV failure[J].JEmergTechnolComputSyst, 2015,11(4): 1-16. DOI:10.1145/2700236.

[4] 李洋. 基于QoS保證的2D-mesh片上網(wǎng)絡延時評價與性能優(yōu)化研究[D]. 長春:吉林大學通信工程學院,2015.

[5] Ahmed A B, Abdallah A B. LA-XYZ: Low latency, high throughput look-ahead routing algorithm for 3D network-on-chip (3D-NoC) architecture[C]//2012IEEEInternationalSymposiumonEmbeddedMulticoreSoCs. Aizu-Wakamatsu, Japan, 2012:167-174. DOI:10.1109/mcsoc.2012.24.

[6] 虞瀟,李麗,張宇昂,等.一種面向功耗免死鎖三維全動態(tài)3D NoC路由算法[J]. 電子學報,2013,41(2):329-334. DOI: 10.3969/j.issn.0372-2112.2013.02.019.

Yu Xiao, Li Li, Zhang Yu’ang, et al. A power-aware dead lock avoid three-dimensional full-adaptive routing algorithm for 3D NoC[J].ActaElectronicaSinica, 2013,41(2):329-334.DOI: 10.3969/j.issn.0372-2112.2013.02.019.(in Chinese)

[7] 錢悅,魯中海,竇強,等. 片上網(wǎng)絡二維和三維結構的通信性能分析[J].計算機工程與科學, 2011, 33(3):34-40.DOI: 10.3969/j.issn.1007-130X.2011.03.007.

Qian Yue, Lu Zhonghai, Dou Qiang, et al. Communication performance analysis of the NoCs in 2D and 3D architectures[J].ComputerEngineering&Science, 2011,33(3):34-40. DOI: 10.3969/j.issn.1007-130X.2011.03.007.(in Chinese)

[8] Du G, Zhang C, Lu Z, et al. Worst-case performance analysis of 2-D mesh NoCs using multi-path minimal routing[C]//ACMInternationalConferenceonHardware/SoftwareCodesignandSystemSynthesis. Tampere, Finland, 2012:123-132. DOI:10.1145/2380445.2380469.

[9] 歐陽一鳴,袁吳鈴,梁華國,等. 3D NoC的冗余雙向TSV容錯設計[J].電子測量與儀器學報,2013,27(4):326-333.DOI:10.3724/SP.J.1187.2013.00326.

Ouyang Yiming, Yuan Wuling, Liang Huaguo, et al. Fault-tolerant design of redundant bidirectional TSV on 3D NoC[J].JournalofElectronicMeasurement&Instrument, 2013,27(4):326-333. DOI:10.3724/SP.J.1187.2013.00326.(in Chinese)

[10] 秦光. 多路徑路由網(wǎng)絡負載均衡算法研究[J]. 計算機仿真, 2011, 28(11):118-121.DOI:10.3969/j.issn.1006-9348.2011.11.028.

Qin Guang. Research of load balance algorithm over multipath network[J].ComputerSimulation, 2011,28(11):118-121. DOI:10.3969/j.issn.1006-9348.2011.11.028.(in Chinese)

[11] Viswanathan N, Paramasivam K, Somasundaram K. Performance comparison of 3D NoC topologies using network calculus[J].LifeScienceJournal, 2013,10(3):4379-4385.

[12] SoClib. Soclib simulation environment [EB/OL]. (2016-10-31)[2018-01-18]. http://soclib.lip6.fr/.