{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:21:38Z","timestamp":1750306898355,"version":"3.41.0"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"2","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\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-0530261"],"award-info":[{"award-number":["CCF-0530261"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Des. Autom. Electron. Syst."],"published-print":{"date-parts":[[2013,3]]},"abstract":"<jats:p>We address the problem of optimizing fault tolerance in FPGA architectures with high defect rates (such as nano-FPGAs) without significantly degrading performance. Our methods address fault tolerance during the placement and reconfiguration stages of FPGA programming. First, we provide several complexity results for both the fault reconfiguration and fault-tolerance placement problems. Then, we propose a placement algorithm which, in the presence of randomly generated faults, optimizes spare placement to maximize the probability that the FPGA can be reconfigured to meet a specified timing constraint. We also give heuristics for reconfiguration after faults have been detected. Despite the hardness results for both the placement and reconfiguration problems, we show our heuristics perform well in simulation (in one scenario, increasing the probability of successful reconfiguration by as much as 55% compared to a uniform spare placement).<\/jats:p>","DOI":"10.1145\/2442087.2442104","type":"journal-article","created":{"date-parts":[[2013,4,9]],"date-time":"2013-04-09T12:17:58Z","timestamp":1365509878000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["The survivability of design-specific spare placement in FPGA architectures with high defect rates"],"prefix":"10.1145","volume":"18","author":[{"given":"Amit","family":"Agarwal","sequence":"first","affiliation":[{"name":"Microsoft"}]},{"given":"Jason","family":"Cong","sequence":"additional","affiliation":[{"name":"UCLA"}]},{"given":"Brian","family":"Tagiku","sequence":"additional","affiliation":[{"name":"Google"}]}],"member":"320","published-online":{"date-parts":[[2013,4,11]]},"reference":[{"volume-title":"Proceedings of the International Conference on Computer-Aided Design.","author":"Agarwal A.","key":"e_1_2_1_1_1"},{"key":"e_1_2_1_2_1","unstructured":"Bareisa E. Jusas V. Motiejunas K. and Seinauskas R. 2004. Testing of FPGA logic cells. Elektronika IR Elektrotechnica.  Bareisa E. Jusas V. Motiejunas K. and Seinauskas R. 2004. Testing of FPGA logic cells. Elektronika IR Elektrotechnica."},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"Betz V. Rose J. and Marquardt A. M. 1999. Architecture and CAD for Deep-Submicron FPGAs. Kluwer Academic Publishers.   Betz V. Rose J. and Marquardt A. M. 1999. Architecture and CAD for Deep-Submicron FPGAs. Kluwer Academic Publishers.","DOI":"10.1007\/978-1-4615-5145-4"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/2.48799"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142155.1142167"},{"volume-title":"Proceedings of the International Conference on Field Programmable Logic and Its Applications.","author":"Chen G.","key":"e_1_2_1_6_1"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1046192.1046200"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1088\/0957-4484\/14\/4\/311"},{"volume-title":"Proceedings of the ACM International Workshop on FPGAs.","author":"Durand S.","key":"e_1_2_1_9_1"},{"volume-title":"Proceedings of the 11th Annual IEEE International ASIC Conference.","author":"Emmert J.","key":"e_1_2_1_10_1"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVLSI.2007.891102"},{"key":"e_1_2_1_12_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 Company.   Garey M. R. and Johnson D. S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Company."},{"volume-title":"Proceedings of the International Conference on Computer Design. 326--331","author":"Hanchek F.","key":"e_1_2_1_13_1"},{"volume-title":"Proceedings of the 9th International Conference on VLSI Design. 225--229","author":"Hanchek F.","key":"e_1_2_1_14_1"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/CICC.1993.590575"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/92.273147"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"Huang Y. Duan X. Wei Q. and Lieber C. M. 2001. Directed assembly of one-dimensional nanostructures into functional networks. Science 291 5504 630--633.  Huang Y. Duan X. Wei Q. and Lieber C. M. 2001. Directed assembly of one-dimensional nanostructures into functional networks. Science 291 5504 630--633.","DOI":"10.1126\/science.291.5504.630"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2003.1244942"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/5.705525"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/2.56854"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/329166.329205"},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","unstructured":"Libeskind-Hadas R. Hasan N. Cong J. McKinley P. K. and Liu C. L. 1992. Fault Covering Problems in Reconfigurable VLSI Systems. Kluwer.   Libeskind-Hadas R. Hasan N. Cong J. McKinley P. K. and Liu C. L. 1992. Fault Covering Problems in Reconfigurable VLSI Systems. Kluwer.","DOI":"10.1007\/978-1-4615-3614-7"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1080\/1065514021000012011"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/296399.296426"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/329166.329208"},{"volume-title":"Proceedings of the Conference and Exhibition on Design, Automation and Test in Europe.","author":"Mathur A.","key":"e_1_2_1_26_1"},{"volume-title":"Proceedings of the International Test Conference.","author":"Mishra M.","key":"e_1_2_1_27_1"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.298034"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1723112.1723152"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.859538"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/647833.737850"},{"volume-title":"Proceedings of the International Symposium on Parallel Architectures, Algorithms and Networks. 24--29","author":"Tsuda N.","key":"e_1_2_1_32_1"},{"volume-title":"Proceedings of the International Symposium on VLSI Technology, Systems, and Applications.","author":"Wu C.","key":"e_1_2_1_33_1"}],"container-title":["ACM Transactions on Design Automation of Electronic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2442087.2442104","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2442087.2442104","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:19:06Z","timestamp":1750234746000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2442087.2442104"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,3]]},"references-count":33,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2013,3]]}},"alternative-id":["10.1145\/2442087.2442104"],"URL":"https:\/\/doi.org\/10.1145\/2442087.2442104","relation":{},"ISSN":["1084-4309","1557-7309"],"issn-type":[{"type":"print","value":"1084-4309"},{"type":"electronic","value":"1557-7309"}],"subject":[],"published":{"date-parts":[[2013,3]]},"assertion":[{"value":"2011-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-04-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}