Topology Reconfiguration for NoCs: A Fast Reconfiguration Algorithm Based on Monotonic Path Shifting.

Abstract

With the advancement of semiconductor technology, the Network-on-Chip (NoC) has become a critical architecture for communication between multiple cores. However, failures caused by factors such as manufacturing processes can degrade its performance and stability, making efficient topology reconstruction algorithms particularly important. Conventional 2D mesh reconstruction yields irregular topologies, increasing network latency and complicating system scheduling and deployment. While REmesh structures maintain topological regularity, they struggle to balance algorithmic complexity, success rates, and reconstruction costs. This paper proposes a monotonic path shift (MPS) topological reconstruction algorithm for REmesh NoCs with core-level redundancy, based on local rapid recovery. This algorithm localizes reconstruction decisions by establishing monotonic paths between failed cores and redundant cores for recovery. It incorporates region retention and local fallback mechanisms to suppress path conflicts among multiple failed cores. Theoretical analysis shows that MPS provides an upper bound on the runtime of the algorithm, significantly reducing its time complexity. Experimental results indicate that its reconstruction success rate is comparable to that of the ACTR algorithm, with both maintaining a high repair rate even under high fault density. In terms of core reuse rate, MPS achieves significant improvements over BTTR, BSTR, and ACTR, with an average increase of approximately 10% under low-fault conditions, effectively utilizing remaining computational resources. Concurrently, the algorithm substantially reduces average migration time, accelerating recovery by several orders of magnitude in large-scale low-fault scenarios and markedly lowering online recovery overhead.