面向低功耗的片上網絡虛通道分配算法

周 芳 吳 寧 周 磊 張 穎

(南京航空航天大學電子信息工程學院,南京 210016)

針對復雜MPSoC系統(tǒng)中互連結構所帶來的吞吐量高、信號不完整以及時鐘難以同步等問題,將宏觀網絡的概念應用于MPSoC設計中,形成了一種全新的集成電路通信結構——片上網絡(network on chip,NoC).在NoC設計中,虛通道技術可在保證傳輸延時性能的同時有效地節(jié)約緩存,但過多的虛通道會帶來巨大的面積和功耗開銷[1-2].因此,設計時須考慮如何合理地分配虛通道資源.

早期的NoC研究側重于其體系結構的研究,因而虛通道的分配多采用平均分配策略,即向NoC中各路由器的所有輸入通道都分配相同個數的虛通道[3-7].而在面向特定應用的NoC中,節(jié)點與節(jié)點之間的通信流量并不均衡,如果仍采用平均分配策略,就不能最大程度地利用虛通道技術來減少傳輸延時和節(jié)約緩存.因此,可考慮采用非平均分配策略來優(yōu)化虛通道的分配[8-10]:在通信流量小的節(jié)點輸入通道上分配較少的虛通道;反之,則分配較多的虛通道.其中,文獻[8]基于貪婪算法,通過計算輸入端口帶寬利用率,進行虛通道分配.文獻[9]則是基于網絡通信特征來分配虛通道的.這些算法實現簡單,但在分配過程中僅從單個輸入通道的角度來考慮,并未兼顧到網絡整體情況,因此分配效率相對較低.文獻[10]采用遺傳算法的思想來實現虛通道分配,但該算法對新空間的探索能力有限,容易早熟收斂到局部最優(yōu)解.

本文運用排隊論理論將虛通道分配問題轉化為一個數學問題,建立了一種2D mesh結構片上網絡通信數學模型,用以估算網絡中數據包的平均傳輸延時,并以此為約束條件,采用模擬退火算法來實現虛通道分配.該算法可以在滿足傳輸延時性能要求的同時,對虛通道進行合理分配,通過提高虛通道利用率來減少虛通道總數目,從而降低系統(tǒng)的總功耗.最后,利用熱點通信流量下的多組仿真實驗,對這種優(yōu)化分配算法的有效性進行了驗證,并給出了精確的評估結果.

1 虛通道分配

在NoC設計中,虛通道技術的實現方式如圖1(b)所示.

圖1 輸入端口虛通道的實現方式

在設計過程中,如果要求輸入端的緩存大小為16個微片時,可采用單通道方式串行排列16個緩存;也可采用虛通道方式,按4×4(即設置4條虛通道,每條虛通道的緩存深度為4)或2×8 的方式排列.一方面,虛通道數目的增加,會提高網絡性能;另一方面,受到緩存資源總數的限制,隨虛通道數目的增加,緩存深度相應減小,導致來自同一個數據包的微片分散于幾個路由節(jié)點中,從而加劇了節(jié)點的擁塞和數據包傳輸延遲現象.此外,虛通道數目還會直接影響片上網絡的總功耗.文獻[3]指出,當數據包注入率為2%,數據包微片寬度為8,虛通道深度為2時,增加1條虛通道,功耗會相應增加大約5 mW.本文設計的NoC路由單元門級電路功耗模型如下[2]:

Prouter=3.6+1.78ψbuffer+5.82ψvc+0.468ψfit

式中,ψbuffer為虛通道緩存深度;ψvc為虛通道數目;ψfit為數據包微片寬度.由此可知,降低片上網絡功耗的有效途徑之一是在保證網絡延時性能的同時減少虛通道數目.

1.1 虛通道分配的問題描述

虛通道分配的思想是:針對特定的應用,已知網絡的拓撲結構和路由算法,考慮如何在保證網絡傳輸延時性能的同時,最小化路由單元各通道的虛通道數目,從而達到降低NoC整體功耗的目標.由于片上網絡的數據包傳輸是一個動態(tài)過程,難以精確預測其傳輸延時,故針對特定的應用,可選擇網絡中所有數據流的平均延時作為約束條件.

已知條件:特定應用的節(jié)點間通信量、網絡拓撲結構及路由算法.

約束條件:TN≤Tmax,其中TN為網絡中所有數據流的平均延時,Tmax為網絡中所允許的最大平均延時.

優(yōu)化目標:min(N).

1.2 NoC路由器的數學模型

片上網絡中數據包的傳輸具有動態(tài)特性,傳輸延時與網絡結構、路由算法及節(jié)點間通信流量等因素有關.為了較為精確地計算傳輸延時,可采用排隊論方法構建片上網絡的數學通信模型.

一個面向片上網絡的特定應用通常由多個數據流構成,片上網絡的平均傳輸延時即為這些數據流延時的平均值,故平均傳輸延時可表示為

(1)

式中,m為特定應用中數據流個數;TLi為第i個數據流中的數據包在片上網絡中的傳輸延時.計算TLi時可以由該數據流的源節(jié)點出發(fā),沿傳輸路徑遞推到目的節(jié)點,計算所經各路由節(jié)點 (x,y)的z方向輸入緩沖區(qū)阻塞延遲時間Bx,y,z和數據包微片頭在源節(jié)點的等待時間WSi,最后得到該數據流在片上網絡中的傳輸延時,即

式中,Tb表示一個微片無阻塞地通過路由節(jié)點的時間;d表示數據包從源節(jié)點到目的節(jié)點所經過的跳數;M表示數據包微片長度.

由此可知,計算傳輸延時的關鍵是計算阻塞延遲時間Bx,y,z和源節(jié)點的等待時間WSi.其中,Bx,y,z可由下式計算得到:

Bx,y,z=θx,y,zωx,y,z

(3)

式中,θx,y,z，ωx,y,z分別為數據包被阻塞在路由節(jié)點(x,y)的z方向緩沖區(qū)的概率和等待時間.為計算等待時間ωx,y,z,可將路由節(jié)點的每一輸入通道都視為1個隊列,根據排隊論可以得到

(4)

式中,Sx,y,z，λx,y,z分別為數據包在路由節(jié)點(x,y)的z方向上的平均服務時間和達到率.λx,y,z的計算公式如下:

(5)

Sx,y,z的計算可參考圖2.在采用虛通道技術的NoC中,同一個數據包的微片會同時存在于多個路由節(jié)點中,傳輸延時的計算應從包頭進入傳輸鏈路開始,直到最后一個微片離開該鏈路結束,具體過程如圖2所示.

圖2 數據包傳輸延時示意圖

由圖2可知,假設數據包由源節(jié)點1傳輸至目的節(jié)點6,數據包長度為6個微片,路由節(jié)點的虛通道緩存深度為2.數據包由源節(jié)點出發(fā),當數據包中所有微片都離開源節(jié)點時,包頭微片還未到達目的節(jié)點,此時數據包的平均服務時間受到鏈路上所有下游節(jié)點的影響(圖2(a)中下游節(jié)點是路由節(jié)點3,4,5,6).當數據包尾部還未離開路由節(jié)點4時,包頭微片已經進入目的節(jié)點,故影響數據包服務時間的路由節(jié)點應固定為節(jié)點4,5,6.因此,第j個路由節(jié)點的平均服務時間為

(6)

式中,Bl為數據包經過下游節(jié)點l時的緩沖區(qū)阻塞延遲時間;Aj為影響平均服務時間的下游路由節(jié)點個數,具體可以表示為

(7)

式中,H為虛通道緩存深度.

計算θx,y,z時,首先需要計算轉發(fā)概率矩陣F.以4×4的2維網格結構為例,其轉發(fā)概率矩陣為

(8)

式中,fzz′表示數據包由z方向轉發(fā)至z′方向的轉發(fā)概率,具體可由下式計算:

(9)

式中,λzz′表示路由節(jié)點中從z方向輸入,轉發(fā)至z′方向的數據包達到率.

設置z方向為東,并以此為例計算θx,y,z,即

θx,y,E=fENPx,y+1,S+fESPx,y-1,N+fEWPx-1,y,W+fELθx,y,L

(10)

式中,Px,y,z為路由節(jié)點(x,y)中轉發(fā)到z方向上緩沖區(qū)被占用的概率.對于采用虛擬通道技術的路由節(jié)點,Px,y,z的取值與虛擬通道數以及虛擬通道分配機制有關.而在采用非平均分配虛通道策略的片上網絡中,則可考慮為所有虛通道均被占用的概率,即

Px,y,z=(λx,y,zSx,y,z)Vx,y,z

(11)

在計算源節(jié)點的平均等待時間時,可把源節(jié)點中的虛通道模擬為一個隊列模型,即

式中,TR為網絡延時;λx,y,L為從源節(jié)點輸入到網絡的數據包到達率.

2 虛通道分配算法

模擬退火算法(simulated annealing,SA)是一種通用的概率元啟發(fā)式算法.在解決全局優(yōu)化問題時,如果搜索空間是離散的,則可應用模擬退火算法在解空間中隨機定位目標函數的全局最優(yōu)解.對于某些問題,模擬退火算法可能比窮舉迭代法更有效.目前,該算法已在工程領域中得到廣泛應用[11].

為了在片上網絡虛通道分配過程中應用模擬退火算法,必須確定以下參數:狀態(tài)空間、優(yōu)化的目標函數、新解空間產生方法、接受概率函數、退火時間表溫度和初始溫度.這些參數的選擇會對算法的有效性產生顯著影響.基于模擬退火算法進行虛通道優(yōu)化分配的步驟如下:

① 初始化.設初始溫度T=100,初始解狀態(tài)V為所有隨機產生的虛通道個數Vx,y,z組成的三維數組,且Vx,y,z≤4.每個T值的迭代次數L=1 000.

③ 計算新解空間V′下的平均傳輸延時TN(V′).若TN(V′)滿足約束條件,即TN(V′)≤Tmax,則保留該新解空間V′;否則轉到步驟③,再次生成新解空間V′.

④ 計算增量Δt=N(V′)-N(V),其中優(yōu)化目標函數N(V)表示虛通道總數.

⑤ 若Δt<0,則設V′為新的當前解;否則以概率exp(-Δt/T)接受V′為新的當前解.

⑥ 重復步驟②～⑤L次.如果連續(xù)若干個新解都沒有被接受,則輸出當前解為最優(yōu)解,結束程序.

⑦ 降低溫度T,并判斷其是否為0.若為0,則結束算法;否則轉步驟②.為了保證算法具有合適的收斂速度,并能搜索到全局最優(yōu)解,根據已有的研究經驗,這里設置溫度T以0.95的衰減速度逐漸減少,并趨向于0.

3 實驗結果與分析

本文算法采用C++語言實現.為了驗證算法的有效性,根據虛通道分配結果,采用Verilog HDL語言完成NoC的RTL級設計,并基于SMIC 0.18 μm工藝庫,利用Design Compiler軟件進行綜合.綜合得到的門級網表通過VCS仿真驗證,并在Prime Time PX軟件中進行功耗分析.

實驗中使用的主要參數設置如下:片上網絡結構為4×4的2D mesh結構;路由算法為XY固定路由算法；數據包微片長度為8；Tb=4，即路由單元在無阻塞情況下,傳輸一個微片需要4個時鐘周期.

實驗中需要對節(jié)點間的數據包流量進行設置.本文選取了熱點流量(hotspot traffic)方式來驗證優(yōu)化算法的有效性:分別設置節(jié)點(2,2)和(1,1)為熱點,即它們收到數據包的概率是其他節(jié)點的2倍.每個節(jié)點以相同的注入率λ發(fā)送數據包.調整注入率的大小,由仿真平臺采集到對應的數據包延時.在每組實驗中共計發(fā)送大約1×105個數據包,為了避免采集到網絡不穩(wěn)定時的包延時,將前1×104個數據包的延時數據丟棄.此外,還可以面向特定應用,由固定的源節(jié)點向固定的目的節(jié)點發(fā)送特定數量的數據包,以驗證算法的有效性.

采用熱點流量方式時,不同的注入率下平均分配算法與本文算法的延遲性能比較結果見圖3.由圖可知,隨著注入率的增加,2種分配算法所導致的數據包平均傳輸延時均增加.但在同一注入率下,采用平均分配算法時的傳輸延時略小于本文算法.這是由于平均分配時,路由節(jié)點的每個輸入端口都分配有4個虛通道;而采用本文算法時,每個輸入端口的虛通道數目可能小于等于4,從而導致數據包的平均傳輸延時增加.由于本文以數據包的平均傳輸延時作為約束條件,因此傳輸延遲并沒有受到很大影響,尤其在注入率比較小的情況下,2種分配算法所導致的傳輸延時基本一致.

圖3 不同注入率下傳輸延遲性能比較

不同注入率下,平均分配算法與本文算法的功耗性能比較結果見圖4.由圖可知,隨著注入率的增加,2種分配算法所導致的片上網絡功耗均增加;但在同一注入率下,采用本文算法時功耗普遍低于平均分配算法.當節(jié)點注入率為0.016數據包/周期時,相比平均分配算法,采用本文算法可降低功耗2.3%,此時的優(yōu)化效果最差;當節(jié)點注入率為0.006數據包/周期時,功耗可降低14.9%,此時優(yōu)化效果最佳.此外,隨著注入率的降低,本文算法對功耗的優(yōu)化效果更加明顯.這是因為注入率較低時,虛通道的利用率也較低,此時可在保證延時性能的前提下,采用優(yōu)化算法來減少虛通道數目,因此具有更大的優(yōu)化空間.

圖4 不同注入率下功耗性能比較

4 結語

針對2D網格結構NoC的通信特點,本文提出了一種面向功耗的虛通道分配算法.對于特定應用的片上網絡,以傳輸延時為約束條件,尋求最優(yōu)虛通道分配和最小化虛通道總數,以達到降低功耗的目標.利用熱點通信流量下的多組仿真實驗來驗證該算法的性能.實驗結果表明,在保證傳輸延時性能的同時,本文算法可合理地分配虛通道資源,有效減少虛通道總數,相比平均分配算法可降低系統(tǒng)功耗2.3%～14.9%.此外,該算法還可推廣至其他拓撲結構和其他路由算法下的虛通道分配問題中.

)

[1]洪佳杰.高性能低功耗片上網絡設計中的功耗與延時模型研究[D].南京:南京航空航天大學信息科學與技術學院,2010.

[2]段振華.可重構的片上網絡功耗建模與優(yōu)化[D].南京:南京航空航天大學電子信息工程學院,2011.

[3]Mostafa R, Hamid S. The effect of virtual channel organization on the performance of interconnection net-

works [C]//Proceedingsofthe19thIEEEInternationalParallelandDistributedProcessingSymposium. Denver, Colorado,USA, 2005: 26-31.

[4]Mullins R, West A, Moore S. Low-latency virtual-channel routers for on-chip networks [J].ACMSIGARCHComputerArchitectureNews, 2004,32(2): 188-197.

[5]Rahmani A M, Daneshtalab M, AfzaliKusha A, et al. Forecasting-based dynamic virtual channels allocation for power optimization of network-on-chips[C]//Proceedingsofthe22ndInternationalConferenceonVLSIDesign. New Delhi, India, 2009: 151-156.

[6]Mirza-Aghatabar M, Koohi S, Hessabi S, et al. An adaptive approach to manage the number of virtual channels[C]//Proceedingsofthe22ndInternationalConferenceonAdvancedInformationNetworkingandApplications. Ginowan, Japan, 2008: 353-358.

[7]Hu J, Ogras U Y, Marculescu R. System level buffer allocation for application specific networks-on-chip router design [J].IEEETransactionsonComputer-AidedDesignofIntegratedCircuitsandSystems, 2006,25(12): 2919-2933.

[8]Ting H, Umit Y O, Radu M. Virtual channels planning for networks-on-chip [C]//Proceedingsofthe8thInternationalSymposiumonQualityElectronicDesign. San Jose, Costa Rica, 2007: 879-884.

[9]王力緯,曹陽,李曉輝,等. 片上網絡虛通道分配算法[J]. 華中科技大學學報:自然科學版, 2009, 37(3): 54-57.

Wang Liwei, Cao Yang, Li Xiaohui, et al. Virtual channel allocation algorithm for network-on-chips[J].JournalofHuazhongUniversityofScienceandTechnology:NaturalScienceEdition, 2009,37(3): 54-57. (in Chinese)

[10]李曉輝,曹陽,王力緯,等. 基于遺傳算法的片上網絡虛通道分配算法[J]. 華中科技大學學報:自然科學版, 2010, 38(3): 42-45.

Li Xiaohui, Cao Yang, Wang Liwei, et al. Genetic algorithm-based virtual channel allocation of network-on-chips[J].JournalofHuazhongUniversityofScienceandTechnology:NaturalScienceEdition, 2010,38(3): 42-45. (in Chinese)

[11]Rutenbar R. Simulated annealing algorithms: an overview[J].IEEECircuitsandDevicesMagazine, 1989(5): 19-26.