用于自適應路由片上網絡的緩沖分配算法

李曉輝，曹 陽，王力緯，陳 晨

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

用于自適應路由片上網絡的緩沖分配算法

李曉輝1,2，曹 陽1，王力緯1，陳 晨1

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

針對片上網絡緩沖資源緊張的問題，提出了一種緩沖分配算法。在有限的資源下，該算法能夠根據每個路由器輸入通道上負載的情況來自動分配緩沖資源，從而獲得最大的網絡性能。在該算法中，提出了適用于自適應路由算法下的路由器性能分析模型，利用該模型可以快速定位系統中的性能瓶頸。仿真實驗的結果表明，使用本算法后的NoC能比均勻分配策略下的NoC獲得更小的數據包平均傳輸時延，同時，該算法還能節省約33%的緩沖資源。

自適應路由算法; 分析模型; 緩沖分配; 片上網絡

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

1 片上網絡

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

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

2 緩沖分配算法

2.1 問題描述

片上網絡緩沖分配問題的實質就是在給定緩沖資源總量的前提下，如何在各個路由器輸入通道間分配有限的資源，從而獲得最大的網絡性能。網絡性能主要通過數據包平均傳輸時延L來衡量[4]，用數學方法可描述為：

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

2.2 相關研究

傳統的緩沖分配主要采用均勻分配策略，即為每個路由器分配相同大小的輸入緩沖，但由于片上網絡中業務流量分布不均勻，該方法無法獲得最大的網絡性能。更優的方法是在負載較重的輸入通道上分配更多的緩沖資源，而負載較輕的通道上分配較少的資源。為了實現該分配方法，需要對NoC的性能進行評估，找出那些負載重的輸入通道。文獻[5]對2維網格(2D Mesh)結構進行了改進，提出了一種新的拓撲結構，在特定業務流量下取得了較好的網絡性能。文獻[6]提出了一種路由器分析模型，該模型適用于不同大小的輸入緩沖和消息長度，但只對均勻分配方式有效。文獻[7]提出了根據網絡中的業務流量動態分配緩沖資源的方法，該方法需要對路由器的結構進行修改，增加了硬件開銷。

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

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

2.3 分析模型

由于不同拓撲結構下自適應路由算法各有區別，為使研究不失一般性，本文主要考慮2維網格結構[1-3]下的部分自適應路由算法(如DyAD routing、Turn-model based routing和Odd-even routing等)，這些算法實現簡單，而且不需要使用虛通道。在此基礎上，建立路由器分析模型，通過該模型，能夠快速定位系統中的性能瓶頸。本文中，性能瓶頸被定義為所有輸入通道中最可能出現滿(full)的位置，即某一輸入通道處緩沖為滿的概率最大。

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

(1)網絡中各節點發送數據包的過程相互獨立，并且該過程滿足泊松分布，平均注入率為每周期gλ個數據包。此外，數據包的目的地址均勻地分布在網絡中。

(2)數據包的長度固定為M個微片，在沒有阻塞的情況下，每個微片從一個路由器發送到相鄰路由器所需要的時間為一個時鐘周期。

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

(4)路由器在本地輸入方向上的緩沖為無限大。此外，任何數據包到達目的節點后都被立即發送到處理單元。

根據排隊論的相關知識[10]，可以把路由器東、西、南、北4個方向上的輸入緩沖分別視為一個M/G/1/K的有限長隊列，對于節點(x,y)，其dir方向上緩沖為滿的概率為：

因此，只要求得路由器每個輸入通道的數據包到達率λx,y,dir和平均服務時間Tx,y,dir，就能夠計算出對應的概率值，并由此找到系統的性能瓶頸對其進行優化。

假設a和b是網絡中兩個相鄰的節點，而s和d分別為源節點和目的節點，由文獻[6]可知，對于一對特定的源、目的節點(s,d)，其數據包傳輸路徑經過通道?a,b?的概率可以表示為：

式中 xs、 ys分別為各節點在網絡中的坐標值。

由假設(1)可知，網絡中的流量為均勻隨機流量，則通道?a,b?上的數據包到達率為：

式中 N表示網絡中的節點數，對于K×K的網絡，N=K2；λg為每個節點的包注入率。

當網絡中有多對源、目的節點時，該通道上總的數據包到達率為：

2.4 算法步驟

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

該分配方式雖然比較簡單，但從下面的實驗結果看，能夠取得比較好的分配效果。

3 仿真結果與分析

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

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

圖1 NL路由算法下的性能曲線

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

圖2 DyAD路由算法下的性能曲線

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

圖3 不同算法與線性啟發式算法比較的性能曲線

4 總 結

本文針對網格型NoC中的部分自適應路由算法，建立了路由器性能分析模型，并以此為基礎，提出了一種緩沖分配算法。該算法首先根據分析模型判斷出系統中的性能瓶頸，隨后通過向其分配較多的緩沖資源獲得網絡性能的提升。仿真結果表明，經過本文算法的分配，有效地利用了已有的緩沖資源，降低了數據包平均傳輸時延。未來的研究工作將主要集中在對現有模型的擴展和獲得更精確的分配結果上。

[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]賴明澈, 王志英, 郭建軍, 等. 具有擁塞緩解策略的動態虛擬通道研究及其VLSI實現[J]. 計算機學報, 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]王力緯, 曹 陽, 李曉輝, 等. 蟲孔路由NoC的緩沖分配算法[J]. 北京郵電大學學報, 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]盛友招. 排隊論及其在現代通信中的應用[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

國家863計劃項目(2002AA1Z149)

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

·電子信息材料與器件·