A Survey of Fault-Tolerance Algorithms for Reconfigurable Nano-Crossbar Arrays <s> Permanent Fault Tolerance. <s> The Teramac configurable hardware system can execute synchronous logic designs of up to one million gates at rates up to 1 megahertz. A fully configured Teramac includes half a gigabyte of RAM and hardware support for large multiported register files. The system has been built from custom FPGA's packaged in large multichip modules (MCMs). A large custom circuit (/spl sim/1,000,000 gates) may be compiled onto the hardware in approximately 2 hours, without user intervention. The system is being used to explore the potential of custom computing machinery (CCM). <s> BIB001 </s> A Survey of Fault-Tolerance Algorithms for Reconfigurable Nano-Crossbar Arrays <s> Permanent Fault Tolerance. <s> Teramac is a massively parallel experimental computer built at Hewlett-Packard Laboratories to investigate a wide range of different computational architectures. This machine contains about 220,000 hardware defects, any one of which could prove fatal to a conventional computer, and yet it operated 100 times faster than a high-end single-processor workstation for some of its configurations. The defect-tolerant architecture of Teramac, which incorporates a high communication bandwith that enables it to easily route around defects, has significant implications for any future nanometer-scale computational paradigm. It may be feasible to chemically synthesize individual electronic components with less than a 100 percent yield, assemble them into systems with appreciable uncertainty in their connectivity, and still create a powerful and reliable data communications network. Future nanoscale computers may consist of extremely large-configuration memories that are programmed for specific tasks by a tutor that locates and tags the defects in the system. <s> BIB002 </s> A Survey of Fault-Tolerance Algorithms for Reconfigurable Nano-Crossbar Arrays <s> Permanent Fault Tolerance. <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> BIB003 </s> A Survey of Fault-Tolerance Algorithms for Reconfigurable Nano-Crossbar Arrays <s> Permanent Fault Tolerance. <s> Lithography-based integrated circuit fabrication is rapidly approaching its limit in terms of feature size. The current alternative is nanotechnology-based fabrication, which relies on self-assembly of nanotubes or nanowires. Such a process is subject to a high defect rate, which can be tolerated using carefully crafted defect tolerance techniques. This paper presents an algorithm for reconfiguration-based defect tolerance in nanotechnology switches. The algorithm offers an average switch density improvement of 50% to 100% to most recently published techniques. The algorithm is also consistent in improving the yield through minimizing false rejects as the results show over a large sample. The improvement percentage varies depending on the manufactured switch size and the desired defect-free size with the improvement in efficiency directly proportional to the size of the switch. <s> BIB004 </s> A Survey of Fault-Tolerance Algorithms for Reconfigurable Nano-Crossbar Arrays <s> Permanent Fault Tolerance. <s> With the recent development of nanoscale materials and assembly techniques, it is envisioned to build high-density reconfigurable systems which have never been achieved by the photolithography. Various reconfigurable architectures have been proposed based on nanowire crossbar structure as the primitive building block. Unfortunately, high-density systems consisting of nanometer-scale elements are likely to have many imperfections and variations; thus, defect tolerance is considered as one of the most exigent challenges. In this paper, we evaluate three different logic mapping algorithms with defect tolerance to circumvent clustered defective crosspoints in nanowire reconfigurable crossbar architectures. The effectiveness of inherited redundancy and configurability utilization is demonstrated through extensive parametric simulations. Then, costs associated with the repair process are analyzed and a method to find the most cost-effective repair solution is presented. <s> BIB005 </s> A Survey of Fault-Tolerance Algorithms for Reconfigurable Nano-Crossbar Arrays <s> Permanent Fault Tolerance. <s> Programmable logic arrays (PLAs) using self-assembly nanowire crossbars have shown promising potential for future nano-scale circuit design. However, due to the density and size factors of nanowires and molecular switches, the fabrication fault densities are much higher than those of the conventional silicon technology, and hence pose greater design challenges. In this paper, we propose a novel defect-aware logic mapping framework via Boolean satisfiability (SAT). Compared with the prior works, our technique considers PLA defects on both input and output planes at the same time. This synergistic approach can help solve logic mapping problems with higher defect rates. The proposed method is universally suitable for various nano-scale PLAs, including AND/OR, NOR/NOR structures, etc. The experimental results have shown that it can efficiently solve large mapping problems at a total defect rate of 20% or even higher. We further investigate the impact of different defects on PLA mapping, which helps set up an initial contribution for yield estimation and utilization of partially-defective PLAs. <s> BIB006 </s> A Survey of Fault-Tolerance Algorithms for Reconfigurable Nano-Crossbar Arrays <s> Permanent Fault Tolerance. <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> BIB007 </s> A Survey of Fault-Tolerance Algorithms for Reconfigurable Nano-Crossbar Arrays <s> Permanent Fault Tolerance. <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> BIB008 </s> A Survey of Fault-Tolerance Algorithms for Reconfigurable Nano-Crossbar Arrays <s> Permanent Fault Tolerance. <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> BIB009 </s> A Survey of Fault-Tolerance Algorithms for Reconfigurable Nano-Crossbar Arrays <s> Permanent Fault Tolerance. <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> BIB010
In the presence of permanent faults called as defects, tolerance is achieved by mapping Boolean logic functions on a defective crossbar using crossbar row and column permutations. This is an NP-complete problem  ). For the worst-case scenario, implementing a given function with an N × M crossbar requires N !M! permutations; computing time quickly grows to intractable levels with the crossbar size. Additionally, high fault rates complicate the mapping process by constraining the possible valid choices. Nevertheless, seminal Teramac experiment in BIB001 shows that it is possible to produce reliable computing with using components having excessive faulty parts. As specified in BIB002 , as long as adequate connectivity and efficient algorithms for configuring present, it is feasible to use a reconfigurable nano-crossbar to obtain reliable computing structures. In the literature, proposed defect-tolerant logic mapping algorithms of nano-crossbars can be categorized under two main methodologies: defect-unaware and defect-aware. However, it should be noted that both methods use a defect map that shows the location of faults in nano-crossbar, so a more intuitive naming would be "defect-avoiding" and "defect-employing." Nevertheless, we follow the prevalent terminology present widely in the literature. Defect-unaware methods determine the size of an n × n nano-crossbar to obtain a k × k defect-free sub-crossbar, so it is possible to know the required size of a crossbar in advance to implement a given logic function. Using the defect-free sub-crossbar, a straightforward mapping process can be applied. However, the number of studies in this field is limited due to the inefficient area yield. There is a common shortcoming especially for high fault rates-obtained k values are much smaller than n. When N = 250 and the fault rate is 15% that is a reasonable value for nano arrays, the proposed algorithms find k values as high as 30 . It means that only 1% of the crossbar can be used. Proposed algorithms use graph-based models and heuristics to solve the maximum independent set problem in a complement graph  BIB004 Li 2011, 2014) . Defect-aware logic mapping methods employ defective elements in the mapping process that results in much better area yields. However, the mapping process is more complicated. The number of studies in this field is abundant due to flexible nature of formalizing the problem. Earlier works utilize graph-based models including BIB003 solving the bipartite matching problem with a greedy approach and solving the graph embedding problem with a recursive approach. Additionally, BIB005 examine the effect of clustered defects with a matrix-based algorithm, and BIB006 uses satisfiability approach for the mapping process. Another greedy algorithm is proposed in BIB007 using partial graph constructing. Apart from the graph-based models, an ILP model is used in BIB008 and BIB010 by introducing constraints related to nano-crossbar defects. Furthermore, a novel approach benefiting from graph canonization with sorting is used in BIB009 . To handle scalability more efficiently compared to the above methods, BIB003 uses a greedy approach; uses a graph-based approach with memetic fitness approximation; and Tunali and Altun (2017) implements matrix sorting supported by greedy backtracking.