### A Fast Extraction Algorithm for Defect-Free Subcrossbar in Nanoelectronic CrossbarA Fast Extraction Algorithm for Defect-Free Subcrossbar in Nanoelectronic Crossbar

Access Restriction
Subscribed

 Author Yuan, Bo ♦ Li, Bin Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2014 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Balanced biclique ♦ Defect tolerant ♦ Nanotechnology ♦ Reconfigurable architectures Abstract Due to the super scale, high defect density, and per-chip designing paradigm of emerging nanoelectronics, the runtime of the algorithms for defect-tolerant design is of vital importance from the perspective of practicability. In this article, an efficient and effective heuristic defect-free subcrossbar extraction algorithm is proposed which improves performance by mixing the heuristics from two state-of-the-art algorithms and then is speeded up significantly by considerably reducing the number of major loops. Compared with the current most effective algorithm that improves the solution quality (i.e., size of the defect-free subcrossbar obtained) at the cost of high time complexity $O(n^{3}),$ the time complexity of the proposed heuristic algorithm is proved to be $O(n^{2}).$ Using a large set of instances of various scales and defect densities, the simulation results show that the proposed algorithm can offer similar high-quality solutions as the current most effective algorithm while consuming much shorter runtimes (reduced to about 1/3 to 1/5) than the current most effective algorithm. ISSN 15504832 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2014-05-06 Publisher Place New York e-ISSN 15504840 Journal ACM Journal on Emerging Technologies in Computing Systems (JETC) Volume Number 10 Issue Number 3 Page Count 19 Starting Page 1 Ending Page 19

#### Open content in new tab

Source: ACM Digital Library