On the use of Bloom filters for defect maps in nanocomputing

ABSTRACT

While the exact manufacturing process for nanoscale computing devices is uncertain, it is abundantly clear that future technology nodes will see an increase in defect rates. Therefore, it is of paramount importance to construct new architectures and design methodologies that can tolerate large numbers of defects. Defect maps are a necessity in the future design flows, and research on their practical construction is essential. In this work, we study the use of Bloom filters as a data structure for defect maps. We show that Bloom filters provide the right tradeoff between accuracy and space-efficiency. In particular, they can help simplify the nanosystem design flow by embedding defect information within the nanosystem delivered by the manufacturers. We develop a novel nanoscale memory design that uses this concept. It does not rely on a voting strategy, and utilizes the device redundancy more effectively than existing approaches.

REFERENCES

• 1: Burton H. Bloom, Space/time trade-offs in hash coding with allowable errors, Communications of the ACM, v.13 n.7, p.422-426, July 1970 [doi>10.1145/362686.362692]
• 2: Y. Chen, G.-Y. Jung, D. A. A. Ohlberg, X. Li, D. R. Stewart, J. O. Jeppesen, K. A. Nielsen, J. F. Stoddart, and R. S. Williams. Nanoscale molecular-switch crossbar circuits. Nanotechnology, 14:462--468, 2003.
• 3: R. Compano, L. Molenkamp, and D. J. P. (eds). Technology roadmap for nanoelectronics. European Commission IST Programme - Future and Emerging Technologies, 2000.
• 4: A. DeHon , K. K. Likharev, Hybrid CMOS/nanoelectronic digital circuits: devices, architectures, and design automation, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.375-382, November 06-10, 2005, San Jose, CA
• 5: S. C. Goldstein, The impact of the nanoscale on computing systems, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.655-661, November 06-10, 2005, San Jose, CA
• 6: J. Han and P. Jonker. A defect- and fault-tolerant architecture for nanocomputers. Nanotechnology, 14:224--230, 2003.
• 7: Chen He , M. F. Jacome , G. de Veciana, Scalable defect mapping and configuration of memory-based nanofabrics, Proceedings of the High-Level Design Validation and Test Workshop, 2005. on Tenth IEEE International, p.11-18, November 30-December 02, 2005 [doi>10.1109/HLDVT.2005.1568807]
• 8: T. Hogg and G. Snider. Defect-tolerant logic with nanoscale crossbar circuits. Technical report, HP Labs, 2004.
• 9: Margarida Jacome , Chen He , Gustavo de Veciana , Stephen Bijansky, Defect tolerant probabilistic design paradigm for nanotechnologies, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996730]
• 10: A. Kirsch and M. Mitzenmacher. Building a better bloom filter. Technical Report TR-02-05, Division of Engineering and Applied Sciences, Harvard University, 2005.
• 11: P. J. Kuekes, W. Robinett, G. Seroussi, and R. S. Williams. Defect-tolerant interconnect to nanoelectronic circuits: internally redundant demultiplexers based on error-correcting codes. Nanotechnology, 16:869--882, 2005.
• 12: M. Mishra and S. C. Goldstein. Defect tolerance at the end of the roadmap. In ITC, pages 1201--1211, 2003.
• 13: K. Nikolic, A. Sadek, and M. Forshaw. Fault-tolerant techniques for nanocomputers. Nanotechnology, 13:357--362, 2002.
• 14: Gethin Norman , David Parker , Marta Kwiatkowska , Sandeep K. Shukla, Evaluating the Reliability of Defect-Tolerant Architectures for Nanotechnology with Probabilistic Model Checking, Proceedings of the 17th International Conference on VLSI Design, p.907, January 05-09, 2004
• 15: Daniel P. Siewiorek , Robert S. Swarz, Reliable computer systems (2nd ed.): design and evaluation, Digital Press, Newton, MA, 1992
• 16: G. Snider, P. Kuekes, and R. S. Williams. CMOS-like logic in defective, nanoscale crossbars. Nanotechnology, 15:881--891, 2004.
• 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]

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING

General Terms:
Algorithms, Design, Theory

Keywords:
Bloom filter, defect map, defect tolerant, nanotechnology