Routing Algorithms and Architectures for Mesh-Based On-Chip Networks with Adjustable Topology
Date Issued
2009
Date
2009
Author(s)
Lin, Shu-Yen
Abstract
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.
Subjects
On-Chip Networks
Mesh Topology
Routing Algorithm
Fault Tolerance
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-98-D93943010-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):7aeab45cc93778e738853c86024cc5ad