Application-independent defect tolerance of reconfigurable nanoarchitectures

ABSTRACT

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-independent defect tolerant design flow to minimize customized postfabrication design efforts to be performed per chip. In this flow, higher level design steps are not needed to be aware of the existence and the location of defects in the chip. Only a final mapping step is required to be defect aware. Application independence of this flow minimizes the number of per-chip design steps, making it appropriate for high volume production. We also present two mapping algorithms, recursive and greedy, which make the connection between defect-unaware design steps and the final defect-aware mapping step. Experiments show that the results obtained by the greedy algorithm are very close to the exact solutions. Using these algorithms, we analyze the manufacturing yield of molecular crossbars under different defect distribution models. We report on the size of the minimum crossbar to be fabricated such that a defect-free crossbar of the desirable size can be found with a guaranteed manufacturing yield.

REFERENCES

• 1: Bachtold, A., Harley, P., Nakanishi, T., and Dekker, C. 2001. Logic circuits with carbon nanotube transistors. Science. 294, 1317--1320.
• 2: Michael Butts , Andrée DeHon , Seth Copen Goldstein, Molecular electronics: devices, systems and tools for gigagate, gigabit chips, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.433-440, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774636]
• 3: Chen, Y., Jung, G., Ohlberg, D., Li, X., Stewart, D., Jeppesen, J., Nielsen, K., Stoddart, J., and Williams, R. 2003. Nanoscale molecular-switch crossbar circuits. Nanotechn. 14, 462--468.
• 4: Collier, C., Wong, E., Belohradsky, M., Raymo, F., Stoddart, J., Kuekes, P., Williams, R., and Heath, J. 1999. Electronically configurable molecular-based logic gates. Science 285, 391--394.
• 5: Cui, Y. and Lieber, C. 2001. Functional nanoscale electronics devices assembled using silicon nanowire building blocks. Science 291, 851--853.
• 6: DeHon, A. 2003. Array-based architecture for FET-based, nanoscale electronics. IEEE Trans. Nanotechn. 2, 23--32.
• 7: DeHon, A., Lincoln, P., and Savage, J. 2003. Stochastic assembly of sublithographic nanoscale interfaces. IEEE Trans. Nanotechn. 2, 165--174.
• 8: Andre DeHon , Michael J. Wilson, Nanowire-based sublithographic programmable logic arrays, Proceedings of the 2004 ACM/SIGDA 12th international symposium on Field programmable gate arrays, February 22-24, 2004, Monterey, California, USA [doi>10.1145/968280.968299]
• 9: Doherty, F. C., Lundgren, J. R., and Siewert, D. J. 1999. Bicliquecovers and partitions of bipartite graphs and digraphs and related matrix ranks of 0,1-matrices. Congressus Numerantium 136, 73--96.
• 10: Seth Copen Goldstein , Mihai Budiu, NanoFabrics: spatial computing using molecular electronics, Proceedings of the 28th annual international symposium on Computer architecture, p.178-191, June 30-July 04, 2001, Göteborg, Sweden
• 11: Jing Huang , Mehdi B. Tahoori , Fabrizio Lombardi, On the Defect Tolerance of Nano-Scale Two-Dimensional Crossbars, Proceedings of the Defect and Fault Tolerance in VLSI Systems, 19th IEEE International Symposium on (DFT'04), p.96-104, October 10-13, 2004
• 12: Huang, Y., Duan, X., Cui, Y., Lauhon, L., Kim, K., and Lieber, C. 2001. Logic gates and computation from assembled nanowire building blocks. Science 294, 1313--1317.
• 13: F. J. Meyer , D. K. Pradhan, Modeling Defect Spatial Distribution, IEEE Transactions on Computers, v.38 n.4, p.538-546, April 1989 [doi>10.1109/12.21146]
• 14: Naeimi, H. and DeHon, A. 2004. A greedy algorithm for tolerating defective crosspoints in NanoPLA design. In Proceedings of the International Conference on Field-Programmable Technology. 49--56.
• 15: Nantero. 2005. www.nantero.com.
• 16: Rueckes, T., Kim, K., Joselevich, E., Tseng, G., Cheung, C., and Lieber, C. 2000. Carbon nanotube-based nonvolatile random access memory for molecular computing. Science 289, 94--97.
• 17: M. B. Tahoori, A mapping algorithm for defect-tolerance of reconfigurable nano-architectures, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.668-672, November 06-10, 2005, San Jose, CA
• 18: Mehdi B. Tahoori, Defects, Yield, and Design in Sublithographic Nano-electronics, Proceedings of the 20th IEEE International Symposium on Defect and Fault Tolerance in VLSI Systems (DFT'05), p.3-11, October 03-05, 2005 [doi>10.1109/DFTVS.2005.28]
• 19: Ziegler, M. and Stan, M. 2002. Design and analysis of crossbar circuits for molecular nanoelectronics. In Proceedings of the IEEE International Conference on Nanotechnology. 323--327.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.8 Performance and Reliability
      B.8.1 Reliability, Testing, and Fault-Tolerance

General Terms:
Design, Reliability

Keywords:
Defect tolerance, nanotechnology, reconfigurable architectures