針對動態重組單晶片網路的新穎架構與路由演算法

A Novel Architecture and Routing Algorithm for Dynamic Reconfigurable Network-on-Chip

巫立偉(Li-Wei Wu)

指導教授 ： 許雅三

國立清華大學/電機資訊學院/電機工程學系/碩士(2010年)

摘要

Hybrid networks, which combine the flexibility of packet-switched network and the low-latency of circuit-switched network, provide decent performance. However, existing researches require users to maintain the configuration of hybrid networks. Users need to spend a lot of time and effort on analyzing the applications at first. Then, they can know how and when to configure the hybrid network. The exhausting process motivates us to construct a hybrid network which reconfigures itself automatically. In this thesis, we propose Dynamic Bypass Circuit, a novel architecture which reconfigures the network according to the traffic trends of applications at run-time. Therefore, users need not to worry about the mapping between the applications and the network. Additionally, in order to make the trends more obvious, we modified original north-last routing algorithm into north-last-weave routing algorithm. It guides packets toward different directions according to the position of their source nodes.
The simulation results show that dynamic reconfigurable NoC which adopts Dynamic Bypass Circuit outperforms the traditional packet-switched network. The latency improvement is 18.08% under Transpose traffic and on average 10.76% under singular synthetic traffic patterns.

關鍵字

單晶片網路 ； 可重組 ； 動態 ； 混合網路

並列摘要

單晶片網路擁有優異的可擴充性及頻寬，已經逐漸地取代傳統匯流排的架構。為了追求最佳的傳輸效能，目前有許多研究是在討論混合網路的架構。混合網路結合了封包交換網路的彈性與線路交換網路的低延遲時間，它能提供優異的性能；然而，現今的研究都需要由使用者來管理混合網路的組態。使用者需要先花費大量的時間與精力來分析應用程式，然後才能知道該如何設定混合網路的組態。這種繁雜的過程給予我們靈感去建立一個能自動設定組態的混合網路。在這篇論文之中，我們分析了暫態線路交換連線對於各種封包的影響，並且提出了新穎的架構「動態旁路電路(Dynamic Bypass Circuit)」。藉由監視各個封包通過路由器的路徑，它能夠即時地偵測出應用程式的交通趨勢，並且針對這個趨勢來改變線路交換連線的組態。因此，使用者不再需要煩惱應用程式與網路的對應關係。除此之外，因為路由演算法會大幅的影響網路上的交通分佈，而這會改變動態旁路電路偵測交通的能力。為了讓交通趨勢能更顯著，我們改良原本的北向最後路由演算法(North-Last)，使之變成「編織樣式北向最後路由演算法(North-Last-Weave)」，其會參考原點的位置將封包導引到不同的方向。這個演算法能大幅提升建立暫態線路交換連線的機率。
實驗結果顯示，搭載了動態旁路電路的動態重組單晶片網路會表現的比傳統的封包交換網路要好。延遲時間的改進幅度最高為18.08%，平均改進幅度是10.76%。

並列關鍵字

Network-on-Chip ； Reconfigurable ； Dynamica ； Hybrid Network

參考文獻

[1] W. J. Dally and B. Towles, "Route packets, not wires: on-chip interconnection networks," in Proc. Design Automation Conference, pp. 684- 689, June 2001

[2] B. Ahmad, A. T. Erdogan and S. Khawam, "Architecture of a Dynamically Reconfigurable NoC for Adaptive Reconfigurable MPSoC," First NASA/ESA Conference on Adaptive Hardware and Systems, pp.405-411, June 2006

[3] M. Modarressi, Sarbazi-Azad H and A. Tavaakkol, "Performance and power efficient on-chip communication using adaptive virtual point-to-point connections," 3rd ACM/IEEE International Symposium on Networks-on-Chip, pp.203-212, May 2009

[4] Shih-Hsun Hsu, Yu-Xuan Lin and Jer-Min Jou, "Design of a Dual-Mode NoC Router Integrated with Network Interface for AMBA-based IPs," Solid-State Circuits Conference, pp.211-214, Nov. 2006

[5] K. Goossens, J. Dielissen and A. Radulescu, "AEthereal network on chip: concepts, architectures, and implementations," Design & Test of Computers, vol.22, no.5, pp. 414- 421, Sept.-Oct. 2005