{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:22:13Z","timestamp":1750306933787,"version":"3.41.0"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"1s","license":[{"start":{"date-parts":[[2013,3,1]],"date-time":"2013-03-01T00:00:00Z","timestamp":1362096000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100004963","name":"Seventh Framework Programme","doi-asserted-by":"publisher","award":["287611"],"award-info":[{"award-number":["287611"]}],"id":[{"id":"10.13039\/501100004963","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Embed. Comput. Syst."],"published-print":{"date-parts":[[2013,3]]},"abstract":"<jats:p>\n            In this article, new heuristic-search methods and algorithms are presented for enabling highly efficient and adaptive, defect-tolerant multiprocessor arrays. We consider systems where a homogeneous multiprocessor array lies on top of reconfigurable interconnects which allow the pipeline stages of the processors to be connected in all possible configurations. Considering the multiprocessor array partitioned in substitutable units at the granularity of pipeline stages, we employ a variety of heuristic-search methods and algorithms to isolate and replace defective units. The proposed heuristics are designed for off-line execution and aim at minimizing the performance overhead necessarily introduced to the array by the interconnects' latency. An empirical evaluation of the designed algorithms is then carried out, in order to assess the targeted problem and the efficacy of our approach. Our findings indicate this to be a NP-complete computational problem, however, our heuristic-search methods can achieve, for the problem sizes we exhaustively searched, 100% accuracy in finding the optimal solution among 10\n            <jats:sup>19<\/jats:sup>\n            possible candidates within 2.5 seconds. Alternatively, they can provide near-optimal solutions at an accuracy which consistently exceeds 70% (compared to the optimal solution) in only 10\n            <jats:sup>-4<\/jats:sup>\n            seconds.\n          <\/jats:p>","DOI":"10.1145\/2435227.2435240","type":"journal-article","created":{"date-parts":[[2013,3,19]],"date-time":"2013-03-19T13:34:23Z","timestamp":1363700063000},"page":"1-23","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Heuristic search for adaptive, defect-tolerant multiprocessor arrays"],"prefix":"10.1145","volume":"12","author":[{"given":"Vasileios","family":"Vasilikos","sequence":"first","affiliation":[{"name":"Delft University of Technology, The Netherlands"}]},{"given":"Georgios","family":"Smaragdos","sequence":"additional","affiliation":[{"name":"Delft University of Technology, The Netherlands"}]},{"given":"Christos","family":"Strydis","sequence":"additional","affiliation":[{"name":"Erasmus University Medical Center, The Netherlands"}]},{"given":"Ioannis","family":"Sourdis","sequence":"additional","affiliation":[{"name":"Chalmers University of Technology, Sweden"}]}],"member":"320","published-online":{"date-parts":[[2013,3,21]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250662.1250720"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/MDT.2008.107"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/MM.2005.110"},{"key":"e_1_2_1_4_1","unstructured":"Cormen T. Leiserson C. Rivest R. and Stein C. 2003. Introduction to Algorithms 2nd Ed. McGraw-Hill Science\/Engineering\/Math.   Cormen T. Leiserson C. Rivest R. and Stein C. 2003. Introduction to Algorithms 2nd Ed. McGraw-Hill Science\/Engineering\/Math."},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the IEEE International Workshop on Design & Test of Defect-Tolerant Nanoscale Archit (NANOARCH).","author":"Bhaduri S. K.","year":"2005","unstructured":"D. Bhaduri , S. K. Shukla , P. G. M. G. 2005 . Reliability analysis of fault-tolerant reconfigurable architectures . In Proceedings of the IEEE International Workshop on Design & Test of Defect-Tolerant Nanoscale Archit (NANOARCH). D. Bhaduri, S. K. Shukla, P. G. M. G. 2005. Reliability analysis of fault-tolerant reconfigurable architectures. In Proceedings of the IEEE International Workshop on Design & Test of Defect-Tolerant Nanoscale Archit (NANOARCH)."},{"key":"e_1_2_1_6_1","unstructured":"Garey M. R. and Johnson D. S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Co. San Francisco CA.   Garey M. R. and Johnson D. S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Co. San Francisco CA."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/PRDC.2009.39"},{"key":"e_1_2_1_8_1","volume-title":"Genetic Algorithms in Search, Optimization and Machine Learning","author":"Goldberg D. E.","unstructured":"Goldberg , D. E. 1989. Genetic Algorithms in Search, Optimization and Machine Learning 1 st Ed. Addison-Wesley Longman Publishing Co., Inc. , Boston, MA . Goldberg, D. E. 1989. Genetic Algorithms in Search, Optimization and Machine Learning 1st Ed. Addison-Wesley Longman Publishing Co., Inc., Boston, MA.","edition":"1"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/DSN.2010.5544915"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/MICRO.2008.4771786"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2010.205"},{"volume-title":"Proceedings of the Reconfigurable and Adaptive Architecture Workshop (RAAW).","author":"Gupta S.","key":"e_1_2_1_12_1","unstructured":"Gupta , S. , Feng , S. , Blome , J. , and Mahlke , S . 2007. Stagenet: A reconfigurable cmp fabric for resilient systems . In Proceedings of the Reconfigurable and Adaptive Architecture Workshop (RAAW). Gupta, S., Feng, S., Blome, J., and Mahlke, S. 2007. Stagenet: A reconfigurable cmp fabric for resilient systems. In Proceedings of the Reconfigurable and Adaptive Architecture Workshop (RAAW)."},{"key":"e_1_2_1_13_1","volume-title":"Reconfigurable Computing: The Theory and Practice of FPGA-Based Computation","author":"Hauck S.","year":"2007","unstructured":"Hauck , S. and DeHon , A. 2007 . Reconfigurable Computing: The Theory and Practice of FPGA-Based Computation . Morgan Kaufmann Publishers Inc ., San Francisco, CA. Hauck, S. and DeHon, A. 2007. Reconfigurable Computing: The Theory and Practice of FPGA-Based Computation. Morgan Kaufmann Publishers Inc., San Francisco, CA."},{"key":"e_1_2_1_14_1","unstructured":"Hennessy J. L. and Patterson D. A. 2007. Computer Architecture\u2014A Quantitative Approach 4th Ed.   Hennessy J. L. and Patterson D. A. 2007. Computer Architecture\u2014A Quantitative Approach 4th Ed."},{"key":"e_1_2_1_15_1","unstructured":"Hoos H. H. and Stuetzle T. 2004. Stochastic Local Search: Foundations and Applications.   Hoos H. H. and Stuetzle T. 2004. Stochastic Local Search: Foundations and Applications."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/795659.795910"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVLSI.2007.891102"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.220.4598.671"},{"volume-title":"The Art of Computer Programming","author":"Knuth D. E.","key":"e_1_2_1_19_1","unstructured":"Knuth , D. E. 2011. The Art of Computer Programming , Volume 4A: Combinatorial Algorithms, Part 1 . Addison-Wesley Professional . Knuth, D. E. 2011. The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1. Addison-Wesley Professional."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1555754.1555769"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/MM.2010.79"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/AERO.2006.1655959"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCD.1988.25724"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1454115.1454124"},{"key":"e_1_2_1_25_1","volume-title":"Discrete Mathematics and Its Applications","author":"Rosen K. H.","unstructured":"Rosen , K. H. 2002. Discrete Mathematics and Its Applications 5 th Ed. McGraw-Hill Higher Education . Rosen, K. H. 2002. Discrete Mathematics and Its Applications 5th Ed. McGraw-Hill Higher Education.","edition":"5"},{"volume-title":"Fpgas with reconfigurable fault-tolerant redundancy. NASA Tech briefs MSC-24464-1","author":"Shuler","key":"e_1_2_1_26_1","unstructured":"Shuler , Robert, J. 2010. Fpgas with reconfigurable fault-tolerant redundancy. NASA Tech briefs MSC-24464-1 , NASA Center, Johnson Space Center . Shuler, Robert, J. 2010. Fpgas with reconfigurable fault-tolerant redundancy. NASA Tech briefs MSC-24464-1, NASA Center, Johnson Space Center."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/MICRO.2006.42"},{"key":"e_1_2_1_29_1","volume-title":"Artificial Intelligence: A Modern Approach","author":"Stuart R.","year":"2003","unstructured":"Stuart , R. and Peter , N . 2003 . Artificial Intelligence: A Modern Approach 2 nd Ed. Prentice Hall . Stuart, R. and Peter, N. 2003. Artificial Intelligence: A Modern Approach 2nd Ed. Prentice Hall.","edition":"2"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/MDT.2006.145"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/FPT.2010.5681773"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00940812"}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2435227.2435240","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2435227.2435240","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:35:40Z","timestamp":1750235740000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2435227.2435240"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,3]]},"references-count":31,"journal-issue":{"issue":"1s","published-print":{"date-parts":[[2013,3]]}},"alternative-id":["10.1145\/2435227.2435240"],"URL":"https:\/\/doi.org\/10.1145\/2435227.2435240","relation":{},"ISSN":["1539-9087","1558-3465"],"issn-type":[{"type":"print","value":"1539-9087"},{"type":"electronic","value":"1558-3465"}],"subject":[],"published":{"date-parts":[[2013,3]]},"assertion":[{"value":"2011-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-03-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}