適用於可調整式拓樸結構之網狀晶片內網路路由演算法與架構

晶片內網路已被提出來解決未來複雜的晶片內通訊問題。在本論文中，我們針對可調整式拓樸結構之網狀晶片內網路來探討，包含故障格狀網路與非規則格狀網路。針對故障格狀網路，我們提出路徑穿越容錯繞進演算法（Through-Path Fault-Tolerant Routing, TP-FT）來解決故障格狀網路的繞徑問題。運用TP-FT演算法的晶片內網路相較於使用傳統容錯繞徑演算法可以有較佳的網路效能。在我們的實驗中，透過分析三種不同的狀況可證明TP-FT演算法可以改進2.9%~45.4%通量 (Throughput)。此外，我們設計了兩種內見自我測試與診斷（Built-in Self-Test/Self-Diagnosis，BIST/SD）與錯誤隔離(Fault isolation, FI)的架構來檢測，診斷，與隔絕路由器中故障的先進先出暫存器和多工器。在我們的實驗中，20PR內建的BIST/SD執行時只需要117固定的測試週期時間，STR則需要144~376測試週期時間。實現採用20PR的晶片內網路架構需要額外增加15.17%硬體面積,而採用STR的晶片內網路架構只需增加8.48%~13.3%硬體面積。　　針對非規則格狀網路，我們提出了一個避開OIP預先路由演算法 (OIP avoidance pre-routing algorithm, OAPR)以解決非規則格狀網路的繞徑問題。OAPR可將交通負載平均分散到整個網路上，並且減少不必要的繞路行為，以縮短封包的路徑。所以，使用OAPR的網路與傳統的容錯路由演算法相比有較低的延遲以及較高的通量。在我們的實驗中，有四個不同的例子證明OAPR相較於其他兩種容錯路由演算法，增進了13.3%~100%的通量。最後，我們將演算法實現在硬體上，與整個晶片內的路由器比較起來，只佔不到1%的面積。此外，在非規則格狀網路中，尺寸過大之矽智產 (Oversized IP, OIP)的擺放位置與轉向方式(OIP positions/orientations)，會嚴重影響網路效能。我們針對OIP預先路由演算法分析不同擺放位置與轉向方式並定出一些準則。根據這些準則，使用者在利用OIP預先路由演算法可以決定要如何尺寸過大之矽智產的位置以達到較佳的網路效能。

關鍵字

晶片內網路；網狀拓樸；路由演算法；容錯

並列摘要

On-Chip Networks (OCNs) have been proposed to solve the complex on-chip communication problems. In this dissertation, we focus on mesh-based OCNs with adjustable topology, which considers both irregular meshes and faulty meshes for future SoC designs. For faulty meshes, we propose new Fault-Tolerant (FT) routing algorithms, called Through-Path Fault-Tolerant (TP-FT) routing algorithms to solve the routing problems in the faulty meshes. The OCNs using these TP-FT routings can results in better network performance in comparison with traditional FT routings. In our experiments, three different cases are simulated to demonstrate that the proposed TP-FT improves 2.9%~45.4% sustainable throughputs than traditional FT routings. Besides, we design two Built-in Self-Test/Self-Diagnosis (BIST/SD) and Fault-Isolation (FI) circuits to detect, locate, and isolate the impacts of the faulty FIFOs and MUXs in the fault routers. In our experiments, the BIST/SD of the 20PR can be executed in 117 constant test cycles and the STR can be executed in 144~376 test cycles. The extra overhead of the OCN using 20PRs increases 15.17%, while the OCNs with STRs increase 8.48%~13.3%. For irregular meshes, we propose a traffic-balanced routing algorithm, called OIP Avoidance Pre-Routing (OAPR), to solve the routing problems in the irregular meshes. The proposed OAPR can make traffic loads evenly spread on the networks and shorten average paths of packets. Therefore, the networks using the OAPR have lower latency and higher throughput than those using fault-tolerant routing algorithms. In our experiments, four different cases are simulated to demonstrate that the proposed OAPR improves 13.3%~100% sustainable throughputs than two previous fault-tolerant routing algorithms. Moreover, the hardware overhead of the OAPR is less than 1% compared to the cost of a whole router. Besides, the positions and orientations of oversized IPs (OIP positions/orientations) influence the network perofmrance hugely. We analyze the OIP positions/orientations based on OAPR and define some rules. According to these rules, designers can determine how to locate OIPs to achieve better network performance for the OCNs using the OAPR.

並列關鍵字

On-Chip Networks ； Mesh Topology ； Routing Algorithm ； Fault Tolerance

參考文獻

[24] R. Holsmark and S. Kumar, “Corrections to Chen and Chiu’s Fault Tolerant Routing Algorithm for Mesh Networks,” Journal of Information Science and Engineering, vol. 23, pp. 1649-1662, May 2007.

[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, “Network on chip: a new paradigm for systems on chip design,” IEEE Computer, vol. 35, pp. 70-78, Jan. 2002.

國際替代計量

適用於可調整式拓樸結構之網狀晶片內網路路由演算法與架構

全文下載

主題瀏覽