吳安宇Wu, An-Yeu (Andy)臺灣大學:電子工程學研究所林書彥Lin, Shu-YenShu-YenLin2010-07-142018-07-102010-07-142018-07-102009U0001-1607200919011500http://ntur.lib.ntu.edu.tw//handle/246246/189134晶片內網路已被提出來解決未來複雜的晶片內通訊問題。在本論文中，我們針對可調整式拓樸結構之網狀晶片內網路來探討，包含故障格狀網路與非規則格狀網路。針對故障格狀網路，我們提出路徑穿越容錯繞進演算法（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%. or 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.Acknowledgment (致謝) I文摘要 IIIbstract Vontents VIIists of Figures IXists of Tables XIVhapter 1 Introduction 1.1 Background 1.2 Motivation and Goal 7hapter 2 Reviews of Mesh-Based On-Chip Networks and Routing Algorithms 13.1 An Overview of Mesh-Based Topologies 13.1.1 2D mesh Topology 13.1.2 Irregular Mesh Topology 14.1.3 Faulty Mesh Topology 15.2 Fault-Tolerant Routing algorithms 16.2.1 Extended XY Routing (E-XY) 17.2.2 Chen and Chiu’s Routing Algorithm (Chen and Chiu’s) 20.2.3 Modified X-First Routing (MXF) 21.3 Testing Mechanisms for Faulty Meshes 23.3.1 DfT-based Solutions 23.3.2 BIST-based Solutions 24hapter 3 Through-Path Fault-Tolerant Routing Algorithms 26.1 20-Path Router Model 27.2 Searching Algorithm for the Through Paths 29.3 Through-Path Fault-Tolerant (TP-FT) Routing Algorithm 30.3.1 Through-Path Modified X-First (TP-MXF) Routing 30.3.2 Through-Path Extended XY (TP-E-XY) Routing 32.3.3 Through-Path Chen and Chiu’s (TP- Chen and Chiu’s) Routing 32.4 Experiments and Performance Analysis 35.4.1 Traffics of Single F-ring 36.4.2 Traffics of Multiple F-rings 44.4.3 Traffics of Multiple F-chains 47hapter 4 Built-in Self-Test/Self-Diagnosis and Fault-Isolation Architectures 49.1 20-Path Router Architecture (20PR) 50.1.1 Architecture of a Generic XY Router 51.1.2 BIST and BISD Circuit 52.1.3 Fault-Isolation Circuit 55.2 Surrounding Test Ring (STR) 56.2.1 Test, Diagnosis, and Isolation Methods 59.2.2 Architecture of STR 66.3 Implementations and Experiments 68.3.1 Overhead 68.3.2 Testability of the BIST/SD 69hapter 5 OIP Avoidance Pre-Routing (OAPR) Algorithm 71.1 Default Routing 73.2 Single OIP 73.3 Multiple OIPs 76.4 f-chain 78.5 Hardware Overhead of the OAPR 81hapter 6 Performance Evaluation and Hardware Overhead of OAPR 84.1 Traffics of Single OIP 85.2 Traffics of Multiple OIPs 89.3 Traffics of an f-ring and f-chains 91.4 A Case Study: A MultiMedia System 94hapter 7 Positions and Orientations of Oversized IPs 96.1 Restrictions on OIP Locations 97.2 Rule of OIP Positions/Orientations based on OAPR 98.3 Rules of OIP Positions/Orientations for Multiple OIPs 102hapter 8 Conclusions and Future Works 106.1 Conclusions 106.2 Future Works 107ibliography 1096103183 bytesapplication/pdfen-US晶片內網路網狀拓樸路由演算法容錯On-Chip NetworksMesh TopologyRouting AlgorithmFault Tolerancethesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/189134/1/ntu-98-D93943010-1.pdf