面向低功耗的片上網(wǎng)絡(luò)虛通道分配算法

周 芳 吳 寧 周 磊 張 穎

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

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

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

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

1 虛通道分配

在NoC設(shè)計(jì)中,虛通道技術(shù)的實(shí)現(xiàn)方式如圖1(b)所示.

圖1 輸入端口虛通道的實(shí)現(xiàn)方式

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

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

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

1.1 虛通道分配的問(wèn)題描述

虛通道分配的思想是:針對(duì)特定的應(yīng)用,已知網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)和路由算法,考慮如何在保證網(wǎng)絡(luò)傳輸延時(shí)性能的同時(shí),最小化路由單元各通道的虛通道數(shù)目,從而達(dá)到降低NoC整體功耗的目標(biāo).由于片上網(wǎng)絡(luò)的數(shù)據(jù)包傳輸是一個(gè)動(dòng)態(tài)過(guò)程,難以精確預(yù)測(cè)其傳輸延時(shí),故針對(duì)特定的應(yīng)用,可選擇網(wǎng)絡(luò)中所有數(shù)據(jù)流的平均延時(shí)作為約束條件.

已知條件:特定應(yīng)用的節(jié)點(diǎn)間通信量、網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)及路由算法.

約束條件:TN≤Tmax,其中TN為網(wǎng)絡(luò)中所有數(shù)據(jù)流的平均延時(shí),Tmax為網(wǎng)絡(luò)中所允許的最大平均延時(shí).

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

1.2 NoC路由器的數(shù)學(xué)模型

片上網(wǎng)絡(luò)中數(shù)據(jù)包的傳輸具有動(dòng)態(tài)特性,傳輸延時(shí)與網(wǎng)絡(luò)結(jié)構(gòu)、路由算法及節(jié)點(diǎn)間通信流量等因素有關(guān).為了較為精確地計(jì)算傳輸延時(shí),可采用排隊(duì)論方法構(gòu)建片上網(wǎng)絡(luò)的數(shù)學(xué)通信模型.

一個(gè)面向片上網(wǎng)絡(luò)的特定應(yīng)用通常由多個(gè)數(shù)據(jù)流構(gòu)成,片上網(wǎng)絡(luò)的平均傳輸延時(shí)即為這些數(shù)據(jù)流延時(shí)的平均值,故平均傳輸延時(shí)可表示為

(1)

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

式中,Tb表示一個(gè)微片無(wú)阻塞地通過(guò)路由節(jié)點(diǎn)的時(shí)間;d表示數(shù)據(jù)包從源節(jié)點(diǎn)到目的節(jié)點(diǎn)所經(jīng)過(guò)的跳數(shù);M表示數(shù)據(jù)包微片長(zhǎng)度.

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

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

(3)

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

(4)

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

(5)

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

圖2 數(shù)據(jù)包傳輸延時(shí)示意圖

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

(6)

式中,Bl為數(shù)據(jù)包經(jīng)過(guò)下游節(jié)點(diǎn)l時(shí)的緩沖區(qū)阻塞延遲時(shí)間;Aj為影響平均服務(wù)時(shí)間的下游路由節(jié)點(diǎn)個(gè)數(shù),具體可以表示為

(7)

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

計(jì)算θx,y,z時(shí),首先需要計(jì)算轉(zhuǎn)發(fā)概率矩陣F.以4×4的2維網(wǎng)格結(jié)構(gòu)為例,其轉(zhuǎn)發(fā)概率矩陣為

(8)

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

(9)

式中,λzz′表示路由節(jié)點(diǎn)中從z方向輸入,轉(zhuǎn)發(fā)至z′方向的數(shù)據(jù)包達(dá)到率.

設(shè)置z方向?yàn)闁|,并以此為例計(jì)算θ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é)點(diǎn)(x,y)中轉(zhuǎn)發(fā)到z方向上緩沖區(qū)被占用的概率.對(duì)于采用虛擬通道技術(shù)的路由節(jié)點(diǎn),Px,y,z的取值與虛擬通道數(shù)以及虛擬通道分配機(jī)制有關(guān).而在采用非平均分配虛通道策略的片上網(wǎng)絡(luò)中,則可考慮為所有虛通道均被占用的概率,即

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

(11)

在計(jì)算源節(jié)點(diǎn)的平均等待時(shí)間時(shí),可把源節(jié)點(diǎn)中的虛通道模擬為一個(gè)隊(duì)列模型,即

式中,TR為網(wǎng)絡(luò)延時(shí);λx,y,L為從源節(jié)點(diǎn)輸入到網(wǎng)絡(luò)的數(shù)據(jù)包到達(dá)率.

2 虛通道分配算法

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)結(jié)果與分析

本文算法采用C++語(yǔ)言實(shí)現(xiàn).為了驗(yàn)證算法的有效性,根據(jù)虛通道分配結(jié)果,采用Verilog HDL語(yǔ)言完成NoC的RTL級(jí)設(shè)計(jì),并基于SMIC 0.18 μm工藝庫(kù),利用Design Compiler軟件進(jìn)行綜合.綜合得到的門級(jí)網(wǎng)表通過(guò)VCS仿真驗(yàn)證,并在Prime Time PX軟件中進(jìn)行功耗分析.

實(shí)驗(yàn)中使用的主要參數(shù)設(shè)置如下:片上網(wǎng)絡(luò)結(jié)構(gòu)為4×4的2D mesh結(jié)構(gòu);路由算法為XY固定路由算法；數(shù)據(jù)包微片長(zhǎng)度為8；Tb=4，即路由單元在無(wú)阻塞情況下,傳輸一個(gè)微片需要4個(gè)時(shí)鐘周期.

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

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

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

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

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

4 結(jié)語(yǔ)

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

)

[1]洪佳杰.高性能低功耗片上網(wǎng)絡(luò)設(shè)計(jì)中的功耗與延時(shí)模型研究[D].南京:南京航空航天大學(xué)信息科學(xué)與技術(shù)學(xué)院,2010.

[2]段振華.可重構(gòu)的片上網(wǎng)絡(luò)功耗建模與優(yōu)化[D].南京:南京航空航天大學(xué)電子信息工程學(xué)院,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]王力緯,曹陽(yáng),李曉輝,等. 片上網(wǎng)絡(luò)虛通道分配算法[J]. 華中科技大學(xué)學(xué)報(bào):自然科學(xué)版, 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]李曉輝,曹陽(yáng),王力緯,等. 基于遺傳算法的片上網(wǎng)絡(luò)虛通道分配算法[J]. 華中科技大學(xué)學(xué)報(bào):自然科學(xué)版, 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.