用于自適應(yīng)路由片上網(wǎng)絡(luò)的緩沖分配算法

李曉輝，曹 陽(yáng)，王力緯，陳 晨

(1. 武漢大學(xué)電子信息學(xué)院 武漢 430079; 2. 中國(guó)科學(xué)院高有物理研究所 北京 石景山區(qū) 100049)

用于自適應(yīng)路由片上網(wǎng)絡(luò)的緩沖分配算法

李曉輝1,2，曹 陽(yáng)1，王力緯1，陳 晨1

(1. 武漢大學(xué)電子信息學(xué)院 武漢 430079; 2. 中國(guó)科學(xué)院高有物理研究所 北京 石景山區(qū) 100049)

針對(duì)片上網(wǎng)絡(luò)緩沖資源緊張的問(wèn)題，提出了一種緩沖分配算法。在有限的資源下，該算法能夠根據(jù)每個(gè)路由器輸入通道上負(fù)載的情況來(lái)自動(dòng)分配緩沖資源，從而獲得最大的網(wǎng)絡(luò)性能。在該算法中，提出了適用于自適應(yīng)路由算法下的路由器性能分析模型，利用該模型可以快速定位系統(tǒng)中的性能瓶頸。仿真實(shí)驗(yàn)的結(jié)果表明，使用本算法后的NoC能比均勻分配策略下的NoC獲得更小的數(shù)據(jù)包平均傳輸時(shí)延，同時(shí)，該算法還能節(jié)省約33%的緩沖資源。

自適應(yīng)路由算法; 分析模型; 緩沖分配; 片上網(wǎng)絡(luò)

隨著半導(dǎo)體工藝的迅猛發(fā)展，一個(gè)單一的芯片上可集成幾十個(gè)，甚至數(shù)百個(gè)處理單元(processing element，PE)和存儲(chǔ)單元(storage element，SE)，為了解決各個(gè)單元間復(fù)雜的互連通信問(wèn)題，提出了片上網(wǎng)絡(luò)(NoC)[1-3]的概念。

1 片上網(wǎng)絡(luò)

典型的片上網(wǎng)絡(luò)由資源節(jié)點(diǎn)、路由器和雙向鏈路組成。每個(gè)資源節(jié)點(diǎn)通過(guò)本地網(wǎng)絡(luò)接口與一個(gè)路由器相連接，使各種不同的接口協(xié)議在網(wǎng)絡(luò)層可以被屏蔽。每個(gè)路由器與相鄰的4個(gè)路由器通過(guò)雙向鏈路相連，數(shù)據(jù)主要以包的形式在各個(gè)資源節(jié)點(diǎn)間傳輸。在蟲(chóng)孔交換(wormhole switch)機(jī)制中，每個(gè)數(shù)據(jù)包被分為固定長(zhǎng)度的微片。數(shù)據(jù)包的傳輸路徑受路由算法的控制。

片上網(wǎng)絡(luò)由于實(shí)現(xiàn)環(huán)境所限而面臨嚴(yán)格的資源成本約束，為了降低實(shí)現(xiàn)代價(jià)，要求NoC的面積必須盡可能地小。在NoC路由器中，每個(gè)輸入方向上的緩沖大小直接影響網(wǎng)絡(luò)的性能。文獻(xiàn)[4]的研究表明，路由器絕大部分面積都被輸入緩沖所使用。因此，為了減小NoC面積而又不影響網(wǎng)絡(luò)的性能，每個(gè)路由器輸入緩沖的大小都必須仔細(xì)計(jì)算。

2 緩沖分配算法

2.1 問(wèn)題描述

片上網(wǎng)絡(luò)緩沖分配問(wèn)題的實(shí)質(zhì)就是在給定緩沖資源總量的前提下，如何在各個(gè)路由器輸入通道間分配有限的資源，從而獲得最大的網(wǎng)絡(luò)性能。網(wǎng)絡(luò)性能主要通過(guò)數(shù)據(jù)包平均傳輸時(shí)延L來(lái)衡量[4]，用數(shù)學(xué)方法可描述為：

已知緩沖資源的總量為B；數(shù)據(jù)包注入率為gλ；系統(tǒng)參數(shù)，如數(shù)據(jù)包頭微片處理時(shí)間為H；數(shù)據(jù)包微片個(gè)數(shù)為M等，求每個(gè)輸入方向上的緩沖大小lx,y,dir，使得數(shù)據(jù)包平均傳輸時(shí)延L最小，即：

2.2 相關(guān)研究

傳統(tǒng)的緩沖分配主要采用均勻分配策略，即為每個(gè)路由器分配相同大小的輸入緩沖，但由于片上網(wǎng)絡(luò)中業(yè)務(wù)流量分布不均勻，該方法無(wú)法獲得最大的網(wǎng)絡(luò)性能。更優(yōu)的方法是在負(fù)載較重的輸入通道上分配更多的緩沖資源，而負(fù)載較輕的通道上分配較少的資源。為了實(shí)現(xiàn)該分配方法，需要對(duì)NoC的性能進(jìn)行評(píng)估，找出那些負(fù)載重的輸入通道。文獻(xiàn)[5]對(duì)2維網(wǎng)格(2D Mesh)結(jié)構(gòu)進(jìn)行了改進(jìn)，提出了一種新的拓?fù)浣Y(jié)構(gòu)，在特定業(yè)務(wù)流量下取得了較好的網(wǎng)絡(luò)性能。文獻(xiàn)[6]提出了一種路由器分析模型，該模型適用于不同大小的輸入緩沖和消息長(zhǎng)度，但只對(duì)均勻分配方式有效。文獻(xiàn)[7]提出了根據(jù)網(wǎng)絡(luò)中的業(yè)務(wù)流量動(dòng)態(tài)分配緩沖資源的方法，該方法需要對(duì)路由器的結(jié)構(gòu)進(jìn)行修改，增加了硬件開(kāi)銷(xiāo)。

文獻(xiàn)[4]利用排隊(duì)論建立了基于存儲(chǔ)轉(zhuǎn)發(fā)(store-and-forward)機(jī)制和虛跨步切換(virtual cut-through)機(jī)制的分析模型，并提出了一種緩沖分配算法。文獻(xiàn)[8]對(duì)此做出改進(jìn)，建立了用于蟲(chóng)孔交換機(jī)制下的分析模型。

文獻(xiàn)[4]和文獻(xiàn)[8]都僅考慮了確定性路由算法，然而在實(shí)際的應(yīng)用中，自適應(yīng)路由算法，特別是部分自適應(yīng)路由算法，在片上網(wǎng)絡(luò)中使用更為廣泛[9]，因此本文將主要討論如何在自適應(yīng)路由算法下建立分析模型，并實(shí)現(xiàn)緩沖分配。

2.3 分析模型

由于不同拓?fù)浣Y(jié)構(gòu)下自適應(yīng)路由算法各有區(qū)別，為使研究不失一般性，本文主要考慮2維網(wǎng)格結(jié)構(gòu)[1-3]下的部分自適應(yīng)路由算法(如DyAD routing、Turn-model based routing和Odd-even routing等)，這些算法實(shí)現(xiàn)簡(jiǎn)單，而且不需要使用虛通道。在此基礎(chǔ)上，建立路由器分析模型，通過(guò)該模型，能夠快速定位系統(tǒng)中的性能瓶頸。本文中，性能瓶頸被定義為所有輸入通道中最可能出現(xiàn)滿(mǎn)(full)的位置，即某一輸入通道處緩沖為滿(mǎn)的概率最大。

本文提出的分析模型基于如下假設(shè)[4,6,8,11]：

(1)網(wǎng)絡(luò)中各節(jié)點(diǎn)發(fā)送數(shù)據(jù)包的過(guò)程相互獨(dú)立，并且該過(guò)程滿(mǎn)足泊松分布，平均注入率為每周期gλ個(gè)數(shù)據(jù)包。此外，數(shù)據(jù)包的目的地址均勻地分布在網(wǎng)絡(luò)中。

(2)數(shù)據(jù)包的長(zhǎng)度固定為M個(gè)微片，在沒(méi)有阻塞的情況下，每個(gè)微片從一個(gè)路由器發(fā)送到相鄰路由器所需要的時(shí)間為一個(gè)時(shí)鐘周期。

(3)路由器輸入緩沖的寬度等于一個(gè)微片的位寬，因此輸入緩沖容量可用微片個(gè)數(shù)來(lái)表示。

(4)路由器在本地輸入方向上的緩沖為無(wú)限大。此外，任何數(shù)據(jù)包到達(dá)目的節(jié)點(diǎn)后都被立即發(fā)送到處理單元。

根據(jù)排隊(duì)論的相關(guān)知識(shí)[10]，可以把路由器東、西、南、北4個(gè)方向上的輸入緩沖分別視為一個(gè)M/G/1/K的有限長(zhǎng)隊(duì)列，對(duì)于節(jié)點(diǎn)(x,y)，其dir方向上緩沖為滿(mǎn)的概率為：

因此，只要求得路由器每個(gè)輸入通道的數(shù)據(jù)包到達(dá)率λx,y,dir和平均服務(wù)時(shí)間Tx,y,dir，就能夠計(jì)算出對(duì)應(yīng)的概率值，并由此找到系統(tǒng)的性能瓶頸對(duì)其進(jìn)行優(yōu)化。

假設(shè)a和b是網(wǎng)絡(luò)中兩個(gè)相鄰的節(jié)點(diǎn)，而s和d分別為源節(jié)點(diǎn)和目的節(jié)點(diǎn)，由文獻(xiàn)[6]可知，對(duì)于一對(duì)特定的源、目的節(jié)點(diǎn)(s,d)，其數(shù)據(jù)包傳輸路徑經(jīng)過(guò)通道?a,b?的概率可以表示為：

式中 xs、 ys分別為各節(jié)點(diǎn)在網(wǎng)絡(luò)中的坐標(biāo)值。

由假設(shè)(1)可知，網(wǎng)絡(luò)中的流量為均勻隨機(jī)流量，則通道?a,b?上的數(shù)據(jù)包到達(dá)率為：

式中 N表示網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)，對(duì)于K×K的網(wǎng)絡(luò)，N=K2；λg為每個(gè)節(jié)點(diǎn)的包注入率。

當(dāng)網(wǎng)絡(luò)中有多對(duì)源、目的節(jié)點(diǎn)時(shí)，該通道上總的數(shù)據(jù)包到達(dá)率為：

2.4 算法步驟

基于上述分析模型，本文采用了一種貪婪的緩沖分配算法[8]，它能夠向負(fù)載最重的輸入通道自動(dòng)分配更多的緩沖資源，具體步驟如下：

該分配方式雖然比較簡(jiǎn)單，但從下面的實(shí)驗(yàn)結(jié)果看，能夠取得比較好的分配效果。

3 仿真結(jié)果與分析

為驗(yàn)證本文所提出的算法，利用System C[12]構(gòu)建一個(gè)NoC性能仿真平臺(tái)，其具有高時(shí)鐘模擬精度以及良好的可擴(kuò)展性，可以對(duì)網(wǎng)絡(luò)大小、拓?fù)浣Y(jié)構(gòu)、路由算法等靈活配置。仿真采用數(shù)據(jù)包微片個(gè)數(shù)M=16，數(shù)據(jù)包頭微片處理時(shí)間為兩個(gè)時(shí)鐘周期(H=2)，網(wǎng)絡(luò)結(jié)構(gòu)為4×4 Mesh?；谵D(zhuǎn)彎模型的北向最后(north-last，NL)路由算法和DyAD路由算法[13-14]，在一種典型的業(yè)務(wù)流量，即均勻隨機(jī)流量(uniform)情況下進(jìn)行。在該流量下，每個(gè)節(jié)點(diǎn)都以相同的概率向任意節(jié)點(diǎn)發(fā)送數(shù)據(jù)包。每次仿真過(guò)程都持續(xù)5×105個(gè)時(shí)鐘周期，為避免采集到網(wǎng)絡(luò)不穩(wěn)定時(shí)的數(shù)據(jù)，前1×105個(gè)周期屬于預(yù)熱階段，數(shù)據(jù)包信息不予采用。在仿真結(jié)果中，用Uniform N代表為每個(gè)輸入通道分配N(xiāo)個(gè)緩沖單元的均勻分配算法，而用Customized N代表相同緩沖資源下本文所提出的分配算法。

圖1表示了NL路由算法下不同分配算法的仿真結(jié)果。從圖中可以看出，在較低的注入率下(<0.012 packet·cycle?1)，各分配算法的網(wǎng)絡(luò)性能基本相同。隨著注入率的增加，Uniform 4和Uniform 6先后因輸入通道緩沖資源不足導(dǎo)致網(wǎng)絡(luò)中發(fā)生數(shù)據(jù)包擁塞，整個(gè)網(wǎng)絡(luò)性能迅速趨于飽和。而Customized 4預(yù)先通過(guò)分析模型估算出了系統(tǒng)的性能瓶頸并向其分配了較多的緩沖資源，有效地緩解了該處數(shù)據(jù)包的擁塞，最終獲得了較小的數(shù)據(jù)包時(shí)延。由實(shí)驗(yàn)結(jié)果可知，Customized 4的性能要優(yōu)于Uniform 6，說(shuō)明通過(guò)本文的分配算法可為NoC節(jié)省約33%的緩沖資源達(dá)到比均勻分配算法更好的性能。

圖1 NL路由算法下的性能曲線(xiàn)

圖2為DyAD路由算法下的仿真結(jié)果?？梢钥吹剑藭r(shí)Customized 4的性能依然優(yōu)于其他算法，且其飽和吞吐率為0.013 packet·cycle?1，比Uniform 6提高了約18.2%。而在圖1中，Customized 4的飽和吞吐率僅比Uniform 6提高了(0.014- 0 .013)/0.013≈7.7%。本文算法在DyAD路由算法下能獲得更好的分配效果，這主要是因?yàn)?，與DyAD路由算法相比，NL路由算法在一定程度上使網(wǎng)絡(luò)中業(yè)務(wù)流量的分布更均勻，從而減少了系統(tǒng)中可能存在的性能瓶頸。在該情況下，均勻分配算法可以取得相對(duì)較好的分配效果，而本文算法對(duì)系統(tǒng)性能的優(yōu)化作用則不明顯。實(shí)際上，網(wǎng)絡(luò)中業(yè)務(wù)流量分布越不均勻，系統(tǒng)中潛在的性能瓶頸就越多，本文算法對(duì)系統(tǒng)的優(yōu)化程度就越高，反之就越低。

圖2 DyAD路由算法下的性能曲線(xiàn)

為進(jìn)一步驗(yàn)證本文算法的性能，將該算法與文獻(xiàn)[4]中的線(xiàn)性啟發(fā)式算法進(jìn)行比較。啟發(fā)式算法的基本思想是利用路由器輸入通道上負(fù)載大小與緩沖資源間的線(xiàn)性比例關(guān)系進(jìn)行分配。在圖3中，線(xiàn)性啟發(fā)式算法(linearly proportional，LP)用LP N表示，路由算法為DyAD路由算法。可以看到，當(dāng)緩沖資源總量相同時(shí)，線(xiàn)性啟發(fā)式算法具有比均勻分配算法更好的性能，但是與本文算法相比，兩者數(shù)據(jù)包時(shí)延仍相差較大，即本文算法的分配效果要優(yōu)于文獻(xiàn)[4]中的線(xiàn)性啟發(fā)式算法。

圖3 不同算法與線(xiàn)性啟發(fā)式算法比較的性能曲線(xiàn)

4 總 結(jié)

本文針對(duì)網(wǎng)格型NoC中的部分自適應(yīng)路由算法，建立了路由器性能分析模型，并以此為基礎(chǔ)，提出了一種緩沖分配算法。該算法首先根據(jù)分析模型判斷出系統(tǒng)中的性能瓶頸，隨后通過(guò)向其分配較多的緩沖資源獲得網(wǎng)絡(luò)性能的提升。仿真結(jié)果表明，經(jīng)過(guò)本文算法的分配，有效地利用了已有的緩沖資源，降低了數(shù)據(jù)包平均傳輸時(shí)延。未來(lái)的研究工作將主要集中在對(duì)現(xiàn)有模型的擴(kuò)展和獲得更精確的分配結(jié)果上。

[1]KUMAR S, JANTSCH A, SONININEN J P, et al. A network on chip architecture and design methodology[C]//Proceedings of the IEEE Computer Society Annual Symposium on VLSI. Pennsylvania: IEEE Press, 2002: 117-124.

[2]BENINI L, DEMICHELI G. Networks on chips: a new SoC paradigm[J]. Computer, 2002, 35(1): 70-78.

[3]HEMKEL J, WOLF W, CHAKRADHAR S. On-chip networks: A scalable, communication centric embedded system design paradigm[C]//Proceedings of the IEEE International Conference on VLSI Design. Mumbai: IEEE Press, 2004: 845-851.

[4]HU J, OGRAS U Y, MARCULESCU R. System-level buffer allocation for application specific networks -on-chip router design[J]. IEEE Transaction on Computer-aided Design of Integrated Circuits and Systems, 2006, 25(12): 2919-2933.

[5]ANJUM S, CHEN Jie, YUE Pei-pei, et al. Delay optimized architecture for on-chip communication[J]. Journal of Electronic Science and Technology of China, 2009, 7(2):104-109.

[6]BAHN J H, BAGHERZADEH N. Design of simulation and analytical models for a 2d-meshed asymmetric adaptive router[J]. IET Computer Digital Technology, 2008, 2(1):63-73.

[7]賴(lài)明澈, 王志英, 郭建軍, 等. 具有擁塞緩解策略的動(dòng)態(tài)虛擬通道研究及其VLSI實(shí)現(xiàn)[J]. 計(jì)算機(jī)學(xué)報(bào), 2008,31(11): 2026-2037.

LAI Ming-che, WANG Zhi-ying, GUO Jian-jun, et al.Research and VLSI implementation of a dynamic virtual channel structure with congestion awareness scheme[J].Chinese Journal of Computers, 2008, 31(11): 2026-2037.

[8]王力緯, 曹 陽(yáng), 李曉輝, 等. 蟲(chóng)孔路由NoC的緩沖分配算法[J]. 北京郵電大學(xué)學(xué)報(bào), 2008, 31(4): 29-32.

WANG Li-wei, CAO Yang, LI Xiao-hui, et al. A buffer allocation algorithm for wormhole routing networks-on-chip[J].Journal of Beijing University of Posts and Telecommunications,2008, 31(4): 29-32.

[9]BARATI H, MOVAGHAR A, BARATI A, et al. Routing algorithms study and comparing in interconnection networks[C]//Proceedings of 3rd International Conference on Information and Communication Technologies.Damascus: IEEE Press, 2008: 1-5.

[10]盛友招. 排隊(duì)論及其在現(xiàn)代通信中的應(yīng)用[M]. 北京: 人民郵電出版社, 2007.

SHENG You-zhao. Queuing theory and its application in modern communications [M]. Beijing: Posts and Telecommunications Press, 2007.

[11]PATOOGHY A, SARBAZI-AZAD H. Analytical performance modeling of partially adaptive routing in wormhole hypercube[C]//Proceedings of 20th International Parallel and Distributed Processing Symposium. Rhodes Island: IEEE Press, 2006: 1-7.

[12]Open System C Initiative. System C version 2.0 user’s guide[DB/OL]. [2002-02-08]. http:// www.systemc. org.

[13]DUATO J, YALAMANCHILI S, LIONEL M.Interconnection networks—an engineering approach[M].San Francisco: Morgan Kaufmann Publisher, 2003.

[14]HU J, MARCULESCU R. DyAD-smart routing for networks-on-chip[C]//Proceedings of the 41st Design Automatic Conference. San Diego: ACM Press, 2004:260-263.

編 輯 張 俊

Buffer Allocation Algorithm for Adaptively-Routed Network-on-Chip

LI Xiao-hui1,2, CAO Yang1, WANG Li-wei1, and CHEN Chen1

(1. School of Electronic Information, Wuhan University Wuhan 430079;2. Institute of High Energy Physics, Chinese Academy of Sciences Shijingshan Beijing 100049)

For the intension of buffering resources in network-on-chip (NoC), a buffer allocation algorithm is proposed. Given buffering space budget, our algorithm automatically allocates the resources on each input channel,in different routers across the chip, to match the traffic load, such that the overall performance is maximized. In the algorithm, a novel analytical model for adaptive routing is used to quickly detect potential performance bottlenecks in the system. Simulation results indicate that our algorithm can get lower average packet latency than uniform allocation strategy, and about 33% savings in buffering resources can be achieved.

adaptive routing algorithm; analytical model; buffer allocation; network-on-chip

TP393

A

10.3969/j.issn.1001-0548.2010.06.026

2009- 04- 13;

2009- 10- 25

國(guó)家863計(jì)劃項(xiàng)目(2002AA1Z149)

李曉輝(1982- )，男，博士生，主要從事NoC設(shè)計(jì)方法學(xué)方面的研究.

·電子信息材料與器件·