On the Use of Bloom Filters for Defect Maps inNanocomputingGang Wang Wenrui Gong Ryan KastnerDepartment of Electrical and Computer EngineeringUniversity of CaliforniaSanta Barbara, CA 93106-9560{wanggang, gong, kastner}@ece.ucsb.eduABSTRACTWhile the exact manufacturing process for nanoscale computingdevices is uncertain, it is abundantly clear that future technologynodes will see an increase in defect rates. Therefore, it is of paramountimportance to construct new architectures and design methodolo-gies that can tolerate large numbers of defects. Defect maps are anecessity in the future design flows, and research on their practicalconstruction is essential. In this work, we study the use of Bloomfilters as a data structure for defect maps. We show that Bloom fil-ters provide the right tradeoff between accuracy and space-efficiency.In particular, they can help simplify the nanosystem design flow byembedding defect information within the nanosystem delivered bythe manufacturers. We develop a novel nanoscale memory designthat uses this concept. It does not rely on a voting strategy, andutilizes the device redundancy more effectiv ely than existing ap-proaches.Categories and Subject DescriptorsJ.6 [Computer -Aided Engineering]: Computer-Aided Design (CAD)General TermsAlgorithms, Design, TheoryKeywordsNanotechnology, Defect tolerant, Bloom filter, Defect map1. INTRODUCTIONIn research laboratories around the world, prototype nanoscaledevices have been constructed using bottom-up chemical assemblyinstead of top-down lithography that has dominated VLSI manu-facturing in the past decades. This progress brings the hope that inthe not too distant future, we will be able to create computing de-vices with unprecedented density (1010devices/cm2) that operatein the THz frequency domain [3].There are fundamental differences between traditional fabrica-tion methods and the proposed nanoscale methods. Nanoscale man-ufacturing techniques cannot replicate the complex structures seenin today’s ASIC designs. Instead, future techniques favor regu-lar, periodic and programable structures. This makes it natural fornanoscale architectures to have a computation structure similar tothose found in current reconfigurable architectures. For instance,Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies arenot made or distributed for profit or commercial adv antage and that copiesbear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.ICCAD’06, November 5-9, 2006, San Jose, California, USA.Copyright 2006 ACM 1-59593-389-1/06/0011 ...$5.00.the crossbar structure is a simple reconfigurable realization that isprevalent in many proposed nanoscale architectures [2, 4, 8, 16].It is predicted that nanoscale devices will have high defect rates.These defects can be roughly divided into two classes: (i) perma-nent defects caused by inherent physics uncertainties in the manu-facturing process, and (ii) transient faults due to lower noise toler-ance or charge injection at reduced v o ltage and current levels. No-body knows the eventual manufacturing failure rate for the nanoscaledevices. It is reported that self-assembly nanometer devices couldhave defect rates as high as 10% [12]. This is much worse com-pared to the one per billion defect rate found in current CMOS tech-nology. In the near future, it is extremely unlikely that we will beable to produce defect-free nanocomputing devices; current man-ufacturing practices will not work since high defect rates and themassive number of devices on a chip will result in a yield close to0%. Therefore, any practical nanoscale computing system must beable to cope with the possibilities of defects.To address this problem, many defect-tolerant design methodsand architectures have been proposed [14]. These methods can beclassified into two categories. In the first approach [6, 11, 12],defect tolerance is built into the system utilizing redundancy, e.g.R-fold Module Redundancy (RMR) [13, 15]. Such approachescan handle both permanent defects and transient faults; however ,they suffer from low reliability. Alternatively, reconfigurable meth-ods [7, 9, 18] provide an attractive way to address defect toler-ance [5]. The basic idea is to use reconfigurable techniques duringpost-manufacturing design to avoid the defects. It is reported thatreconfiguration is the most effectiv e technique, and is able to copewith manufacturing defect rates of the order of 0.01 to 0.1 [13]. Itdoes not, however, effectively handle transient faults.One of the key concepts in the reconfigurable approach is a de-fect map [12] − a data structure that stores the locations of the de-fective dev ices. Effective and efficient defect maps have not beenwell studied, and are often treated as intermediate component in thedesign flow [9, 12, 17]. In this work, we show that Bloom filtersare an ideal data structure for defect maps. We propose a noveldefect-tolerant nanoscale memory architecture by exploiting theBloom filters. This approach is more effective in using device re-dundancy compared to traditional majority voting approaches, andcan be used effectiv ely with the reconfigurable approaches.We confine our discussion on permanent defect tolerance only.Though it is possible to extend our method to handle transient faults,it is outside the scope of this work. To our best knowledge, this isthe first attempt to utilize Bloom filters in defect-tolerant comput-ing for nanoscale de v ices.The paper is organized as follows. In order to better motivateour study, the next section highlights the role of defect maps in thelifecycle of a nanoscale computing system. We discuss the poten-tial impact of the Bloom filter on the nanoscale computing designFabrication, Test and VerificationDesignTest and verificationPermanent DefectsPermanent + Transient DefectsMitigation methods:RMR, CTMR, NAND-demultiplexing,Error-correcting coded bus, ...Mitigation methods:Configure-around based on defect mapsMitigation methods:Self-testing, repairing, reconfiguring?timeManufacturing Stage Development Stage Service StageChip Manufacturer Application Designer End User Final ProductNanoscaleComputing Devices Stage:Stakeholder:Nano Material(silicon, carbon nanotubes and etc.) Figure 1: Nanosystem lifecycle(what mitigation