ACO-based Adaptive Routing with Pheromone Diffusion for Network-on-Chip Systems
Date Issued
2012
Date
2012
Author(s)
Su, Kuan-Yu
Abstract
This thesis proposes an adaptive routing algorithm for Network-on-Chip (NoC) systems. With the algorithm which adopts the Ant Colony Optimization (ACO) algorithm and applies the concept of Pheromone Diffusion, the network throughput is increased and the latency is decreased, improving the network performance. ACO is a problem-solving technique inspired by the behavior of real-world ant colony. ACO-based routing also has high potential on balancing the traffic load in the domain of NoC, where the performance is generally dominated by the traffic distribution and routing.
The algorithm proposed utilizes the pheromone information in the ACO algorithm, which provides the temporal network information. Moreover, it further adopts the concept of Pheromone Diffusion, which diffuses the pheromone outward and the spatial network information is thus exchanged. With the acquirement of both spatial and temporal network information, each router is able to expand an information region in the shape of a pyramid. The size and shape of this information region are controllable by setting the parameters in this algorithm. According to our analysis, the information used in the related works such as OBL, RCA, and ACO are all within this region. In other words, the algorithm proposed in this thesis can not only attain the largest information region, but also perform the same performance as other related works with the corresponding settings. Moreover, this thesis discusses the physical meaning and the influence on network performance of each design parameter. Finally, the hardware design of the corresponding router architecture is also implemented and analyzed. The results show an improvement of 10.04% on network performance and the highest area efficiency achieved by the algorithm proposed.
Subjects
Network-on-Chip (NoC)
Adaptive Routing Algorithm
Ant Colony Optimization (ACO)
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-101-R99943047-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):7ca229632e6f0efd583bf3d50b621289