Ant Colony Optimization-Based Fault-Aware Routing in Mesh-Based Network-on-Chip Systems

作者：Hsin Hsien Kai^*; Chang En Jui; Lin Chia An; Wu An Yeu

来源：IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2014, 33(11): 1693-1705.

DOI：10.1109/TCAD.2014.2347922

• Ant colony optimization (ACO)
• fault-tolerant routing
• network-on-chip (NoC)

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.

• 出版日期2014-11
• 单位中国科学院电工研究所