A Survey of Fault-Tolerance Algorithms for Reconfigurable Nano-Crossbar Arrays <s> DEFECT-AWARE LOGIC MAPPING <s> Recent developments suggest both plausible fabrication techniques and viable architectures for building sublithographic programmable logic arrays using molecular-scale wires and switches. Designs at this scale will see much higher defect rates than in conventional lithography. However, these defects need not be an impediment to programmable logic design as this scale. We introduce a strategy for tolerating defective crosspoints and develop a linear-time, greedy algorithm for mapping PLA logic around crosspoint defects. We note that P-term fanin must be bounded to guarantee low overhead mapping and develop analytical guidelines for bounding fanin. We further quantify analytical and empirical mapping overhead rates. Including fanin bounding, our greedy mapping algorithm maps a large set of benchmark designs with 13% average overhead for random junction defect rates as high as 20%. <s> BIB001 </s> A Survey of Fault-Tolerance Algorithms for Reconfigurable Nano-Crossbar Arrays <s> DEFECT-AWARE LOGIC MAPPING <s> As the end of the semiconductor roadmap for CMOS approaches, architectures based on nanoscale molecular devices are attracting attention. Among several alternatives, silicon nanowires and carbon nanotubes are the two most promising nanotechnologies according to the ITRS. These technologies may enable scaling deep into the nanometer regime. However, they suffer from very defect-prone manufacturing processes. Although the reconfigurability property of the nanoscale devices can be used to tolerate high defect rates, it may not be possible to locate all defects. With very high device densities, testing each component may not be possible because of time or technology restrictions. This points to a scenario in which even though the devices are tested, the tests are not very comprehensive at locating defects, and hence the shipped chips are still defective. Moreover, the devices in the nanometer range will be susceptible to transient faults which can produce arbitrary soft errors. Despite these drawbacks, it is possible to make nanoscale architectures practical and realistic by introducing defect and fault tolerance. In this article, we propose and evaluate a hybrid nanowire-CMOS architecture that addresses all three problems—namely high defect rates, unlocated defects, and transient faults—at the same time. This goal is achieved by using multiple levels of redundancy and majority voters. A key aspect of the architecture is that it contains a judicious balance of both nanoscale and traditional CMOS components. A companion to the architecture is a compiler with heuristics to quickly determine if logic can be mapped onto partially defective nanoscale elements. The heuristics make it possible to introduce defect-awareness in placement and routing. The architecture and compiler are evaluated by applying the complete design flow to several benchmarks. <s> BIB002 </s> A Survey of Fault-Tolerance Algorithms for Reconfigurable Nano-Crossbar Arrays <s> DEFECT-AWARE LOGIC MAPPING <s> Nanocrossbars (i.e., nanowire crossbars) offer extreme logic densities but come with very high defect rates; stuck-open/closed, broken nanowires. Achieving reasonable yield and utilization requires logic mapping that is defect-aware even at the crosspoint level. Such logic mapping works with a defect map per each manufactured chip. The problem can be expressed as matching of two bipartite graphs; one for the logic to be implemented and other for the nanocrossbar. This article shows that the problem becomes a Bipartite SubGraph Isomorphism (BSGI) problem within sub-nanocrossbars free of stuck-closed faults. Our heuristic KNS-2DS is an iterative rough canonizer with approximately O(N2) complexity followed by an O(N3) matching algorithm. Canonization brings a partial or full order to graph nodes. It is normally used for solving the regular Graph Isomorphism (GI) problem, while we apply it to BSGI. KNS stands for K-Neighbor Sort and is used for initializing our main contribution 2-Dimensional-Sort (2DS). 2DS operates on the adjacency matrix of a bipartite graph. Radix-2 2DS solves the problem in the absence of stuck-closed faults. With the addition of Radix-3 and our novel Radix-2.5 sort, we solve problems that also have stuck-closed faults. We offer very short runtimes (due to canonization) compared to previous work and have success on all benchmarks. KNS-2DS is also novel from the perspective of BSGI problem as it is based on canonization but not on a search tree with backtracking. <s> BIB003 </s> A Survey of Fault-Tolerance Algorithms for Reconfigurable Nano-Crossbar Arrays <s> DEFECT-AWARE LOGIC MAPPING <s> Nanoscale crossbar architectures have been proposed as viable alternatives for overcoming the fundamental physical limitations of CMOS technology. However due to the manufacturing processes for Nan fabrication and their smaller feature sizes, defect densities are higher. This paper presents an efficient function mapping method in the presence of high defect rates for nanoscale crossbar arrays. Given a function and a defect map that describes fault patterns in the crossbar architecture, the approach described here tries to find a valid function mapping, if one exists, using a matrix representation. A set of constraints are derived to preserve semantics and then Integer Linear Programming (ILP) is used to solve the equations. Experimental results show the proposed approach provides efficient utilization of nanoscale crossbars in mapping functions in presence of high defect rates. <s> BIB004 </s> A Survey of Fault-Tolerance Algorithms for Reconfigurable Nano-Crossbar Arrays <s> DEFECT-AWARE LOGIC MAPPING <s> Several emerging nano-technologies, including crossbar nano-architectures, have recently been studied as possible replacement or supplement to CMOS technology in the future. However, extreme process variation and high failure rates, mainly due to atomic device sizes, are major challenges for crossbar nano-architectures. This article presents variation- and defect-tolerant logic mapping on crossbar nano-architectures. Since variation/defect-aware mapping is an NP-hard problem, we introduce a set of Integer Linear Programming (ILP) formulations to effectively solve the problem in a reasonable time. The proposed ILP formulations can be used for both diode-based and FET-based crossbars. Experimental results on benchmark circuits show that our approach can reduce the critical-path delay 39p compared to the Simulated Annealing (SA) method. It can also successfully achieve 97p defect-free mapping with 40p defect density. It can tolerate process variations to meet timing constraints in 95p of the cases, compared to only 77p achieved by SA. <s> BIB005 </s> A Survey of Fault-Tolerance Algorithms for Reconfigurable Nano-Crossbar Arrays <s> DEFECT-AWARE LOGIC MAPPING <s> Nanoelectronics are inherently defect prone, and defect-tolerant logic implementation has emerged as a new foundation to form reliable systems. Crossbar-based architectures have been shown to be promising in future nanoelectronic systems, with most of the existing defect tolerance approaches based on logic mapping. Essentially, mapping-based schemes exploit the freedom of choosing which variables/products (in a logic function) to map to which of the vertical/horizontal wires (in a crossbar). In this paper, we expand the realm of defecting tolerant logic implementation by introducing two approaches orthogonal to mapping-based schemes, namely, logic morphing and fine-grained fine-tuned logic hardening. Logic morphing exploits the various equivalent forms of a logic function to tolerate defects, while calculated logic hardening adds redundancies to make the hardened logic function inherently defect tolerable. A new integrated framework is proposed to utilize the two new schemes while not sacrificing existing mapping-based techniques. The algorithms in the framework can efficiently search for a successful logic implementation in the combined solution space. Simulation results show that the proposed integrated framework boost defect tolerance capability significantly with 2-10 yield improvement, while adding no runtime overhead on top of the basic mapping algorithm. <s> BIB006 </s> A Survey of Fault-Tolerance Algorithms for Reconfigurable Nano-Crossbar Arrays <s> DEFECT-AWARE LOGIC MAPPING <s> This paper studies fault tolerance in switching reconfigurable nano-crossbar arrays. Both permanent and transient faults are taken into account by independently assigning stuck-open and stuck-closed fault probabilities into crosspoints. In the presence of permanent faults, a fast and accurate heuristic algorithm is proposed that uses the techniques of index sorting, backtracking, and row matching. The algorithm’s effectiveness is demonstrated on standard benchmark circuits in terms of runtime, success rate, and accuracy. In the presence of transient faults, tolerance analysis is performed by formally and recursively determining tolerable fault positions. In this way, we are able to specify fault tolerance performances of nano-crossbars without relying on randomly generated faults that is relatively costly regarding that the number of fault distributions in a crossbar grows exponentially with the crossbar size. <s> BIB007
Defect-aware approaches employ defects present in a nano-crossbar during the configuration process to map a given logic function. It is indicated that mapping a logic function on a defective nano-crossbar array is an NP-complete problem  ). The problem is directly equivalent to finding a subgraph isomorphism between graph representations of a logic function and a nano-crossbar. However, in formalization of the problem, a variety of different approaches are adopted to fasten the process, especially for high defect rates. As a common practice, maximum bipartite matching and graph-based heuristics are used to lighten the computational load BIB001 BIB002 . A different approach using matrix representations of a given logic function and a defective nano-crossbar is used with row by row matching BIB003 BIB007 . Another method is integer linear programming with transforming defects as constraints BIB004 BIB005 . A comprehensive and chronological list of the main articles and their contributions to the defect tolerant logic mapping problem is shown in Table 5 . Concerning the different types of defects, we see an overwhelming tendency in the literature with only considering stuck-at deactivated types (different names used in the literature are nonprogrammable, stuck-at 0, stuck-open) ( BIB006 , which analyze the occurrence of multiple-type defects. As follows, we separately explain the main approaches in subsections followed by their evaluations.