Ant Colony Optimization-Based Fault-Aware Routing in Mesh-Based Network-on-Chip Systems
Authors:
- 16 October 2014
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
- Vol. 33 (11) , 1693-1705
Abstract
The advanced deep submicrometer technology increases the risk of failure for on-chip components. In advanced network-on-chip (NoC) systems, the failure constrains the on-chip bandwidth and network throughput. Fault-tolerant routing algorithms aim to alleviate the impact on performance. However, few works have integrated the congestion-, deadlock-, and fault-awareness information in channel evaluation function to avoid the hotspot around the faulty router. To solve this problem, we propose the ant colony optimization-based fault-aware routing (ACO-FAR) algorithm for load balancing in faulty networks. The behavior of an ant colony while facing an obstacle (failure in NoC) can be described in three steps: 1) encounter; 2) search; and 3) select. We implement the corresponding mechanisms as: 1) notification of fault information; 2) path searching mechanism; and 3) path selecting mechanism. With proposed ACO-FAR, the router can evaluate the available paths and detour packets through a less-congested fault-free path. The simulation results show that this paper has higher throughput than related works by 29.1%–66.5%. In addition, ACO-FAR can reduce the undelivered packet ratio to 0.5%–0.02% and balance the distribution of traffic flow in the faulty network.Keywords
Funding Information
- National Science Council (NSC 100-2221-E-002-001-MY3, NSC 103-2220-E-002-003)
This publication has 32 references indexed in Scilit:
- Spatial-Temporal Enhancement of ACO-Based Selection Schemes for Adaptive Routing in Network-on-Chip SystemsIEEE Transactions on Parallel and Distributed Systems, 2013
- Methods for fault tolerance in networks-on-chipACM Computing Surveys, 2013
- A scalable built-in self-recovery (BISR) VLSI architecture and design methodology for 2D-mesh based on-chip networksDesign Automation for Embedded Systems, 2011
- Living with Failure: Lessons from Nature?2006
- Ant colony optimization for routing and load-balancing: survey and new directionsIEEE Transactions on Systems, Man, and Cybernetics - Part A: Systems and Humans, 2003
- Route packets, net wires2001
- Ant algorithms and stigmergyFuture Generation Computer Systems, 2000
- Ant system: optimization by a colony of cooperating agentsIEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 1996
- Trails and U-turns in the selection of a path by the ant Lasius nigerJournal of Theoretical Biology, 1992
- Low-density parity-check codesIEEE Transactions on Information Theory, 1962