A Survey of Fault-Tolerance Algorithms for Reconfigurable Nano-Crossbar Arrays <s> LOGIC MAPPING PROBLEM <s> Chemists can now construct wires which are just a few atoms in diameter; these wires can be selectively field-effect gated, and wire crossings can act as diodes with programmable resistance. These new capabilities present both opportunities and challenges for constructing nanoscale computing systems. The tiny feature sizes offer a path to economically scale down to atomic dimensions. However, the associated bottom-up synthesis techniques only produce highly regular structures and come with high defect rates and minimal control during assembly. To exploit these technologies, we develop nanowire-based architectures which can bridge between lithographic and atomic-scale feature sizes and tolerate defective and stochastic assembly of regular arrays to deliver high density universal computing devices. Using 10nm pitch nanowires, these nanowire-based programmable architectures offer one to two orders of magnitude greater mapped-logic density than defect-free lithographic FPGAs at 22nm. <s> BIB001 </s> A Survey of Fault-Tolerance Algorithms for Reconfigurable Nano-Crossbar Arrays <s> LOGIC MAPPING PROBLEM <s> This paper describes a digital logic architecture for ‘CMOL’ hybrid circuits which combine a semiconductor–transistor (CMOS) stack and two levels of parallel nanowires, with molecular-scale nanodevices formed between the nanowires at every crosspoint. This cell-based, field-programmable gate array (FPGA)-like architecture is based on a uniform, reconfigurable CMOL fabric, with four-transistor CMOS cells and two-terminal nanodevices (‘latching switches’). The switches play two roles: they provide diode-like I –V curves for logic circuit operation, and allow circuit mapping on CMOL fabric and its reconfiguration around defective nanodevices. Monte Carlo simulations of two simple circuits (a 32-bit integer adder and a 64-bit full crossbar switch) have shown that the reconfiguration allows one to increase the circuit yield above 99% at the fraction of bad nanodevices above 20%. Estimates have shown that at the same time the circuits may have extremely high density (approximately 500 times higher than that of the usual CMOS FPGAs with the same design rules), while operating at higher speed at acceptable power consumption. (Some figures in this article are in colour only in the electronic version) <s> BIB002 </s> A Survey of Fault-Tolerance Algorithms for Reconfigurable Nano-Crossbar Arrays <s> LOGIC MAPPING PROBLEM <s> We have calculated the maximum useful bit density that may be achieved by the synergy of bad bit exclusion and advanced (BCH) error correcting codes in prospective crossbar nanoelectronic memories, as a function of defective memory cell fraction. While our calculations are based on a particular ("CMOL") memory topology, with naturally segmented nanowires and an area-distributed nano/CMOS interface, for realistic parameters our results are also applicable to "global" crossbar memories with peripheral interfaces. The results indicate that the crossbar memories with a nano/CMOS pitch ratio close to 1/3 (which is typical for the current, initial stage of the nanoelectronics development) may overcome purely semiconductor memories in useful bit density if the fraction of nanodevice defects (stuck-on-faults) is below approximately 15%, even under rather tough, 30 ns upper bound on the total access time. Moreover, as the technology matures, and the pitch ratio approaches an order of magnitude, the crossbar memories may be far superior to the densest semiconductor memories by providing, e.g., a 1 Tbit/cm2 density even for a plausible defect fraction of 2%. These highly encouraging results are much better than those reported in literature earlier, including our own early work, mostly due to more advanced error correcting codes. <s> BIB003
Nano-crossbar-based architectures are generally composed of specific crossbars/planes, each of which implement a two-level logic such as AND-OR as illustrated in BIB001 , BIB002 , BIB003 , , and . Therefore realization of a target logic function whether two-level or multi-level is closely related to the architecture. However, if we focus on a single plane and use an abstraction (independent of plane character), logic mapping process (whether two-level or multi-level) gradually can be applied to every connecting/succeeding planes to accomplish the desired result. This is a common practice in the literature with using AND planes for benchmark simulations. The reason of using AND planes is that they are generally much larger than OR planes; using a reconfigurability feature, a single line/wire as an OR plane is even sufficient to have every output at a time. Note that with defect-free OR planes, one can make connections between planes without any constraint for the orderings of input and output lines. For this purpose defect-unaware logic mapping techniques can be preferred. Logic mapping and connectivity checks of planes are previously illustrated in Figure 2 with an integrated high-level view. Logic mapping is the configuration of crosspoint switches of a nano-crossbar to implement a given Boolean logic function given in sum-of-products form such as f = P 1 +, . . . , +P k . The main goal is finding a valid mapping, namely a correct assignment of literals and products of the function to inputs and outputs of a given crossbar. Input and output assignments can be represented with an input array I = [I 1 , . . . , In case of having a fault-free crossbar, every assignment produces a valid mapping, so the configuration process is simple and straightforward. Defect-unaware approaches benefit from this feature by finding a defect-free sub-crossbar, so physical design is not troubled with the locations of defects. Figure 5 (a) shows an example. In case of having faults, it is not guaranteed that an assignment produces a valid mapping. Figure 5 (b) shows an example. Configuration with the same input and output arrays as used for a fault-free crossbar, produces a different logic function, since certain switches cannot be activated or deactivated. However, with using a defect-aware method one can implement the given function with a valid assignment. Figure 5 (c) shows an example. In the following two sections, we consider defect-unaware and defect-aware algorithms targeting permanent faults or defects. In short, defect-unaware approaches aim to find a defect-free sub-crossbar, so the follow-up assignment procedure is straightforward and trouble free. Defectaware approaches aim to find valid input and output assignments using the full-size crossbar by considering every defect in a crossbar.