Regional ACO-Based Cascaded Adaptive Routing for Traffic Balancing in Mesh-Based Network-on-Chip Systems
Authors:
- 16 January 2014
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. 64 (3) , 868-875
Abstract
The regular topology of mesh-based network-on-chip (NoC) provides flexible and scalable architecture for chip multiprocessor (CMP) systems. However, as the complexity of network increases, routing problems become performance bottlenecks. In the field of wide area networks (WANs), ant colony optimization (ACO) has been applied to an adaptive routing for improving performance and achieving load balancing. Nevertheless, if we directly apply ACO to NoC systems, the implementation cost of ACO is excessively high. To overcome this problem, the ACO-based adaptive routing must be reformulated while considering both router cost and NoC efficiency. This work proposes the regional ACO-based cascaded adaptive routing (RACO-CAR) scheme with the following techniques: 1) table elimination by removing redundant information, 2) table sharing by grouping pheromone information to merge table content, and 3) cascaded routing that assigns traffic to different uncongested regions to balance traffic. Our experimental results demonstrate that the RACO-CAR scheme has an improvement of 3.9-36.84 percent in saturation throughput compared with existing adaptive routing schemes. The implementation cost of the RACO-CAR router is only 37.4 percent of that of the ACO-based router with full routing table. Therefore, the proposed RACO-CAR scheme has high area efficiency, defined as saturation throughput divided by the total cost of router.Keywords
This publication has 30 references indexed in Scilit:
- Performance analysis of the AntNet algorithmComputer Networks, 2007
- Performance Evaluation and Design Trade-Offs for Network-on-Chip Interconnect ArchitecturesIEEE Transactions on Computers, 2005
- An Extension of Ant Colony System to Continuous Optimization Problems2004
- Ant colony optimization for routing and load-balancing: survey and new directionsIEEE Transactions on Systems, Man, and Cybernetics - Part A: Systems and Humans, 2003
- A short convergence proof for a class of ant colony optimization algorithmsIEEE Transactions on Evolutionary Computation, 2002
- Performance Tuning of Adaptive Wormhole Routing through Selection Function ChoiceJournal of Parallel and Distributed Computing, 2002
- ACO algorithms with guaranteed convergence to the optimal solutionInformation Processing Letters, 2002
- The odd-even turn model for adaptive routingIEEE Transactions on Parallel and Distributed Systems, 2000
- On the Influence of the Selection Function on the Performance of Networks of Workstations2000
- Virtual-channel flow controlIEEE Transactions on Parallel and Distributed Systems, 1992