Bo Yuan
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(n3), the time complexity of the proposed heuristic algorithm is proved to be O(n2). 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.
- A. Al-Yamani, S. Ramsundar, and D. K. Pradham. 2007. A defect tolerance scheme for nanotechnology circuits. IEEE Trans. Circ. Syst. I. Regular Papers. 54, 11, 2402--2409.Google Scholar
Cross Ref
- G. Bourianoff, J. E. Brewer, R. Cavin, J. A. Hutchby, and V. Zhirnov. 2008. Boolean logic and alternative information-processing devices. Computer 41, 5, 38--46. Google ScholarDigital Library
- R. Cavin, J. A. Hutchby, V. Zhirnov, J. E. Brewer, and G. Bourianoff. 2008. Emerging research architectures. Computer 41, 5, 33--37. Google ScholarDigital Library
- Y. Chen, G.-Y. Jung, D. A. A. Ohlberg, X. M. Li, D. R. Stewart, J. O. Jeppesen, K. A. Nielsen, J. F. Stoddart, and R. S. Williams. 2003a. Nanoscale molecular-switch crossbar circuits. Nanotechnology 14, 4, 462--468.Google ScholarCross Ref
- Y. Chen, D. A. A. Ohlberg, X. M. Li, D. R. Stewart, R. S. Williams, J. O. Jeppesen, K. A. Nielsen, J. F. Stoddart, D. L. Olynick, and E. Erson. 2003b. Nanoscale molecular-switch devices fabricated by imprint lithography. Appl. Phys. Lett. 82, 1610--1612.Google ScholarCross Ref
- Y. Cheng and G. M. Church. 2000. Biclustering of expression data. In Proceedings of the International Conference on Intelligent Systems for Molecular Biology. 93--103. Google ScholarDigital Library
- S. Chilstedt, C. Dong, and D. Chen. 2009. Design and evaluation of a carbon nanotube-based programmable architecture. Int. J. Parallel Program. 37, 4, 389--416. Google ScholarDigital Library
- M. Crocker, X. S. Hu, and M. Niemier. 2009. Defects and faults in QCA-based PLAs. ACM J. Emerg. Technol. Comput. Syst. 5, 2, Article 8. Google ScholarDigital Library
- J. Dai, L. Wang, and F. Jain. 2009. Analysis of defect tolerance in molecular crossbar electronics. IEEE Trans. VLSI Syst. 17, 4, 529--540. Google ScholarDigital Library
- M. Dawande, P. Keskinocak, J. M. Swaminathan, and S. Tayur. 2001. On bipartite and multipartite clique problems. J. Algor. 41, 2, 388--403. Google ScholarDigital Library
- A. Dehon. 2005. Nanowire-based programmable architectures. ACM J. Emerg. Technol. Comput. Syst. 1, 2, 109--162. Google ScholarDigital Library
- A. Dehon and H. Naeimi. 2005. Seven strategies for tolerating highly defective fabrication. IEEE Des. Test Comput. 22, 4, 306--315. Google ScholarDigital Library
- M. R. Garey and D. S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, San Francisco, CA. Google ScholarDigital Library
- G. F. Gerofolini. 2007a. Realistic limits to computation I. Physical limits. Appl. Phys. A 86, 1, 23--29.Google ScholarCross Ref
- G. F. Gerofolini. 2007b. Realistic limits to computation II. The technological side. Appl. Phys. A. Sci. Process. 86, 1, 31--42.Google ScholarCross Ref
- B. Ghavami, A. Tajary, M. Raji, and H. Pedram. 2010. Defect and variation issues on design mapping of reconfigurable nanoscale crossbars. In Proceedings of the IEEE Computer Society Annual Symposium on VLSI. 173--178. Google ScholarDigital Library
- S. C. Goldstein and M. Budiu. 2001. Nanofabrics: Spatial computing using molecular electronics. In Proceedings of the Annual International Symposium on Computer Architecture. 178--189. Google ScholarDigital Library
- S. Goren, H. F. Ugurdag, and O. Palaz. 2011. Defect-aware nanocrossbar logic mapping through matrix canonization using two-dimensional radix sort. ACM J. Emerg. Technol. Comput. Syst. 7, 3, Article 12. Google ScholarDigital Library
- M. Haselman and S. Hauck. 2010. The future of integrated circuits: A survey of nanoelectronics. Proc. IEEE 98, 1, 11--38.Google ScholarCross Ref
- T. Hogg and G. Snider. 2006. Defect-tolerant adder circuits with nanoscale crossbars. IEEE Trans. Nanotechnol. 5, 2, 97--100. Google ScholarDigital Library
- T. Hogg and G. Snider. 2007. Defect-tolerant logic with nanoscale crossbar circuits. J. Electr. Test. 23, 2--3, 117--129. Google ScholarDigital Library
- W. Lu and C. M. Lieber. 2007. Nanoelectronics from the bottom up. Nat. Mater. 6, 841--850.Google ScholarCross Ref
- W. Rao, A. Orailoglu, and R. Karri. 2009. Logic mapping in crossbar-based nanoarchitectures. IEEE Des. Test Comput. 26, 1, 68--76. Google ScholarDigital Library
- S. S. Ravi and E. L. Lloyd. 1988. The complexity of near-optimal programmable logic array folding. SIAM J. Comput. 17, 4, 696--710. Google ScholarDigital Library
- T. Rueckes, K. Kim, E. Joselevich, G. Y. Tseng, C.-L. Cheung, and C. M. Lieber. 2000. Carbon nanotube-based nonvolatile random access memory for molecular computing. Science 289, 5476, 94--97.Google Scholar
- G. Snider, P. Kuekes, T. Hogg, and R. S. Williams. 2005. Nanoelectronic architectures. Appl. Phys. A Mater. Sci. Process. 80, 6, 1183--1195.Google ScholarCross Ref
- D. B. Strukov and K. K. Likharev. 2005. CMOL FPGA: A reconfigurable architecture for hybrid digital circuits with two-terminal nanodevices. Nanotechnology 16, 6, 888--900.Google ScholarCross Ref
- M. B. Tahoori. 2006. Application-independent defect tolerance of reconfigurable nanoarchitectures. ACM J. Emerg. Technol. Comput. Syst. 2, 3, 197--218. Google ScholarDigital Library
- M. B. Tahoori. 2009. Low-overhead defect tolerance in crossbar Nanoarchitectures. ACM J. Emerg. Technol. Comput. Syst. 5, 2, Article 11. Google ScholarDigital Library
- C. Tunc and M. B. Tahoori. 2010. Variation tolerant logic mapping for crossbar array nano architectures. In Proceedings of the 15th Asia and South Pacific Design Automation Conference. 855--860. Google ScholarDigital Library
- H. Yan, H. S. Choe, S. W. Nam, Y. Hu, S. Das, J. F. Klemic, J. C. Ellenbogen, and C. M. Lieber. 2011. Programmable nanowire circuits for nanoprocessor. Nature 470, 7333, 240--244.Google Scholar
- M. Yannakakis. 1981. Node-deletion problems on bipartite graphs. SIAM J. Comput. 10, 2, 310--327.Google ScholarDigital Library
- Y. Yellambalase and M. Choi. 2008. Cost-driven repair optimization of reconfigurable nanowire crossbar systems with clustered defects. J. Syst. Archit. 54, 8, 729--741. Google ScholarDigital Library
- B. Yuan and B. Li. 2011. A low time complexity defect-tolerance algorithm for nanoelectronic crossbar. In Proceedings of the International Conference on Information Science and Technology. 143--148.Google Scholar
Index Terms
- A Fast Extraction Algorithm for Defect-Free Subcrossbar in Nanoelectronic Crossbar
Recommendations
Application-independent defect tolerance of reconfigurable nanoarchitectures
Self-assembled nanofabrication processes yield regular and reconfigurable devices. However, defect densities in this emerging nanotechnology are higher than those in conventional lithography-based VLSI. In this article, we present an application-...
Low-overhead defect tolerance in crossbar nanoarchitectures
It is anticipated that the number of defects in nanoscale devices fabricated using bottom-up self-assembly process is significantly higher than that for CMOS devices fabricated by conventional top-down lithography patterning. This is mainly because of ...
A low-power reconfigurable logic array based on double-gate transistors
fine-grained reconfigurable architecture based on double gate technology is proposed and analyzed. The logic function operating on the first gate of a double-gate (DG) transistor is reconfigured by altering the charge on its second gate. Each cell in ...
Comments