{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,10]],"date-time":"2025-11-10T13:34:31Z","timestamp":1762781671175,"version":"3.41.0"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2011,8,1]],"date-time":"2011-08-01T00:00:00Z","timestamp":1312156800000},"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":[[2011,8]]},"abstract":"<jats:p>Nanocrossbars (i.e., nanowire crossbars) offer extreme logic densities but come with very high defect rates; stuck-open\/closed, broken nanowires. Achieving reasonable yield and utilization requires logic mapping that is defect-aware even at the crosspoint level. Such logic mapping works with a defect map per each manufactured chip. The problem can be expressed as matching of two bipartite graphs; one for the logic to be implemented and other for the nanocrossbar. This article shows that the problem becomes a Bipartite SubGraph Isomorphism (BSGI) problem within sub-nanocrossbars free of stuck-closed faults. Our heuristic KNS-2DS is an iterative rough canonizer with approximately O(N<jats:sup>2<\/jats:sup>) complexity followed by an O(N<jats:sup>3<\/jats:sup>) matching algorithm. Canonization brings a partial or full order to graph nodes. It is normally used for solving the regular Graph Isomorphism (GI) problem, while we apply it to BSGI. KNS stands for K-Neighbor Sort and is used for initializing our main contribution 2-Dimensional-Sort (2DS). 2DS operates on the adjacency matrix of a bipartite graph. Radix-2 2DS solves the problem in the absence of stuck-closed faults. With the addition of Radix-3 and our novel Radix-2.5 sort, we solve problems that also have stuck-closed faults. We offer very short runtimes (due to canonization) compared to previous work and have success on all benchmarks. KNS-2DS is also novel from the perspective of BSGI problem as it is based on canonization but not on a search tree with backtracking.<\/jats:p>","DOI":"10.1145\/2000502.2000505","type":"journal-article","created":{"date-parts":[[2011,8,16]],"date-time":"2011-08-16T19:11:58Z","timestamp":1313521918000},"page":"1-16","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Defect-Aware Nanocrossbar Logic Mapping through Matrix Canonization Using Two-Dimensional Radix Sort"],"prefix":"10.1145","volume":"7","author":[{"given":"Sezer","family":"G\u00f6ren","sequence":"first","affiliation":[{"name":"Yeditepe University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"H. Fatih","family":"Ugurdag","sequence":"additional","affiliation":[{"name":"Ozyegin University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Okan","family":"Palaz","sequence":"additional","affiliation":[{"name":"Bahcesehir University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2011,8]]},"reference":[{"unstructured":"ACM\/SIGDA benchmarks. 1993. LGSynth Benchmarks. http:\/\/www.cbl.ncsu.edu\/benchmarks\/LGSynth93\/. ACM\/SIGDA benchmarks. 1993. LGSynth Benchmarks. http:\/\/www.cbl.ncsu.edu\/benchmarks\/LGSynth93\/.","key":"e_1_2_1_1_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_2_1","DOI":"10.1145\/800061.808746"},{"doi-asserted-by":"publisher","key":"e_1_2_1_3_1","DOI":"10.1126\/science.1065824"},{"doi-asserted-by":"publisher","key":"e_1_2_1_4_1","DOI":"10.1126\/science.1114757"},{"doi-asserted-by":"crossref","unstructured":"Bhaduri D. 2007. Design and analysis of defect- and fault-tolerant nano-computing systems. Ph.D. dissertation Virginia Polytechnic Institute and State University. Bhaduri D. 2007. Design and analysis of defect- and fault-tolerant nano-computing systems. Ph.D. dissertation Virginia Polytechnic Institute and State University.","key":"e_1_2_1_5_1","DOI":"10.1007\/978-0-387-74747-7_14"},{"doi-asserted-by":"publisher","key":"e_1_2_1_6_1","DOI":"10.1126\/science.285.5426.391"},{"doi-asserted-by":"publisher","key":"e_1_2_1_7_1","DOI":"10.1126\/science.291.5505.851"},{"doi-asserted-by":"publisher","key":"e_1_2_1_8_1","DOI":"10.1109\/TNANO.2003.808508"},{"doi-asserted-by":"publisher","key":"e_1_2_1_9_1","DOI":"10.1145\/1084748.1084750"},{"doi-asserted-by":"publisher","key":"e_1_2_1_10_1","DOI":"10.1145\/968280.968299"},{"volume-title":"Proceedings of the International Conference on Computer-Aided Design. 375--382","author":"Dehon A.","key":"e_1_2_1_11_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_12_1","DOI":"10.1038\/nature05462"},{"doi-asserted-by":"publisher","key":"e_1_2_1_13_1","DOI":"10.1093\/bioinformatics\/18.3.465"},{"doi-asserted-by":"publisher","key":"e_1_2_1_14_1","DOI":"10.1109\/TCAD.2006.884401"},{"doi-asserted-by":"publisher","key":"e_1_2_1_15_1","DOI":"10.1126\/science.280.5370.1716"},{"doi-asserted-by":"publisher","key":"e_1_2_1_16_1","DOI":"10.1126\/science.1066192"},{"doi-asserted-by":"publisher","key":"e_1_2_1_17_1","DOI":"10.1021\/nl052110f"},{"key":"e_1_2_1_18_1","first-page":"1","article-title":"Experimental demonstration of a defect-tolerant nanocrossbar demultiplexer","volume":"19","author":"Li Z.","year":"2008","journal-title":"Nanotechnology"},{"doi-asserted-by":"publisher","key":"e_1_2_1_19_1","DOI":"10.1038\/nmat2028"},{"unstructured":"Naeimi H. 2005. A greedy algorithm for tolerating defective crosspoints in NanoPLA design. M.S. thesis California Institute of Technology. Naeimi H. 2005. A greedy algorithm for tolerating defective crosspoints in NanoPLA design. M.S. thesis California Institute of Technology.","key":"e_1_2_1_20_1"},{"unstructured":"Papadimitriou C. H. 1994. Computational Complexity. Addison-Wesley. Papadimitriou C. H. 1994. Computational Complexity . Addison-Wesley.","key":"e_1_2_1_21_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_22_1","DOI":"10.1109\/MDT.2009.14"},{"doi-asserted-by":"publisher","key":"e_1_2_1_23_1","DOI":"10.1126\/science.289.5476.94"},{"doi-asserted-by":"publisher","key":"e_1_2_1_24_1","DOI":"10.5555\/1129601.1129697"},{"doi-asserted-by":"publisher","key":"e_1_2_1_25_1","DOI":"10.1145\/1167943.1167945"},{"doi-asserted-by":"publisher","key":"e_1_2_1_26_1","DOI":"10.1145\/321921.321925"},{"volume-title":"Proceedings of the International Test Conference.","author":"Wang Z.","key":"e_1_2_1_27_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_28_1","DOI":"10.1021\/nl034268a"},{"volume-title":"Proceedings of the Conference on Design Automation and Test in Europe.","author":"Zheng Y.","key":"e_1_2_1_29_1"},{"volume-title":"Proceedings of the IEEE International Conference on Nanotechnology. 323--327","author":"Ziegler M. M.","key":"e_1_2_1_30_1"}],"container-title":["ACM Journal on Emerging Technologies in Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2000502.2000505","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2000502.2000505","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T11:00:01Z","timestamp":1750244401000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2000502.2000505"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,8]]},"references-count":30,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2011,8]]}},"alternative-id":["10.1145\/2000502.2000505"],"URL":"https:\/\/doi.org\/10.1145\/2000502.2000505","relation":{},"ISSN":["1550-4832","1550-4840"],"issn-type":[{"type":"print","value":"1550-4832"},{"type":"electronic","value":"1550-4840"}],"subject":[],"published":{"date-parts":[[2011,8]]},"assertion":[{"value":"2010-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-08-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}