朱愛軍,卜鵬程,胡 聰,許川佩,古展其

(1.桂林電子科技大學(xué)電子工程與自動化學(xué)院,廣西桂林 541004;2.廣西自動檢測技術(shù)與儀器重點(diǎn)實(shí)驗(yàn)室,廣西桂林 541004)

0 引言

隨著多核系統(tǒng)中元件數(shù)量的穩(wěn)步增長,傳統(tǒng)的電結(jié)構(gòu)片上網(wǎng)絡(luò)已不能滿足系統(tǒng)的性能要求[1-3],并面臨著延遲和功耗等關(guān)鍵問題。為解決基于電互連的片上網(wǎng)絡(luò)存在的局限性,基于光互連的片上網(wǎng)絡(luò)(optical network on chip,ONoC)技術(shù)成為未來高性能多核片上網(wǎng)絡(luò)設(shè)計(jì)的一個(gè)方向。近十年來,硅基光器件制造工藝方面取得的進(jìn)展為ONoC的快速發(fā)展鋪平了道路。三維封裝技術(shù)逐步走向成熟,使三維ONoC的設(shè)計(jì)趨于必然。其中最關(guān)鍵的問題之一是IP核映射。IP核映射在網(wǎng)絡(luò)的不同節(jié)點(diǎn)上將對網(wǎng)絡(luò)的通信產(chǎn)生不同的影響,映射結(jié)果將影響網(wǎng)絡(luò)的功率分布,進(jìn)而對網(wǎng)絡(luò)的溫度分布產(chǎn)生波動,從而影響ONoC中光學(xué)器件的正常工作,對網(wǎng)絡(luò)的傳輸性能造成影響[4]。

為降低由于網(wǎng)絡(luò)功率分配對網(wǎng)絡(luò)傳輸可靠性的影響,文獻(xiàn)[5-7]基于串?dāng)_噪聲感知使用遺傳算法將IP核自動映射到基于網(wǎng)格的ONoC節(jié)點(diǎn)中。文獻(xiàn)[8]同時(shí)考慮IP核映射和波長分配對ONoC可靠性的影響,提出了一種基于可靠性感知的聯(lián)合設(shè)計(jì)方法。為減少波長分配時(shí)波長的數(shù)量,文獻(xiàn)[9]研究了波長數(shù)目與網(wǎng)絡(luò)之間的關(guān)系,發(fā)現(xiàn)增加網(wǎng)絡(luò)大小可以減少所需的波長數(shù)。文獻(xiàn)[10]針對ONoC中的串?dāng)_噪聲,提出一種用于串?dāng)_噪聲優(yōu)化的啟發(fā)式融合映射算法。文獻(xiàn)[11]提出基于大災(zāi)變遺傳的模擬退火,解決了采用遺傳算法進(jìn)行IP核映射求解時(shí)出現(xiàn)的算法過早收斂和陷入局部最優(yōu)的問題。

綜上所述,現(xiàn)有的研究均未考慮以溫度均衡為光片上網(wǎng)絡(luò)IP核映射目標(biāo),從而導(dǎo)致通信性能下降和通信能耗增大。本文提出的趨邊快速映射以溫度均衡為目標(biāo),通過將網(wǎng)絡(luò)中的流量均勻分散到網(wǎng)絡(luò)中以均衡網(wǎng)絡(luò)溫度,從而改善通信性能和減小通信能耗。

1 IP核映射模型

由于構(gòu)成光波導(dǎo)的材料為硅基材料,而硅基材料的環(huán)境溫度改變時(shí),其一些參數(shù)也會發(fā)生相應(yīng)的改變。在波導(dǎo)傳輸損耗的基礎(chǔ)上考慮溫度的影響,得到含溫度系數(shù)的波導(dǎo)傳輸損耗公式:

(1)

式中:LWG0為常溫環(huán)境下的波導(dǎo)傳輸損耗;σc-σd為波導(dǎo)外壁與內(nèi)壁的熱光系數(shù)差值;ΔT為微環(huán)工作環(huán)境溫度與常溫的差值。

從式(1)可以看到,溫度的變化量與波導(dǎo)傳輸損耗存在平方關(guān)系,每10 ℃的溫差將會給波導(dǎo)帶來額外0.11%的損耗。

本文在光片上網(wǎng)絡(luò)的IP核映射研究中,除考慮IP核映射在網(wǎng)絡(luò)節(jié)點(diǎn)中的能耗和固有損耗以外,還考慮了網(wǎng)絡(luò)由于溫度影響所帶來的額外傳輸損耗。光片上網(wǎng)絡(luò)的網(wǎng)絡(luò)結(jié)構(gòu)在很大程度上可以決定網(wǎng)絡(luò)運(yùn)行的功耗和效率。本文采用曼哈頓距離來描述網(wǎng)絡(luò)的結(jié)構(gòu),所使用的三維Folded Torus網(wǎng)絡(luò)結(jié)構(gòu)的曼哈頓距離計(jì)算公式為

(2)

在計(jì)算曼哈頓距離時(shí),要考慮到目標(biāo)路徑是否連通,如果m,n兩個(gè)節(jié)點(diǎn)之間不存在通路,則這兩個(gè)節(jié)點(diǎn)的曼哈頓距離dm,n為0。本文所使用的三層三維Folded Torus結(jié)構(gòu)的曼哈頓距離矩陣如圖1所示。

圖1 曼哈頓距離矩陣

通信任務(wù)圖是描述通信模型的有向加權(quán)圖G(C,L),圖中的每個(gè)圓形節(jié)點(diǎn)ci(ci∈C)表示IP核,節(jié)點(diǎn)之間的有向線段lj,k(lj,k∈L,j≠k)表示節(jié)點(diǎn)上的IP核數(shù)據(jù)從cj到ck的傳輸方向,線段上的數(shù)字wj,k表示信息傳輸?shù)膸?數(shù)據(jù)傳輸單位為Mb/s。將IP核有向圖G映射到結(jié)構(gòu)圖T時(shí)規(guī)定IP核有向圖的大小不能大于結(jié)構(gòu)圖,即

size(G)≤size(T)

(3)

為評估映射方案的性能,本文以映射結(jié)果的總體能耗作為網(wǎng)絡(luò)映射的目標(biāo),在T.T.Ye等提出的片上網(wǎng)絡(luò)通信能耗模型和J.H等提出的能耗估算模型基礎(chǔ)上,對上述模型進(jìn)行修改,如式(4)所示:

ES=EC+ELWG+ERC

(4)

式中:ES為所有通信節(jié)點(diǎn)進(jìn)行通信時(shí)的能耗和信號在網(wǎng)絡(luò)中傳輸時(shí)的損耗累加和;EC為系統(tǒng)的通信節(jié)點(diǎn)在無損傳輸時(shí)的通信能耗總和;ELWG為網(wǎng)路中波導(dǎo)的能量損耗總和;ERC為每對通信節(jié)點(diǎn)之間的諧振器諧振損耗總和,其包括微環(huán)諧振器的插入損耗以及傳輸損耗。

將式(4)展開后得到的網(wǎng)絡(luò)系統(tǒng)能耗傳輸模型如式(5)～式(7)所示。式(5)中,等式右邊的第1項(xiàng)表示網(wǎng)絡(luò)傳輸時(shí)的通信功耗,第2項(xiàng)表示信號傳輸時(shí)在波導(dǎo)上的損耗,第3項(xiàng)為諧振器的諧振損耗量。

(1-rS)·Ci,j,i≠j

(5)

tS=k·ΔT(1+k·ΔT)

(6)

(7)

式中:Ni,j為通信節(jié)點(diǎn)i將信號發(fā)送到通信節(jié)點(diǎn)j時(shí)所經(jīng)過的路由器節(jié)點(diǎn)數(shù),即IP核映射在網(wǎng)絡(luò)后的曼哈頓距離;Ci,j為節(jié)點(diǎn)i到節(jié)點(diǎn)j的通信量;tS為波導(dǎo)的溫度損耗系數(shù);rS為微環(huán)諧振器的漂移系數(shù);ΔAS為微環(huán)諧振器的諧振波長漂移前后所對應(yīng)的光信號透射率的差值。

2 基于對稱分布的IP核趨邊映射算法

光片上網(wǎng)絡(luò)的基本器件在工作時(shí)對溫度有要求,過大的溫差不僅會給系統(tǒng)帶來額外的損耗,甚至?xí)斐善骷l(fā)生故障而不能正常工作,從而導(dǎo)致系統(tǒng)發(fā)生問題。因此,在基于對稱分布的快速映射算法上,本文提出面向網(wǎng)絡(luò)溫度均衡的IP核趨邊映射,降低網(wǎng)絡(luò)對溫度的敏感性。算法流程如圖2所示。

圖2 基于對稱分布的IP核趨邊映射算法流程圖

該算法針對片上網(wǎng)絡(luò)中心內(nèi)部結(jié)構(gòu)緊湊、通信頻率較大、容易發(fā)生堵塞的特點(diǎn),將通信量大和通信度復(fù)雜的IP核優(yōu)先映射在網(wǎng)絡(luò)的邊界節(jié)點(diǎn)。將通信流量高的IP核映射在網(wǎng)絡(luò)邊緣節(jié)點(diǎn)后,可以加速網(wǎng)絡(luò)的散熱,同時(shí),網(wǎng)絡(luò)通信的重心也將由網(wǎng)絡(luò)內(nèi)部轉(zhuǎn)移至網(wǎng)絡(luò)邊緣,從而更好地分散流量通信帶來的熱量。因?yàn)楣庑盘柕膫鬏敳灰蕾囉跁r(shí)間,并且波導(dǎo)的傳輸損耗要遠(yuǎn)低于由硅基器件的溫漂帶來的傳輸損耗。因此,將快速映射算法與趨邊映射算法相結(jié)合,能夠在不影響IP核映射速度的同時(shí)考慮網(wǎng)絡(luò)溫度均衡分布的問題。

根據(jù)流程圖,該算法可分為4部分。第一部分建立光片上網(wǎng)絡(luò)的中心值矩陣模型。根據(jù)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)建立的網(wǎng)絡(luò)結(jié)構(gòu)中心模型能夠反映網(wǎng)絡(luò)結(jié)構(gòu)中各節(jié)點(diǎn)所處偏離網(wǎng)絡(luò)中心的程度,節(jié)點(diǎn)的中心值越高,則所處的位置距離網(wǎng)絡(luò)中心越近。根據(jù)本文所使用的Folded Torus結(jié)構(gòu),圖3為該結(jié)構(gòu)的中心值矩陣。

圖3 三維3層Folded Torus網(wǎng)絡(luò)熱度值矩陣

熱度值矩陣的大小表示網(wǎng)絡(luò)節(jié)點(diǎn)在工作時(shí)溫度改變的權(quán)重。熱度值越高的節(jié)點(diǎn),表示該節(jié)點(diǎn)距離網(wǎng)絡(luò)的中心區(qū)域越近,被其他通信節(jié)點(diǎn)經(jīng)過的概率更大,數(shù)量更多,信道的負(fù)載量越大,其溫度的變化量將更大。而熱度值越小的節(jié)點(diǎn),則其溫度的變化量就越小。

第二部分是通信流量的熱度模型的建立。該模型以M個(gè)通信節(jié)點(diǎn)間的通信量Cm和連接數(shù)Lm作為依據(jù),將所有節(jié)點(diǎn)根據(jù)通信量的大小和通信復(fù)雜度分配歸一化的熱度值,并根據(jù)式(8)計(jì)算每個(gè)節(jié)點(diǎn)的熱度系數(shù)T_Cm。根據(jù)通信權(quán)重值對IP核進(jìn)行重新排序,生成基于熱度系數(shù)的CPL表。

(8)

式中:α為通信量系數(shù),α=0.2;β為連接量系數(shù),β=0.6。

第三部分生成網(wǎng)絡(luò)結(jié)構(gòu)ITS節(jié)點(diǎn)映射集合,在原來映射集合流程的基礎(chǔ)上新增網(wǎng)絡(luò)結(jié)構(gòu)的熱度矩陣,并在生成對稱分布集合ITS的基礎(chǔ)上為非對稱節(jié)點(diǎn)分配熱度值。

第四部分將IP核根據(jù)新的CPL列表映射到ITS集合的節(jié)點(diǎn)中,每次映射都會根據(jù)IP核選擇策略進(jìn)行下一個(gè)IP核映射位置的選擇。IP核選擇策略會計(jì)算IP核映射在下一次所有待選位置時(shí)的功耗,然后從中選擇相對功耗最小的位置作為本次IP核映射的目標(biāo)。若在映射IP核的過程中遇到多個(gè)待選位置功耗相同的節(jié)點(diǎn),則對以上節(jié)點(diǎn)進(jìn)行預(yù)分配。最后將兩次映射所需要的功耗進(jìn)行比較,選擇兩次映射的功耗最低的一組映射方案,直到CPL列表中的所有元素都完成映射,得到當(dāng)前映射方案的總體能耗。

3 實(shí)驗(yàn)結(jié)果對比

為驗(yàn)證本文所提出的映射算法,使用3D Folded Torus光片上網(wǎng)絡(luò)結(jié)構(gòu),用MPEG-4、VOPD、Core-10和Core-24 4個(gè)應(yīng)用作為測試實(shí)例對比算法的能耗,與隨機(jī)映射算法、蟻群映射算法和粒子群映射算法作對比,并分析映射算法在網(wǎng)絡(luò)不同溫度分布情況下的性能。

表1為使用的網(wǎng)絡(luò)仿真參數(shù)。網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)表示可被IP核映射的數(shù)量,信道損耗為光信號在波導(dǎo)中傳輸時(shí)的損耗,節(jié)點(diǎn)耦合損耗表示信號通過微環(huán)諧振器時(shí)的插入損耗以及耦合損耗;另外,下文中的均勻溫度分布N表示的是網(wǎng)絡(luò)中的所有節(jié)點(diǎn)位置的溫度均相同,并且在系統(tǒng)開始工作時(shí)仍然保持溫度不變;中心溫度分布M表示網(wǎng)絡(luò)中心節(jié)點(diǎn)位置的溫度最高,并呈球形向網(wǎng)絡(luò)的四周擴(kuò)散;隨機(jī)溫度分布R表示網(wǎng)絡(luò)有兩個(gè)以上的熱源出現(xiàn)在網(wǎng)絡(luò)中的隨機(jī)位置。

表1 仿真參數(shù)

圖4為4種映射在不同的通信任務(wù)下完成映射到網(wǎng)絡(luò)所需的時(shí)間,同時(shí)對比了算法在每個(gè)通信任務(wù)的不同網(wǎng)絡(luò)溫度分布下的運(yùn)行時(shí)間。在網(wǎng)絡(luò)均勻溫度分布的情況下,如圖4中的N部分所示,提出的趨邊快速映射在VOPD、MPEG-4、Core-10和Core-24 4個(gè)通信任務(wù)中的映射速度都大幅度領(lǐng)先于蟻群映射和粒子群映射,而略慢于隨機(jī)映射。而在網(wǎng)絡(luò)中心溫度分布和隨機(jī)溫度分布下,4種映射算法的映射速度與均勻溫度分布時(shí)的映射速度差別不大。由此可見,提出的趨邊映射算法可以保證算法映射的速度。

圖4 映射算法在不同通信任務(wù)下的所需時(shí)間

圖5展示了4種映射結(jié)果下的網(wǎng)絡(luò)能耗,從圖5可以看到,在相同的通信任務(wù)下,網(wǎng)絡(luò)溫度隨機(jī)分布的能耗要高于中心溫度,這是由于網(wǎng)絡(luò)在隨機(jī)溫度分布下的平均溫度要高于中心溫度分布,因此網(wǎng)絡(luò)的整體能耗也就隨之增加。在隨機(jī)溫度分布下,提出的趨邊映射在不同的通信任務(wù)下均低于隨機(jī)映射,而略高于蟻群和粒子群映射。這是由于蟻群和粒子群在尋找網(wǎng)絡(luò)的映射位置時(shí)犧牲了時(shí)間而進(jìn)行多次的迭代搜索,從而尋找到網(wǎng)絡(luò)相對能耗最優(yōu)的映射位置。

圖5 映射算法在不同通信任務(wù)下的能耗總和

表2為映射算法在不同的網(wǎng)絡(luò)溫度分布情況下循環(huán)10次,每次循環(huán)依次完成VOPD,MPEG-4,Core-10和Core-24通信任務(wù)的平均能耗。

表2 不同溫度分布下映射算法完成所有通信任務(wù)的平均能耗 J

從表2可以看到,提出的趨邊快速映射算法與蟻群映射和粒子群映射相近,優(yōu)于隨機(jī)映射。在3種不同的溫度分布下,提出的趨邊映射比隨機(jī)映射平均少了22.5%的能耗,與粒子群映射相比平均少了13.7%的能耗,與蟻群映射的能耗持平。

4 結(jié)束語

ONoC中的IP核映射問題是光片上網(wǎng)絡(luò)的研究重點(diǎn)之一,應(yīng)用在網(wǎng)絡(luò)中的映射結(jié)果對網(wǎng)絡(luò)的能耗有較大的影響。分析光片上網(wǎng)絡(luò)中IP核映射對網(wǎng)絡(luò)能耗的影響,提出了面向溫度均衡的光片上網(wǎng)絡(luò)映射算法。分析ONoC網(wǎng)絡(luò)結(jié)構(gòu)的特點(diǎn),建立了網(wǎng)絡(luò)的能耗模型。然后根據(jù)網(wǎng)絡(luò)的對稱性結(jié)構(gòu)和溫度分布特點(diǎn)提出一種趨邊快速映射算法。仿真結(jié)果表明:提出的映射算法在快速獲得映射結(jié)果的同時(shí),具有更低的網(wǎng)絡(luò)能耗,并且能夠得到分布較均衡的網(wǎng)絡(luò)映射結(jié)果。