Thumbnail
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

   Open content in new tab
Source: ACM Digital Library