針對單晶片網路路由器內含多封包之動態配置多重佇列緩衝的設計與評估

Design and Evaluation of Dynamically-Allocated Multi-Queue Buffers with Multiple Packets for Network-on-Chip Routers

蔡詠州(Yung-Chou Tsai)

指導教授 ： 許雅三

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

摘要

在單晶片網路中有很大比例的面積及功率是被緩衝記憶體所消耗，因此這些昂貴的儲存資源必須被妥善使用。然而，一些早期相關的文獻已經不再適用於現代的單晶片網路路由器架構或者各種複雜的流量負載。在這篇論文當中，我們重新審視傳統的靜態配置多重佇列（SAMQ）與動態配置多重佇列（DAMQ）兩種緩衝記憶體方式，對於它們應用於現今的在單晶片網路路由器架構時提出所認為應有的設計考量，並且進一步提出一種叫做內含多封包之動態配置多重佇列（DAMQ-MP）的緩衝記憶體架構，而它是基於DAMQ改良使其能夠同時容納多於虛擬通道數量的封包。此DAMQ-MP方法不僅能事先將封包帶進緩衝記憶體預做準備來減少封包替換時的等待延遲，而且能將數個短封包塞在少數路由器中來釋出更多虛擬通道資源。這樣便能直接地解決在某些情況下的資料傳輸問題（例如嚴重網路雍塞或短封包）進而提升效能。同時我們也介紹兩種適合應用於DAMQ緩衝記憶體的方法：對於交換器附加優先權以及對於高優先權的封包保留某些虛擬通道。實驗結果顯示在大部分情況下DAMQ-MP路由器通常會比SAMQ和SAMQ路由器具有更好的效能與更高的緩衝記憶體使用率。我們相信對於現今單晶片網路路由器而言，由於DAMQ-MP不需要複雜的硬體設計更動，它可說是一種最簡單可行的改進緩衝記憶體架構方法，更加充分利用緩衝記憶體這項寶貴的資源。

關鍵字

單晶片網路 ； 路由器 ； 緩衝記憶體 ； 虛擬通道

並列摘要

A large portion of area and power in Network-on-Chip (NoC) routers is consumed by buffers, and hence these costly storage resources must be utilized well. However, some early related literatures are not suitable for modern NoC router architectures as well as various complicated traffic loads anymore. In this thesis, we resurveyed the conventional statically-allocated multi-queue (SAMQ) and dynamically-allocated multi-queue (DAMQ) buffer schemes. Furthermore, we proposed a new DAMQ-based buffer organization that can accommodate multiple packets more than the number of virtual channels, named DAMQ with multiple packets (DAMQ-MP). The DAMQ-MP scheme not only can bring standby packets in advance to reduce the waiting latencies of switching packets, but also can compact several short packets in few router nodes to release more virtual channel resources. This directly solves certain data transmission issues under some circumstances, such as heavy network congestion or short packets, to improve performance. We also introduced two methods applicable to DAMQ-based buffers, which are adding priorities for switch allocation and reserving certain virtual channels for high-priority packets. Experimental results show that DAMQ-MP routers generally can have better performance and higher buffer utilization rate than SAMQ and DAMQ counterparts in most cases. We believe that DAMQ-MP is the easiest and feasible method to improve buffer organization for modern NoC routers without sophisticated hardware design modifications.

並列關鍵字

Network-on-Chip ； router ； buffer ； virtual channel

參考文獻

[1] W. J. Dally and B. Towles, "Route Packets, Not Wires: On-Chip Interconnection Networks", In Proceedings of Design Automation Conference, pp. 684- 689, 2001

[2] Y. Hoskote, S. Vangal, A. Singh, N. Borkar, and S. Borkar, “A 5-GHz Mesh Interconnect for a Teraflops Processor”, IEEE Micro, vol. 27, no. 5, pp. 51-61, 2007.

[4] Y. Tamir and G. L. Frazier, “Dynamically-Allocated Multi-Queue Buffers for VLSI Communication Switches”, IEEE Transactions on Computers, vol. 41, no. 6, pp. 725-737, 1992.

[5] W. J. Dally, “Performance Analysis of k-ary n-cube Interconnection Networks”, IEEE Transactions on Computers, vol. 39, no. 6, pp. 775-785, 1990.

[7] J. Park, B. W. O’Krafka, S. Vassiliadis, and J. Delgado-Frias, “Design and Evaluation of a DAMQ Multiprocessor Network with Self-Compacting Buffers”, In Proceedings of ACM/IEEE Conference on Supercomputing, pp. 713-722, 1994.