{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,10]],"date-time":"2025-11-10T13:36:43Z","timestamp":1762781803747,"version":"3.41.0"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2013,9,1]],"date-time":"2013-09-01T00:00:00Z","timestamp":1377993600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. Emerg. Technol. Comput. Syst."],"published-print":{"date-parts":[[2013,9]]},"abstract":"<jats:p>Several emerging nano-technologies, including crossbar nano-architectures, have recently been studied as possible replacement or supplement to CMOS technology in the future. However, extreme process variation and high failure rates, mainly due to atomic device sizes, are major challenges for crossbar nano-architectures.<\/jats:p>\n          <jats:p>\n            This article presents variation- and defect-tolerant logic mapping on crossbar nano-architectures. Since variation\/defect-aware mapping is an NP-hard problem, we introduce a set of\n            <jats:italic>Integer Linear Programming<\/jats:italic>\n            (ILP) formulations to effectively solve the problem in a reasonable time. The proposed ILP formulations can be used for both diode-based and FET-based crossbars. Experimental results on benchmark circuits show that our approach can reduce the critical-path delay 39% compared to the\n            <jats:italic>Simulated Annealing (SA)<\/jats:italic>\n            method. It can also successfully achieve 97% defect-free mapping with 40% defect density. It can tolerate process variations to meet timing constraints in 95% of the cases, compared to only 77% achieved by SA.\n          <\/jats:p>","DOI":"10.1145\/2491680","type":"journal-article","created":{"date-parts":[[2013,10,3]],"date-time":"2013-10-03T13:37:30Z","timestamp":1380807450000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["ILP formulations for variation\/defect-tolerant logic mapping on crossbar nano-architectures"],"prefix":"10.1145","volume":"9","author":[{"given":"Masoud","family":"Zamani","sequence":"first","affiliation":[{"name":"Northeastern University, Boston, MA"}]},{"given":"Hanieh","family":"Mirzaei","sequence":"additional","affiliation":[{"name":"Boston University, Boston, MA"}]},{"given":"Mehdi B.","family":"Tahoori","sequence":"additional","affiliation":[{"name":"Karlsruhe Institute of Technology, Karlsruhe, Germany"}]}],"member":"320","published-online":{"date-parts":[[2013,10,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/563952.563950"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1063\/1.1543252"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/VLSI.2008.44"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNANO.2003.808508"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1084748.1084750"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1002\/1521-3773(20020118)41:2<353::AID-ANIE353>3.0.CO;2-Y"},{"key":"e_1_2_1_7_1","unstructured":"Garey M. and Johnson D. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman & Co. New York.   Garey M. and Johnson D. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman & Co. New York."},{"volume-title":"Proceedings of the IEEE International Conference on Field-Programmable Technology (FPT'09)","author":"Gojman B.","key":"e_1_2_1_8_1","unstructured":"Gojman , B. and Dehon , A . 2009. VMATCH: Using logical variation to counteract physical variation in bottom-up, nanoscale systems . In Proceedings of the IEEE International Conference on Field-Programmable Technology (FPT'09) . 78--87. Gojman, B. and Dehon, A. 2009. VMATCH: Using logical variation to counteract physical variation in bottom-up, nanoscale systems. In Proceedings of the IEEE International Conference on Field-Programmable Technology (FPT'09). 78--87."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/379240.379262"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Heath J. R. Kuekes P. J. Snider G. S. and Williams R. S. 1998. A defect-tolerant computer architecture: Opportunities for nanotechnology. Sci. 280 5370 1716--1721.  Heath J. R. Kuekes P. J. Snider G. S. and Williams R. S. 1998. A defect-tolerant computer architecture: Opportunities for nanotechnology. Sci. 280 5370 1716--1721.","DOI":"10.1126\/science.280.5370.1716"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10836-006-0547-7"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1021\/nl073225h"},{"volume-title":"Proceedings of the IEEE International Symposium on Defect and Fault Tolerance in VLSI Systems (DFT'07)","author":"Joshi M.","key":"e_1_2_1_13_1","unstructured":"Joshi , M. and Al-Assadi , W . 2007. Nanofabric PLA architecture with redundancy enhancement . In Proceedings of the IEEE International Symposium on Defect and Fault Tolerance in VLSI Systems (DFT'07) . 427--438. Joshi, M. and Al-Assadi, W. 2007. Nanofabric PLA architecture with redundancy enhancement. In Proceedings of the IEEE International Symposium on Defect and Fault Tolerance in VLSI Systems (DFT'07). 427--438."},{"key":"e_1_2_1_14_1","first-page":"211","article-title":"A new method of solving some classes of extremal problems","volume":"28","author":"Kantorovich L. V.","year":"1940","unstructured":"Kantorovich , L. V. 1940 . A new method of solving some classes of extremal problems . Comptes Rendus (Dok-lady) Acad. Sci. USSR 28 , 5, 211 -- 214 . Kantorovich, L. V. 1940. A new method of solving some classes of extremal problems. Comptes Rendus (Dok-lady) Acad. Sci. USSR 28, 5, 211--214.","journal-title":"Comptes Rendus (Dok-lady) Acad. Sci. USSR"},{"key":"e_1_2_1_15_1","first-page":"1","article-title":"Experimental demonstration of a defect-tolerant nanocrossbar demultiplexer","volume":"19","author":"Li Z.","year":"2008","unstructured":"Li , Z. , Pickett , M. , Stewart , D. , Ohlberg , D. A. , Li , X. , Wu , W. , Robinett , W. , and Williams , S. 2008 . Experimental demonstration of a defect-tolerant nanocrossbar demultiplexer . Nanotechnol. 19 , 16, 1 -- 5 . Li, Z., Pickett, M., Stewart, D., Ohlberg, D. A., Li, X., Wu, W., Robinett, W., and Williams, S. 2008. Experimental demonstration of a defect-tolerant nanocrossbar demultiplexer. Nanotechnol. 19, 16, 1--5.","journal-title":"Nanotechnol."},{"key":"e_1_2_1_16_1","first-page":"50","article-title":"The incredible shrinking circuit. Sci","volume":"285","author":"Lieber C.","year":"2001","unstructured":"Lieber , C. 2001 . The incredible shrinking circuit. Sci . Amer. 285 , 50 -- 56 . Lieber, C. 2001. The incredible shrinking circuit. Sci. Amer. 285, 50--56.","journal-title":"Amer."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/MWSCAS.2010.5548550"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1038\/nmat2028"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1049\/iet-cdt.2008.0128"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASYNC.2008.22"},{"volume-title":"Proceedings of the IEEE International Conference on Field-Programmable Technology (FPT'04)","author":"Naeimi H.","key":"e_1_2_1_21_1","unstructured":"Naeimi , H. and Dehon , A . 2004. A greedy algorithm for tolerating defective crosspoints in nanoPLA design . In Proceedings of the IEEE International Conference on Field-Programmable Technology (FPT'04) . 49--56. Naeimi, H. and Dehon, A. 2004. A greedy algorithm for tolerating defective crosspoints in nanoPLA design. In Proceedings of the IEEE International Conference on Field-Programmable Technology (FPT'04). 49--56."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/TED.2007.901882"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/VTS.2006.61"},{"volume-title":"Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'07)","author":"Rao W.","key":"e_1_2_1_24_1","unstructured":"Rao , W. , Orailoglu , A. , and Karri , R . 2007. Logic level fault tolerance approaches targeting nanoelectronics plas . In Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'07) . 1--5. Rao, W., Orailoglu, A., and Karri, R. 2007. Logic level fault tolerance approaches targeting nanoelectronics plas. In Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'07). 1--5."},{"key":"e_1_2_1_25_1","unstructured":"RASP. 2013. http:\/\/cadlab.cs.ucla.edu\/software_release\/rasp\/htdocs\/.  RASP. 2013. http:\/\/cadlab.cs.ucla.edu\/software_release\/rasp\/htdocs\/."},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","unstructured":"Rueckes T. Kim K. Joselevich E. Tseng G. Y. Cheung C. and Lieber C. M. 2000. Carbon nanotube-based nonvolatile random access memory for molecular computing. Sci. 289 5476 94--97.  Rueckes T. Kim K. Joselevich E. Tseng G. Y. Cheung C. and Lieber C. M. 2000. Carbon nanotube-based nonvolatile random access memory for molecular computing. Sci. 289 5476 94--97.","DOI":"10.1126\/science.289.5476.94"},{"volume-title":"Proceedings of the International Symposium on Computer Architecture (ISCAS'09)","author":"Shrestha A.","key":"e_1_2_1_27_1","unstructured":"Shrestha , A. , Tayu , S. , and Ueno , S . 2009. Orthogonal ray graphs and nano-pla design . In Proceedings of the International Symposium on Computer Architecture (ISCAS'09) . 2930--2933. Shrestha, A., Tayu, S., and Ueno, S. 2009. Orthogonal ray graphs and nano-pla design. In Proceedings of the International Symposium on Computer Architecture (ISCAS'09). 2930--2933."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1088\/0957-4484\/15\/8\/003"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1088\/0957-4484\/18\/3\/035204"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2003.818327"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1088\/0957-4484\/16\/6\/045"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/TED.2003.816523"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1167943.1167945"},{"volume-title":"Proceedings of the IEEE VLSI Test Symposium (VTS'10)","author":"Tunc C.","key":"e_1_2_1_34_1","unstructured":"Tunc , C. and Tahoori , M . 2010a. On-the-fly variation tolerant mapping in crossbar nano-architectures . In Proceedings of the IEEE VLSI Test Symposium (VTS'10) . 105--110. Tunc, C. and Tahoori, M. 2010a. On-the-fly variation tolerant mapping in crossbar nano-architectures. In Proceedings of the IEEE VLSI Test Symposium (VTS'10). 105--110."},{"volume-title":"Proceedings of the Asia and South Pacific Design Automation Conference (ASP-DAC'10)","author":"Tunc C.","key":"e_1_2_1_35_1","unstructured":"Tunc , C. and Tahoori , M . 2010b. Variation tolerant logic mapping for crossbar array nano architectures . In Proceedings of the Asia and South Pacific Design Automation Conference (ASP-DAC'10) . 855--860. Tunc, C. and Tahoori, M. 2010b. Variation tolerant logic mapping for crossbar array nano architectures. In Proceedings of the Asia and South Pacific Design Automation Conference (ASP-DAC'10). 855--860."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/DFT.2011.39"},{"key":"e_1_2_1_37_1","doi-asserted-by":"crossref","unstructured":"Wu Y. Xiang J. Yang C. Lu W. and Lieber C. M. 2003. Single-crystal metallic nanowires and metal\/semiconductor nanowire heterostructures. Nature 430 6995 61--65.  Wu Y. Xiang J. Yang C. Lu W. and Lieber C. M. 2003. Single-crystal metallic nanowires and metal\/semiconductor nanowire heterostructures. Nature 430 6995 61--65.","DOI":"10.1038\/nature02674"},{"volume-title":"Proceedings of the 20th IEEE North Atlantic Test Workshop (NATW'11)","author":"Zamani M.","key":"e_1_2_1_38_1","unstructured":"Zamani , M. and Tahoori , M. B . 2011a. Variation tolerance for nano-pla architectures . In Proceedings of the 20th IEEE North Atlantic Test Workshop (NATW'11) . Zamani, M. and Tahoori, M. B. 2011a. Variation tolerance for nano-pla architectures. In Proceedings of the 20th IEEE North Atlantic Test Workshop (NATW'11)."},{"volume-title":"Proceedings of the Asia and South Pacific Design Automation Conference (ASP-DAC). 317--322","author":"Zamani M.","key":"e_1_2_1_39_1","unstructured":"Zamani , M. and Tahoori , M . 2011b. Variation-aware logic mapping for crossbar nano-architectures . In Proceedings of the Asia and South Pacific Design Automation Conference (ASP-DAC). 317--322 . Zamani, M. and Tahoori, M. 2011b. Variation-aware logic mapping for crossbar nano-architectures. In Proceedings of the Asia and South Pacific Design Automation Conference (ASP-DAC). 317--322."},{"volume-title":"Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'09)","author":"Zheng Y.","key":"e_1_2_1_40_1","unstructured":"Zheng , Y. and Huang , C . 2009. Defect-aware logic mapping for nanowire-based programmable logic arrays via satisfiability . In Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'09) . 1279--1283. Zheng, Y. and Huang, C. 2009. Defect-aware logic mapping for nanowire-based programmable logic arrays via satisfiability. In Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'09). 1279--1283."}],"container-title":["ACM Journal on Emerging Technologies in Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2491680","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2491680","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:39:22Z","timestamp":1750235962000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2491680"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,9]]},"references-count":40,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2013,9]]}},"alternative-id":["10.1145\/2491680"],"URL":"https:\/\/doi.org\/10.1145\/2491680","relation":{},"ISSN":["1550-4832","1550-4840"],"issn-type":[{"type":"print","value":"1550-4832"},{"type":"electronic","value":"1550-4840"}],"subject":[],"published":{"date-parts":[[2013,9]]},"assertion":[{"value":"2011-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-10-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}