{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,25]],"date-time":"2025-10-25T21:58:36Z","timestamp":1761429516803,"version":"3.44.0"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"3","funder":[{"name":"Guangxi Natural Science Foundation of China","award":["2024GXNSFBA010248"],"award-info":[{"award-number":["2024GXNSFBA010248"]}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["62162004 and U21A20474"],"award-info":[{"award-number":["62162004 and U21A20474"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Guangxi Collaborative Innovation Center of Multi-source Information Integration and Intelligent Processing"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Archit. Code Optim."],"published-print":{"date-parts":[[2025,9,30]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1145\/3744907","type":"journal-article","created":{"date-parts":[[2025,6,16]],"date-time":"2025-06-16T07:17:43Z","timestamp":1750058263000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["A Two-Stage Degradation-Based Topology Reconfiguration Algorithm for Fault-Tolerant Multiprocessor Arrays"],"prefix":"10.1145","volume":"22","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5325-9997","authenticated-orcid":false,"given":"Hao","family":"Ding","sequence":"first","affiliation":[{"name":"School of Computer Science and Engineering, Guangxi Normal University, Guilin 541004,China, Guangxi Normal University Guangxi Key Laboratory of Multi-Source Information Mining and Security","place":["Guilin, China"]}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-1013-2337","authenticated-orcid":false,"given":"Peiling","family":"Song","sequence":"additional","affiliation":[{"name":"School of Computer Science and Engineering, Guangxi Normal University, Guilin 541004,China, Guangxi Normal University Guangxi Key Laboratory of Multi-Source Information Mining and Security","place":["Guilin, China"]}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-5988-2573","authenticated-orcid":false,"given":"Yelin","family":"Li","sequence":"additional","affiliation":[{"name":"School of Computer Science and Engineering, Guangxi Normal University, Guilin 541004,China, Guangxi Normal University Guangxi Key Laboratory of Multi-Source Information Mining and Security","place":["Guilin, China"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1325-6975","authenticated-orcid":false,"given":"Junyan","family":"Qian","sequence":"additional","affiliation":[{"name":"School of Computer Science and Engineering, Guangxi Normal University, Guilin 541004,China, Guangxi Normal University Guangxi Key Laboratory of Multi-Source Information Mining and Security","place":["Guilin, China"]}]}],"member":"320","published-online":{"date-parts":[[2025,9,17]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1109\/TEVC.2019.2912726"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1109\/TDMR.2005.853449"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1109\/2.976921"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1109\/TVLSI.2008.2009452"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1109\/HPCC.and.EUC.2013.125"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1109\/ASPDAC.2011.5722228"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2016.2588482"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2021.3090315"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1109\/JETCAS.2012.2193835"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1109\/COMST.2020.2986444"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2021.08.005"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2023.3337196"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.vlsi.2018.02.012"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPSW.2012.24"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1109\/TDSC.2009.53"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1109\/TDSC.2009.53"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1002\/tee.22628"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2023.3339961"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1587\/elex.13.20160930"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.vlsi.2015.08.002"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.sysarc.2018.10.001"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2019.2940190"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1016\/S1007-0214(07)70104-9"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1109\/TVLSI.2008.2002108"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1109\/WODES.2008.4605925"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1109\/43.662684"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1109\/TDSC.2019.2934098"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.sysarc.2018.10.003"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00607-010-0107-y"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2024.104904"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2020.3006571"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/2700417"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1613\/jair.1.15956"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1109\/ISCA.2005.44"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICCD.2012.6378613"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1109\/PRDC.2017.24"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1109\/PRDC.2018.00011"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1109\/EWDTS52692.2021.9581027"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2006.43"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2013.114"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1142\/S0218126619501111"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1109\/PDCAT.2012.99"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1109\/DATE.2010.5457060"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1109\/ASPDAC.2010.5419830"}],"container-title":["ACM Transactions on Architecture and Code Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3744907","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,17]],"date-time":"2025-09-17T13:44:54Z","timestamp":1758116694000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3744907"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,9,17]]},"references-count":44,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,9,30]]}},"alternative-id":["10.1145\/3744907"],"URL":"https:\/\/doi.org\/10.1145\/3744907","relation":{},"ISSN":["1544-3566","1544-3973"],"issn-type":[{"type":"print","value":"1544-3566"},{"type":"electronic","value":"1544-3973"}],"subject":[],"published":{"date-parts":[[2025,9,17]]},"assertion":[{"value":"2024-12-27","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-06-03","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-09-17","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}