A Fast Two-Step Topology Reconfiguration Algorithm for Core-Level Fault Tolerance in NoCs

With the rapid increase in the number of processor cores integrated on Network-on-Chips (NoCs) and higher requirements for system reliability, fault tolerance is becoming a great challenge in the design process. In this paper, a fast two-step topology reconfiguration (FTTR) algorithm is proposed to solve the reconfiguration mapping problem in NoCs for core-level fault tolerance. By defining mapping domains and adopting the Hungarian Algorithm, an initial mapping is fast generated in the first step. This provides a near-optimal start for the next Tabu search and therefore brings great improvement on the second step. In the second step, Tabu Search is applied and modified to reduce the neighborhood search space and shorten execution time with almost no sacrifice on the final solution. Experiments show that the FTTR algorithm can significantly reduce the execution time while providing an efficient mapping solution for topology reconfiguration on various faulty core distribution cases.