Efficient topology reconfiguration for NoC-based multiprocessors: A greedy-memetic algorithm

• Published in: Journal of parallel and distributed computing 2024-08, Vol.190, p.104904, Article 104904
• Main Authors: Qian, Junyan, Zhang, Chuanfang, Wu, Zheng, Ding, Hao, Li, Long
• Format: Article
• Language: English
• Subjects: Algorithm; Core-level redundancy; Fault-tolerant; Multiprocessor array; Network on chip; Topology reconfiguration
• ISSN: 0743-7315; 1096-0848
• DOI: 10.1016/j.jpdc.2024.104904

In multi-core processor systems, the Network-on-Chip (NoC) serves as a vital communication infrastructure. To ensure chip reliability during potential failures, this paper proposes a two-level topology reconfiguration algorithm with core-level redundancy technology. Initially, a heuristic topology reconfiguration method utilizing a greedy strategy is proposed to perform local replacement of faulty processing elements (PEs) and generate an initial logical topology with shorter interconnection paths between PEs. Then, an intelligent optimization method based on memetic algorithm is introduced to optimize the generated initial topology for better communication performance. The experimental results demonstrate that compared to the current state-of-the-art algorithm, the proposed algorithm achieves an average improvement of 13.92% and 30.83% on various size topologies in terms of distance factor (DF) and congestion factor (CF), which represent communication delay and traffic balance respectively. The proposed algorithm significantly enhances the communication performance of the target topology, mitigating communication latency and potential congestion problems. •The candidate set aids greedy selection for optimal fault-free PE replacements.•Local greedy strategy reduces communication delay, eases congestion issues.•Memetic algorithm further optimizes the target topology in the reconfiguration.•The proposed algorithms show strong stability, adaptability in large-scale arrays.