Regional ACO-Based Cascaded Adaptive Routing for Traffic Balancing in Mesh-Based Network-on-Chip Systems

• Published in: IEEE transactions on computers 2015-03, Vol.64 (3), p.868-875
• Main Authors: Chang, En-Jui, Hsin, Hsien-Kai, Chao, Chih-Hao, Lin, Shu-Yen, Wu, An-Yeu
• Format: Article
• Language: English
• Subjects: adaptive routing; Adaptive systems; ant colony optimization; Degradation; Network topology; Network-on-chip; Routing; routing table reduction; Throughput; Topology; Wide area networks
• ISSN: 0018-9340; 1557-9956
• DOI: 10.1109/TC.2013.2296032

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.