{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T07:58:05Z","timestamp":1758268685710,"version":"3.41.0"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2015,5,19]],"date-time":"2015-05-19T00:00:00Z","timestamp":1431993600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"China National High Technologies Research Program"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Reconfigurable Technol. Syst."],"published-print":{"date-parts":[[2015,5,19]]},"abstract":"<jats:p>With an increasing number of processing elements (PEs) integrated on a single chip, fault-tolerant techniques are critical to ensure the reliability of such complex systems. In current reconfigurable architectures, redundant PEs are utilized for fault tolerance. In the presence of faulty PEs, the physical topologies of various chips may be different, so the concept of virtual topology from network embedding problem has been used to alleviate the burden for the operating systems. With limited hardware resources, how to reconfigure a system into the most effective virtual topology such that the maximum repair rate can be reached presents a significant challenge. In this article, a new approach using a maximum flow (MF) algorithm is proposed for an efficient topology reconfiguration in reconfigurable architectures. In this approach, topology reconfiguration is converted into a network flow problem by constructing a directed graph; the solution is then found by using the MF algorithm. This approach optimizes the use of spare PEs with minimal impacts on area, throughput, and delay, and thus it significantly improves the repair rate of faulty PEs. In addition, it achieves a polynomial reconfiguration time. Experimental results show that compared to previous methods, the MF approach increases the probability to repair faulty PEs by up to 50% using the same redundant resources. Compared to a fault-free system, the throughput only decreases by less than 2.5% and latency increases by less than 4%. To consider various types of PEs in a practical application, a cost factor is introduced into the MF algorithm. An enhanced approach using a minimum-cost MF algorithm is further shown to be efficient in the fault-tolerant reconfiguration of heterogeneous reconfigurable architectures.<\/jats:p>","DOI":"10.1145\/2700417","type":"journal-article","created":{"date-parts":[[2015,5,26]],"date-time":"2015-05-26T14:36:05Z","timestamp":1432650965000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Efficient Fault-Tolerant Topology Reconfiguration Using a Maximum Flow Algorithm"],"prefix":"10.1145","volume":"8","author":[{"given":"Yu","family":"Ren","sequence":"first","affiliation":[{"name":"Tsinghua University, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Leibo","family":"Liu","sequence":"additional","affiliation":[{"name":"Tsinghua University, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shouyi","family":"Yin","sequence":"additional","affiliation":[{"name":"Tsinghua University, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jie","family":"Han","sequence":"additional","affiliation":[{"name":"University of Alberta, Edmonton, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shaojun","family":"Wei","sequence":"additional","affiliation":[{"name":"Tsinghua University, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,5,19]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Retrieved","author":"ARM.","year":"2014","unstructured":"ARM. 2014 . AMBA Open Specifications . Retrieved April 10, 2015, from http:\/\/www.arm.com\/products\/system-ip\/amba\/amba-open-specifications.php. ARM. 2014. AMBA Open Specifications. Retrieved April 10, 2015, from http:\/\/www.arm.com\/products\/system-ip\/amba\/amba-open-specifications.php."},{"doi-asserted-by":"publisher","key":"e_1_2_1_2_1","DOI":"10.1145\/1278480.1278667"},{"doi-asserted-by":"publisher","key":"e_1_2_1_3_1","DOI":"10.5555\/1950815.1950906"},{"doi-asserted-by":"publisher","key":"e_1_2_1_4_1","DOI":"10.1109\/MM.2003.1225959"},{"doi-asserted-by":"publisher","key":"e_1_2_1_5_1","DOI":"10.1145\/378239.379048"},{"doi-asserted-by":"publisher","key":"e_1_2_1_6_1","DOI":"10.1145\/1999946.1999967"},{"doi-asserted-by":"publisher","key":"e_1_2_1_7_1","DOI":"10.1109\/NOCS.2012.10"},{"doi-asserted-by":"publisher","key":"e_1_2_1_8_1","DOI":"10.1145\/321694.321699"},{"doi-asserted-by":"publisher","key":"e_1_2_1_9_1","DOI":"10.1145\/1629911.1630119"},{"doi-asserted-by":"publisher","key":"e_1_2_1_10_1","DOI":"10.1109\/TNET.2003.810319"},{"doi-asserted-by":"publisher","key":"e_1_2_1_11_1","DOI":"10.1145\/48014.61051"},{"doi-asserted-by":"publisher","key":"e_1_2_1_12_1","DOI":"10.1088\/0957-4484\/14\/2\/324"},{"key":"e_1_2_1_13_1","volume-title":"Retrieved","author":"IEEE.","year":"2005","unstructured":"IEEE. 2005 . IEEE P1500 . Retrieved April 10, 2015, from http:\/\/grouper.ieee.org\/groups\/1500\/. IEEE. 2005. IEEE P1500. Retrieved April 10, 2015, from http:\/\/grouper.ieee.org\/groups\/1500\/."},{"doi-asserted-by":"publisher","key":"e_1_2_1_14_1","DOI":"10.1016\/j.jpdc.2012.01.017"},{"doi-asserted-by":"publisher","key":"e_1_2_1_15_1","DOI":"10.1109\/CIT.2010.395"},{"doi-asserted-by":"publisher","key":"e_1_2_1_16_1","DOI":"10.5555\/2492708.2492905"},{"doi-asserted-by":"publisher","key":"e_1_2_1_17_1","DOI":"10.1109\/JSSC.2009.2034408"},{"doi-asserted-by":"publisher","key":"e_1_2_1_18_1","DOI":"10.1109\/FPL.2005.1515723"},{"key":"e_1_2_1_19_1","first-page":"434","article-title":"Determining the maximal flow in a network by the approach of pre-flows","volume":"15","author":"Karzanov Alexander V.","year":"1974","unstructured":"Alexander V. Karzanov . 1974 . Determining the maximal flow in a network by the approach of pre-flows . Souviet Mathematics Doklady 15 , 434 -- 437 . Alexander V. Karzanov. 1974. Determining the maximal flow in a network by the approach of pre-flows. Souviet Mathematics Doklady 15, 434--437.","journal-title":"Souviet Mathematics Doklady"},{"doi-asserted-by":"publisher","key":"e_1_2_1_20_1","DOI":"10.1109\/PROC.1986.13532"},{"doi-asserted-by":"publisher","key":"e_1_2_1_21_1","DOI":"10.1109\/TCAD.2011.2106812"},{"doi-asserted-by":"publisher","key":"e_1_2_1_22_1","DOI":"10.1109\/CSNT.2014.214"},{"doi-asserted-by":"publisher","key":"e_1_2_1_23_1","DOI":"10.5555\/1413497.1413504"},{"doi-asserted-by":"publisher","key":"e_1_2_1_24_1","DOI":"10.1145\/2522968.2522976"},{"doi-asserted-by":"publisher","key":"e_1_2_1_25_1","DOI":"10.1016\/j.sysarc.2013.03.010"},{"doi-asserted-by":"publisher","key":"e_1_2_1_26_1","DOI":"10.1109\/JSSC.2010.2048149"},{"doi-asserted-by":"publisher","key":"e_1_2_1_27_1","DOI":"10.1145\/1084834.1084906"},{"volume-title":"Proceedings of the Hot Interconnects IV Symposium. 147--156","author":"Steven","unstructured":"Steven L. Scott and Gregory M. Thorson. 1996. The Cray T3E network: Adaptive routing in a high performance 3D torus . In Proceedings of the Hot Interconnects IV Symposium. 147--156 . Steven L. Scott and Gregory M. Thorson. 1996. The Cray T3E network: Adaptive routing in a high performance 3D torus. In Proceedings of the Hot Interconnects IV Symposium. 147--156.","key":"e_1_2_1_28_1"},{"key":"e_1_2_1_29_1","volume-title":"Operating Systems: Internals and Design Principles","author":"Stallings William","year":"2011","unstructured":"William Stallings . 2011 . Operating Systems: Internals and Design Principles ( 7 th ed.). Prentice Hall . William Stallings. 2011. Operating Systems: Internals and Design Principles (7th ed.). Prentice Hall.","edition":"7"},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the 2nd ACM\/IEEE International Symposium on Networks-on-Chip (NoCS\u201908)","author":"Mikkel","year":"2008","unstructured":"Mikkel B. Stensgaard and Jens Sparso. 2008. ReNoC: A network-on-chip architecture with reconfigurable topology . In Proceedings of the 2nd ACM\/IEEE International Symposium on Networks-on-Chip (NoCS\u201908) . 55--64. DOI:http:\/\/dx.doi.org\/10.1109\/NOCS. 2008 .4492725 10.1109\/NOCS.2008.4492725 Mikkel B. Stensgaard and Jens Sparso. 2008. ReNoC: A network-on-chip architecture with reconfigurable topology. In Proceedings of the 2nd ACM\/IEEE International Symposium on Networks-on-Chip (NoCS\u201908). 55--64. DOI:http:\/\/dx.doi.org\/10.1109\/NOCS.2008.4492725"},{"doi-asserted-by":"publisher","key":"e_1_2_1_31_1","DOI":"10.1109\/TEST.2006.297637"},{"doi-asserted-by":"publisher","key":"e_1_2_1_32_1","DOI":"10.1109\/12.247834"},{"doi-asserted-by":"publisher","key":"e_1_2_1_33_1","DOI":"10.1109\/TCAD.2012.2188801"},{"doi-asserted-by":"publisher","key":"e_1_2_1_34_1","DOI":"10.1109\/IBICA.2012.56"},{"doi-asserted-by":"publisher","key":"e_1_2_1_35_1","DOI":"10.1109\/TVLSI.2007.899234"},{"doi-asserted-by":"publisher","key":"e_1_2_1_36_1","DOI":"10.1145\/1403375.1403571"},{"doi-asserted-by":"publisher","key":"e_1_2_1_37_1","DOI":"10.1109\/TVLSI.2008.2002108"}],"container-title":["ACM Transactions on Reconfigurable Technology and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2700417","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2700417","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T05:07:44Z","timestamp":1750223264000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2700417"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,5,19]]},"references-count":37,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,5,19]]}},"alternative-id":["10.1145\/2700417"],"URL":"https:\/\/doi.org\/10.1145\/2700417","relation":{},"ISSN":["1936-7406","1936-7414"],"issn-type":[{"type":"print","value":"1936-7406"},{"type":"electronic","value":"1936-7414"}],"subject":[],"published":{"date-parts":[[2015,5,19]]},"assertion":[{"value":"2013-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-05-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}