面向非全互連3D NoC 的自適應單播路由算法

孫美東，劉勤讓，劉冬培，燕昺昊

(國家數字交換系統工程技術研究中心，鄭州450002)

(*通信作者電子郵箱137070845@qq．com)

0 引言

在3D集成系統中，使用垂直互連技術將多層晶片堆疊在一起［1］。因為硅通孔(Through Silicon Via，TSV)技術能提供最大的垂直互連密度和最小的層間距離，所以它是目前使用最普及的垂直互連技術［2］。雖然在集成系統中使用三維片上網絡(three-Dimensional Network-on-Chip，3D NoC)架構可以提高網絡性能，但TSV的使用仍面臨3個問題:1)TSV的制造工藝還不夠成熟，使得3D集成電路成品率較低［3］;2)在3D集成電路封裝以及焊接TSV過程中，TSV可能出現短路導致故障［4］;3)相對于普通的2D水平鏈路，TSV有較大的面積消耗［5］。所以在保證正常通信的前提下，應使TSV的數量盡可能減少，這使得非全互連3D NoC架構得到廣泛研究。

對于3D NoC，路由算法是十分關鍵的問題之一，前人在這一問題上已經作出相關的研究。如文獻［6］提出LAFT(Look Ahead Fault Tolerant)算法，此算法分為三個階段:第一階段，讀取微片(flit)，計算下一節點的地址;第二階段，得到由故障模塊發送的下一節點的故障信息并且獲取其他三個方向的最短路徑;第三階段，做出路由方向的決定，其中最短路徑的方向具有最高優先級。由于LAFT規定路徑選擇性為第二優先級，所以如果選取路徑選擇性多的方向，但此方向上的下一節點出現多處故障，此時會導致路徑堵塞，使傳輸不能選擇最短路徑。針對上述現象，文獻［7］提出HLAFT(Hybrid Look Ahead Fault Tolerant)算法，對于每一個到來的flit，該算法判斷計算的方向是否導致路徑堵塞。如果因為路徑堵塞而選擇非最短路徑，則會根據當前節點和鄰居節點的狀態重新計算輸出端口。HLAFT算法可以避免路徑堵塞，然而只適用于全互連的3D NoC。DyXYZ(Dynamic XYZ)路由算法在X、Y、Z方向分別使用4、4、2個虛通道，將網絡分成2個主網絡，每個主網絡又包含4個次網絡［8］。因為每個次網絡采用不同的虛通道，所以此算法不會死鎖。當選擇輸出通道時，DyXYZ算法考慮輸出方向上的緩存信息，進一步提高網絡性能，但此算法同樣也只適用于全互連的3D NoC架構且算法共采用10個虛通道，增加了網絡的硬件開銷。

文獻［9］和文獻［3］分別提出適用于非全互連不規則3D NoC架構的Elevator-First路由算法和路由器結構，該算法采用2個虛通道避免死鎖。由于虛通道的使用過于耗費資源，文獻［10］對Elevator-First算法進行改進，當選擇“電梯”節點時，增加限制規則，使得不用虛通道就可以避免死鎖。基于TSV上/下表的容錯路由算法通過在每個路由器中添加TSV上/下表尋找最優的TSV進行層間傳輸;此外，為了高效地更新路由表，每個路由器會額外存儲一張連接表［11］，但由于該算法中的TSV上/下表需要存儲每層所有TSV的地址，且還要額外存儲一張連接表，使得表開銷過大，并且當擴大網絡規模時，表的開銷呈劇烈的增長。針對TSV上/下表開銷過大的問題，低開銷容錯路由算法提出新的表策略，但此算法并未考慮垂直方向的擁塞信息［12］。因此，本文針對文獻［11］表開銷過大以及文獻［12］出現的垂直擁塞問題，提出新的表結構和路由算法，該算法不僅能避讓故障和擁塞節點，而且可以進行死鎖恢復和免活鎖，保證了有效的數據傳輸。

1 非全互連3D拓撲結構

非全互連3D拓撲結構層內采用2D mesh結構，且每層的規模相同，其與3D mesh結構不同的是TSV的分布是部分且隨機的。該結構中具有兩類路由器:三維路由器和平面路由器。含有TSV的路由器被稱為三維路由器，具有7個端口，分別為本地、東、西、南、北、上、下方向的端口。其余的路由器稱為平面路由器，具有五個端口，分別為本地、東、西、南、北方向的端口。上述的拓撲結構模型如圖1所示，每個路由器的位置由三維笛卡爾坐標表示。

圖1 非全互連3D拓撲模型Fig．1 Vertically partially connected 3D topology model

2 記錄表的設計

在非全互連的3D NoC中，上/下層傳輸的數據包要選取最合適的垂直連接，所以記錄垂直連接的位置信息顯得尤為重要。本文與文獻［11］和文獻［12］中設計的表結構不同，此表將TSV上/下表整合到一個表中，不僅記錄與當前路由器4個方向距離最近的TSV位置信息，也記錄相鄰節點的緩存占用和故障信息。在傳輸數據包時可以選擇無故障且緩存占用少的端口，減少擁塞的情況和傳輸時間，提高網絡性能。圖1中(1，1，1)節點的記錄表如表1所示。如果當前路由器連接的鏈路或路由器故障，在表中用信號0表示;如果可用，用信號1表示。本文設置路由器輸入端口的緩存深度為8 flits。

表1 節點(1，1，1)存儲的記錄表Tab．1 Record table stored by node(1，1，1)

2．1 記錄表的建立

記錄表是由路由器發送廣播數據包建立的，其中每個廣播包會存儲自身在網絡中傳輸的跳數。表建立的過程分為兩步:第一步是層間廣播，由偶數層三維路由器向上/下層廣播帶有自身輸入緩存占用信息的數據包，奇數層三維路由器收到數據包后會記錄緩存信息同時向偶數層返回自身的輸入緩存占用信息，此時三維路由器都具有鄰近層的輸入緩存占用信息。第二步是層內廣播，三維路由器將緩存信息加入到數據包中向層內4個方向發送廣播包，接收到的路由器會向其返回輸入緩存信息。如果接收到的路由器記錄表中沒有TSV地址，則將包中的TSV地址和相應的緩存信息加入到記錄表中;如果已有TSV地址，選擇跳數比表中記錄更小的廣播包進行更新TSV地址和相應的緩存。為了減少數據包的重傳，當收到兩個相同的數據包會選擇一個丟掉。

1) even layer 3D routers broadcast packets;

2) if(routers←packets) /*收到廣播包*/

3) record and return buffer;

4) plane routers broadcast packets;

5) if(routers←packets)

6) record and return buffer;

7) if(record table is blank‖TSV address is smaller)

/*記錄表的TSV地址為空或數據包中攜帶的TSV地址較小*/

8) update table;

9) end if

10) hop+1，broadcast packets;

/*廣播包的跳數加1，繼續向層內其他方向廣播*/

11) end if

12) end if

2．2 記錄表的更新

通常，三維片上網絡系統中出現的故障分為短暫性故障和永久性故障［13］，當發生故障時，永久性故障相比短暫性故障會更大程度地影響系統性能，所以本文考慮的故障是永久性故障。在三維片上網絡系統中出現的故障模型主要有以下兩種:

1)路由器故障。三維路由器故障，如圖1中的(3，3，1)路由器故障;平面路由器故障，如圖1中的(2，1，1)路由器故障。

2)鏈路故障。層內鏈路故障，如圖1中的(1，1，1)路由器西方向故障;層間鏈路故障，如圖1中的(3，2，1)路由器下垂直連接故障。

當鏈路或路由器故障時，由檢測到故障的路由器發送與建立記錄表時相同的廣播包進行記錄表的更新。為達到增量更新減少更新開銷，此過程只修改需要更新的表項。表更新過程與建立過程相似，這里不再贅述。

3 自適應單播路由算法

3D NoC中的路由算法是將數據包按照一定的路徑從源節點準確無誤地傳輸到目的節點，本文提出的層內和層間路由算法中主要符號和含義如表2所示。

表2 路由算法中主要符號及含義Tab．2 Main symbols and meanings in routing algorithm

3．1 層內路由算法

基于記錄表中的信息，本文提出一種新的層內路由算法。首先根據當前節點和目的節點的地址確定最優方向，然后判斷當前節點的故障信息，如最優方向故障則選取非最優方向，如果兩個非最優方向的故障信息相同則進一步考慮端口的緩存信息，使得數據包可以選擇無故障輸出端口且避免擁塞。由于發生故障的連接會比發生擁塞的連接更易影響網絡的性能，所以本文將判斷故障信息的優先級設為最高，擁塞的優先級次之。

1) if(ΔX=0＆＆ ΔY=0)

2) local port←packet;

3) else if(ΔX=0)

4) N or S is available，N or S← packet;otherwise，check W and E;check W and E adjacent routers; /*N或S可用，選擇相應端口;否則，檢查W和E方向的故障，同時檢查W和E可用方向鄰近路由器的故障信息*/

5) if(one of W and E is faulty) /*兩個方向其一故障*/

6) W or E←packet; /*選取無故障端口*/

7) else if(W and E are faulty)

8) N or S←packet; /*選擇目標方向相反的端口*/

9) else(W and E aren’t faulty)

10) adjacent routers are available in target direction，less buffer W or E ← packet;otherwise，less faulty port← packet;/*兩個鄰近路由器在所需方向上可用，選擇W或E緩存占用少的端口;兩個鄰近路由器在所需方向上故障不同，選擇故障少的方向*/

11) else if(ΔY=0)

12) 處理方式同上;

13)else(ΔX≠0 ＆＆ ΔY≠0)

14) check 2 target direction and adiacent routers; /*檢查與目標方向距離最近兩個方向的故障信息，同時檢查這兩個方向鄰近路由器的故障信息*/

15)if(one of them is faulty)

16) no faulty port←packet;

17)else if(they are faulty)

18) opposite port←packet;

19)else(they aren’t faulty)

20) adjacent routers are available， less buffer port← packet;otherwise， less faulty port← packet;

3．2 層間路由算法

當目的節點與源節點不在同層時，要先將數據包傳輸到目的節點層，然后再傳輸到目的節點。在層間傳輸時，選擇最優的垂直連接是關鍵，所以在尋找最優垂直連接時，層間路由算法將擁塞和故障信息同時考慮。本文將目的節點映射到源節點所在層的節點稱為映射節點。如果映射節點自身含有需要的TSV，那么選擇此TSV進行傳輸;否則，根據映射節點的記錄表，計算源節點與各個TSV的信息進而選擇出最優的TSV，將數據包傳輸到鄰近層，然后根據目的節點地址繼續在層內傳輸。如果此層仍不是目的層，則采用同樣的方法繼續傳輸。源節點與各個TSV的信息計算方法為:

其中:dis表示源節點與映射節點記錄表中各個TSV的距離，選擇最小距離的TSV可以減少傳輸延時;interbuff表示TSV連接的鄰近層路由器上/下輸入端口的緩存占用信息，選擇緩存占用最少的端口可以緩解網絡的擁塞;Info值越小表示選擇的TSV地址越優，可以作為最優的傳輸路徑進行傳輸。

1) if(Zd＞Zc)

2) Xm=Xd;Ym=Yd;Zm=Zc;

3) if(M has TSV) /*映射節點含有需要的TSV*/

4) temporary address← TSV，inner-layer routing;/*選擇此TSV，采用層內路由進行傳輸*/

5) else

6) calculate TSV，temporary address← TSV，inner-layer

routing;

7) else if(Zd＜Zc)

8) 處理方式同上;

9) else

10) intra-layer routing;

由上所述，本文提出的自適應單播路由算法在當前節點選擇最佳的輸出端口后，在接下來的路由器中循環執行判斷邏輯，所以該算法的時間復雜度為O(N)，N為網絡中每一維的節點數目。

3．3 死鎖恢復與免活鎖

在三維片上網絡架構中采用自適應路由算法很可能會引起死鎖。如圖1 所示，當節點(1，0，1)向節點(1，0，0)發送數據包，同時節點(2，0，0)向節點(2，0，1)發送數據包，兩條傳輸路徑相互占用資源，形成死鎖。本文采用RAB(Random-Access-Buffer)［7］進行死鎖恢復。在沒有死鎖的情況下采用FIFO緩存管理機制，一旦檢測到死鎖，RAB會放棄緩存中正在執行的請求，尋找允許的請求進行緩存釋放，進而打破死鎖恢復網絡狀態。

因為本文考慮網絡中的擁塞和故障信息，使得數據包在傳輸時，由于多次避免擁塞和故障的節點導致活鎖現象發生。所以本文采用跳數限制避免活鎖，具體方法是如果數據包記錄的跳數超過設定的閾值，本文算法對路徑的選擇將只進行故障的判斷，從而避免了活鎖。

4 實驗仿真

4．1 數據包設計

根據記錄表中的內容和路由算法的特性，本文設計出對應的數據包結構，如圖2所示。其中數據包分為兩類:1)單播包，用來進行數據傳輸;2)廣播包，用來建立和更新記錄表。本文采用蟲孔路由器，數據傳輸的最小單位是微片，微片大小為32 b。路由器根據前2 b進行頭微片、體微片和尾微片的類型區分，其中頭微片帶有跳數和目的地址等信息，體微片和尾微片攜帶傳輸的數據。當網絡出現故障時，及時更新記錄表可以減少傳輸延時和功耗開銷，所以用于更新記錄表的廣播包具有比單播包更高的優先級，因此用第3 b代表包的優先級(Pri):1代表高優先級;0代表低優先級。Temp字段為1代表數據包包含臨時目的地址，Temp為0代表數據包包含真實目的地址。Hop字段記錄數據包在網絡中傳輸的跳數，大小為7 b。Xd、Yd、Zd分別代表目的地址的X、Y、Z軸坐標，因為設定拓撲結構為32×32×32，所以每一維的坐標需要用5 b表示。其中Hop和坐標地址所需的位數根據拓撲結構大小而相應地改變。Ext字段可供以后進行擴展來使用。

圖2 數據包結構Fig．2 Packet structure

4．2 性能仿真分析

本文采用臺灣大學開發的Access Noxim開源仿真器進行網絡性能仿真，它將 Noxim和 HopSpot結合，使得 Access Noxim支持網絡模型、功率模型和熱模型的3D NoC仿真。

為了說明算法的性能，實驗將算法應用到不同規模的網絡結構，并且采用了兩種流量模型進行目的地址的選擇。由于文獻［9］和文獻［11］使用兩個虛通道避免死鎖，為了實驗的公平起見，本實驗使用RAB死鎖恢復機制代替虛通道。

表3 實驗參數設置Tab．3 Setting of experimental parameters

4．2．1 網絡平均延時

在不同的數據包注入率下，4種算法在不同網絡規模下的平均延時如圖3和圖4所示。單個數據包的延時是指數據包的頭微片進入網絡到目的節點接收尾微片的這段時間。平均延時是指多個數據包延時的平均值。數據包注入率是指每個IP核在每個時鐘周期下向網絡中注入數據包的速度。

在Random流量模型下，由于本文考慮到各輸入端口的緩存占用信息，在傳輸數據包時會判斷選擇最優路徑，所以在注入率較低時，平均延時高于文獻［9］和文獻［11］的算法。但在兩種網絡規模下，當注入率分別大于0．028和0．02時，由于文獻［9］和文獻［11］算法只考慮水平和垂直連接的故障，導致擁塞的情況發生，所以平均延時高于本文算法。文獻［12］和本文的平均延時情況很接近，原因是它也同樣考慮了層內緩存占用信息。

圖3 4×4×4網絡規模下的平均延時Fig．3 Average delay under 4×4×4 network size

圖4 6×6×6網絡規模下的平均延時Fig．4 Average delay under 6×6×6 network size

在Shuffle流量模型下，文獻［9］和文獻［11］算法在 4×4×4網絡規模并且注入率大于0．015時，平均延時均高于本文算法。文獻［12］算法在注入率小于0．016時依舊與本文有著接近的平均延時，但在注入率大于0．016后，平均延時高于本文。這是因為Shuffle流量模型以層間傳輸數據包為主，本文額外考慮了垂直方向的緩存占用信息，當注入過多的數據包時，可以減少層間傳輸的擁塞情況，使得平均延時低于文獻［12］算法。6×6×6網絡規模下的情況與上述類似，但因為網絡規模的增加，所有算法的平均延時都有所增加。

4．2．2 網絡吞吐率

吞吐率是指網絡接收或發送消息的速率，實驗以flit為網絡中基本傳輸單位，所以吞吐率的大小可以用每個節點在每個時鐘周期下傳輸的flit數量來衡量。吞吐率的理論計算公式如下:

其中:Throughput指網絡吞吐率，吞吐率越高表明網絡可以處理的數據包越多;Nrouter指網絡中節點的數量，與網絡規模有關;T指實驗的仿真時間;PN指在T時間內成功到達目的節點的數據包總數;Lengthi指第i個數據包的大小(包含flit的數量)。

圖5和圖6為在兩種網絡規模下4種算法的吞吐率比較。

圖5 4×4×4網絡規模下的吞吐率Fig．5 Throughput under 4×4×4 network size

可以看出隨著注入率的增加，本文算法比文獻［9］、文獻［11］和文獻［12］算法都有優勢，在Random流量模型下本文算法的優勢并不明顯，但在Shuffle流量模型下本文的吞吐率較其他三個算法有明顯的優勢。其原因是各節點的緩存使用率隨著數據包注入率的增加而逐漸提高，對于以層間數據包傳輸為主的Shuffle流量模型，本文算法不會因為避讓故障而導致某一層或某一節點發生擁塞。

另外由于文獻［9］算法選擇的TSV地址直接從寄存器中讀取，當存儲的TSV發生故障，即便有可用的TSV也無法進行層間傳輸，導致網絡提前趨于飽和，在兩種流量模型下的吞吐率均低于其他三個算法。

4．2．3 可靠性

數據包的丟棄是因為傳輸路徑中的TSV故障或網絡中的資源不足，因此可以用丟包率衡量算法的可靠性。本文計算了兩種網絡規模下算法的丟包率，結果如圖7所示。

圖6 6×6×6網絡規模下的吞吐率Fig．6 Throughput under 6×6×6 network size

圖7 兩種網絡規模下的丟包率Fig．7 Rate of losing packet under two network sizes

文獻［12］和文獻［11］算法由于沒考慮垂直方向的緩存，當層間傳輸發生擁塞時，便會丟棄數據包。文獻［9］算法在傳輸數據包時靜態地選擇TSV，所以當TSV發生故障，文獻［9］算法不得不丟棄數據包，而且隨著故障率的增加，數據包的丟棄變得越來越頻繁。本文算法通過綜合考慮記錄表中的信息，躲避了故障的連接并緩解了擁塞的情況，在故障率為5%時，兩種網絡模型下的丟包率分別為2．4%和2．8%;在故障率為50%時，丟包率分別為25．5%和29．5%。

4．3 記錄表的開銷分析

根據本文記錄表的結構，保存記錄表所需寄存器大小的計算公式如下:

其中:Regbit表示寄存器的大小;fault表示鏈路或路由器是否故障，需要1 b;intrabuff表示層內鄰節點緩存占用信息;interbuff已在式(1)中介紹;本文設置緩存深度為8 flit，所以intrabuff和interbuff均需要3 b;pc表示節點的坐標信息;hop表示當前節點到TSV的跳數，其中根據網絡規模的不同，pc和hop需要的位數也不同。

表4給出了具體網絡規模下保存記錄表所需的硬件開銷。在層內網絡規模為N×N時，文獻［11］的硬件開銷為2N2;文獻［12］的硬件開銷為24 lb N+8;本文的硬件開銷為24 lb N+48。由上述可知，隨著網絡規模的增加，文獻［11］的表開銷呈劇烈的增長，而文獻［12］和本文的表開銷增長緩慢。

表4 記錄表的硬件開銷Tab．4 Hardware overhead of record table

5 結語

本文主要針對非全互連3D NoC的拓撲結構提出基于記錄表的自適應單播路由算法。該表不僅記錄了TSV的位置信息也記錄了緩存占用和故障信息，而且在較大的網絡規模下比文獻［11］算法的表開銷要小得多;仿真實驗結果表明，本文算法的可靠性優于其他三個算法，并且在平均延時和吞吐率性能指標上均有一定的優勢。尤其在Shuffle流量模型下，當注入率高于0．02時，本文算法的網絡還沒有達到飽和，而其他兩個算法的網絡趨于飽和狀態。當層內網絡規模小于8×8時，本文算法的表開銷過大，這是本文算法的不足。為了進一步提高非全互連3D NoC的網絡性能，表結構的優化以及非全互連3D NoC的多播路由算法都是以后需要解決的問題。