A Two-Stage Degradation-Based Topology Reconfiguration Algorithm for Fault-Tolerant Multiprocessor Arrays

As the integration density of multiprocessor arrays increases, the likelihood of permanent faults in processing elements (PEs) rises, requiring effective topology reconfiguration for system reliability. However, existing router-based multiprocessor arrays reconfiguration methods predominantly rely on redundancy techniques and lack effective degradation strategies for applications of varying sizes. To address this, we propose a two-stage degradation-based topology reconfiguration algorithm to construct a maximized and high-performance logical array. First, we introduce a novel fault compensation mechanism by defining a set of faulty PE candidates to identify locally optimal fault-free PEs for compensation, minimizing the compensation path. Building upon this, we develop a greedy bidirectional column reconfiguration algorithm that constructs an initial fault-free logical array with short interconnects and prove its maximality. Lastly, we propose a satisfiability-based reconfiguration algorithm, transforming the topology reconfiguration problem into a satisfiability problem via a SAT model, reducing interconnect redundancy, and further optimizing array performance. Experimental results demonstrate that the proposed algorithm consistently outperforms state-of-the-art methods in reducing communication latency and alleviating link congestion, especially under high fault density conditions. Furthermore, as array size and fault density increase, the effectiveness of the proposed method becomes more pronounced, showcasing excellent scalability and robustness.