skip to main content
10.1145/1233501.1233654acmconferencesArticle/Chapter ViewAbstractPublication PagesiccadConference Proceedingsconference-collections
Article

On the use of Bloom filters for defect maps in nanocomputing

Published: 05 November 2006 Publication History

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]
B. H. Bloom. Space/time trade-offs in hash coding with allowable errors. Commun. ACM, 13(7):422--426, 1970.
[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 and K. K. Likharev. Hybrid CMOS/Nanoelectronic digital circuits: Devices, architectures, and design automation. In ICCAD'05, pages 375--382, November 2005.
[5]
S. C. Goldstein. The impact of the nanoscale on computing systems. In ICCAD'05, pages 655--661, November 2005.
[6]
J. Han and P. Jonker. A defect- and fault-tolerant architecture for nanocomputers. Nanotechnology, 14:224--230, 2003.
[7]
C. He, M. F. Jacome, and G. de Veciana. Scalable defect mapping and configuration of memory-based nanofabrics. In IEEE HLDVT Workshop, 2005.
[8]
T. Hogg and G. Snider. Defect-tolerant logic with nanoscale crossbar circuits. Technical report, HP Labs, 2004.
[9]
M. Jacome, C. He, G. de Veciana, and S. Bijansky. Defect tolerant probabilistic design paradigm for nanotechnologies. In DAC '04, pages 596--601, New York, NY, USA, 2004. ACM Press.
[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]
G. Norman, D. Parker, M. Z. Kwiatkowska, and S. K. Shukla. Evaluating the reliability of defect-tolerant architectures for nanotechnology with probabilistic model checking. In VLSI Design, pages 907--912, 2004.
[15]
D. Siewiorek and R. Swarz. Reliable Computer Systems Design and Evaluation. Digital Press, Bedford, 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. Tahoori. A mapping algorithm for defect tolerance of reconfigurable nano-architectures. In ICCAD'05, pages 668--672, 2005.
[18]
M. B. Tahoori. Defects, yield, and design in sublithographic nano-electronics. In 20th IEEE International Symposium on Defect and Fault Tolerance in VLSI Systems., pages 3--11, 2005.

Cited By

View all
  • (2023)Double locality sensitive hashing Bloom filter for high-dimensional streaming anomaly detectionInformation Processing and Management: an International Journal10.1016/j.ipm.2023.10330660:3Online publication date: 1-May-2023
  • (2017)A Survey of Fault-Tolerance Algorithms for Reconfigurable Nano-Crossbar ArraysACM Computing Surveys10.1145/312564150:6(1-35)Online publication date: 14-Nov-2017

Index Terms

  1. On the use of Bloom filters for defect maps in nanocomputing

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    ICCAD '06: Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design
    November 2006
    147 pages
    ISBN:1595933891
    DOI:10.1145/1233501
    Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

    Sponsors

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 05 November 2006

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. Bloom filter
    2. defect map
    3. defect tolerant
    4. nanotechnology

    Qualifiers

    • Article

    Conference

    ICCAD06
    Sponsor:

    Acceptance Rates

    Overall Acceptance Rate 457 of 1,762 submissions, 26%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)0
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 27 Jan 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2023)Double locality sensitive hashing Bloom filter for high-dimensional streaming anomaly detectionInformation Processing and Management: an International Journal10.1016/j.ipm.2023.10330660:3Online publication date: 1-May-2023
    • (2017)A Survey of Fault-Tolerance Algorithms for Reconfigurable Nano-Crossbar ArraysACM Computing Surveys10.1145/312564150:6(1-35)Online publication date: 14-Nov-2017

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media