Traffic-Balanced Routing Algorithm for Irregular Mesh-Based On-Chip Networks
Date Issued
2007
Date
2007
Author(s)
Huang, Chun-Hsiang
DOI
en-US
Abstract
On-chip networks (OCNs) have been proposed to solve increasing scale and complexity of the designs in nano-scale VLSI designs. In OCNs, the concept of irregular mesh is an important issue because IPs with different sizes can be supported. In order to solve routing on irregular mesh, modified routing algorithms to detour oversized IPs (OIPs) are needed. Fault-tolerant routing algorithms have been thought as solutions for irregular mesh because of the similar topology, faulty mesh, in multicomputer system. However, directly applying fault-tolerant routing algorithms may cause two serious problems: 1) heavy traffic loads around OIPs and unbalanced traffic loads on irregular meshes, 2) some paths of packets much longer than minimal path. In this thesis, we propose an OIP avoidance pre-routing (OAPR) algorithm to solve the aforementioned problems. OAPR can make traffic loads even spread on the networks, and shorten some paths of packets. Therefore, the networks using OAPR have lower latency and higher throughput than those using fault-tolerant routing algorithms. In our experiments, three different cases are simulated to demonstrate that proposed OAPR improve 55.6% ~ 100% sustainable throughputs than two cited fault-tolerant routing algorithm, Chen and Chiu’s algorithm [15] and extended XY routing algorithm [17]. Finally, we implement OAPR into hardware. The area overhead of OAPR is less than 1% compared to a whole router [24]. OAPR algorithm has good performance and is practical for irregular mesh-based OCNs.
Subjects
晶片內網路
路由演算法
非規則網狀網路
On-chip networks
routing algorithm
irregular mesh
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-96-R94943031-1.pdf
Size
23.31 KB
Format
Adobe PDF
Checksum
(MD5):94c8d852b61fd774c12834812e60fbac