適用於晶片內非規律網狀網路之交通均衡負載路由演算法

Traffic-Balanced Routing Algorithm for Irregular Mesh-Based On-Chip Networks

黃群翔(Chun-Hsiang Huang)

指導教授 ： 吳安宇

國立臺灣大學/電機資訊學院/電子工程學研究所/碩士(2007年)

https://doi.org/10.6342/NTU.2007.10440

摘要

在未來奈米製程下，快速成長的電晶體數目與積體電路設計的複雜度上升將會是嚴重的問題，因此晶片內網路 (On-chip network) 被發表來解決這些問題。在晶片內網路中，實際上矽智產的面積大小並不會一樣，所以可以提供擺放不同大小矽智產的非規律網狀網路 (Irregular mesh) 是一個相當重要的概念。然而，適用於原本網狀網路的路由演算法 (Routing algorithm) 並不能直接套用在有尺寸過大之矽智產 (Oversized IP, OIP) 的非規律網狀網路上。為了能夠在傳送資料時能順利繞過OIP ，原本的路由演算法必須被修正。在多電腦(multicomputer) 系統裡，故障的網狀網路 (Faulty mesh) 在拓撲學上與非規律網狀網路是很相似的，而其容錯路由演算法 (Fault-tolerant routing algorithm) 已經被討論很多年了。然而，直接套用容錯路由演算法在非規律網狀網路上會造成下列兩大問題： 1) 在OIP 附近會有嚴重的交通負載以致於網路上的負載並不平均， 2) 有些封包的路徑過長。在這篇論文中，我們提出了一個避開OIP 預先路由演算法 (OIP avoidance pre-routing algorithm, OAPR) 以解決上述問題。OAPR可將交通負載平均分散到整個網路上，並且減少不必要的繞路行為，以縮短封包的路徑。所以，使用OAPR 的網路與傳統的容錯路由演算法相比有較低的延遲 (Latency) 以及較高的通量 (Throughput)。在我們的實驗中，有三個不同的例子證明OAPR 相較於其他兩種容錯路由演算法，增進了55.6% ~ 100%的通量。引用的兩個演算法分別為Chen and Chiu’s algorithm[15] 以及Extended XY routing algorithm [17]。最後，我們將演算法實現在硬體上，與整個晶片內的路由器 [24]比較起來，只佔不到1%的面積。因此，對於晶片內非網狀網路，OAPR 是一個既有優良效果並且易於實現的路由演算法。

關鍵字

晶片內網路 ； 路由演算法 ； 非規則網狀網路

並列摘要

On-chip networks (OCNs) have been proposed to solve increasing scale and complexity of the designs in nano-scale VLSI designs. In OCNs, the concept of irregular mesh is an important issue because IPs with different sizes can be supported. In order to solve routing on irregular mesh, modified routing algorithms to detour oversized IPs (OIPs) are needed. Fault-tolerant routing algorithms have been thought as solutions for irregular mesh because of the similar topology, faulty mesh, in multicomputer system. However, directly applying fault-tolerant routing algorithms may cause two serious problems: 1) heavy traffic loads around OIPs and unbalanced traffic loads on irregular meshes, 2) some paths of packets much longer than minimal path. In this thesis, we propose an OIP avoidance pre-routing (OAPR) algorithm to solve the aforementioned problems. OAPR can make traffic loads even spread on the networks, and shorten some paths of packets. Therefore, the networks using OAPR have lower latency and higher throughput than those using fault-tolerant routing algorithms. In our experiments, three different cases are simulated to demonstrate that proposed OAPR improve 55.6% ~ 100% sustainable throughputs than two cited fault-tolerant routing algorithm, Chen and Chiu’s algorithm [15] and extended XY routing algorithm [17]. Finally, we implement OAPR into hardware. The area overhead of OAPR is less than 1% compared to a whole router [24]. OAPR algorithm has good performance and is practical for irregular mesh-based OCNs.

並列關鍵字

On-chip networks ； routing algorithm ； irregular mesh

參考文獻

[1] ITRS, International Technology Roadmap for Semiconductors, http://public.itrs.net.

[2] J. A. Davis et al. “Interconnect Limits on Gigascale Integration (GSI) in the 21st Century,” Proc. IEEE, vol. 89, pp. 305-324, Mar. 2001.

[4] D. Sylvester and K. Keutzer, “A Global Wiring Paradigm for Deep Submicron Design,” IEEE Trans. CAD/ICAS, vol. 19, pp. 242-252, Feb. 2000.

[5] L. Benini and G. De Micheli, “Networks on Chips: A New SoC Paradigm,” IEEE Computer, vol. 35, pp. 70-78, Jan. 2002.

[6] P. Magarshack and P. G. Paulin, “System-on-Chip beyond the Nanometer Wall,” in Proc. DAC, Anaheim, 2003, pp. 419-424.