A Survey of Fault-Tolerance Algorithms for Reconfigurable Nano-Crossbar Arrays <s> Fault Tolerance in Programmable Logic Arrays <s> After a discussion of the reasons for choosing to implement logic in array form. a detailed description of the nature of array logic is given. Topics specifically discussed include general array structures and implementation, influence of decoder partitioning, design of logic arrays, output phase, "split" variables, feedback in logic arrays, and reconfiguration. <s> BIB001 </s> A Survey of Fault-Tolerance Algorithms for Reconfigurable Nano-Crossbar Arrays <s> Fault Tolerance in Programmable Logic Arrays <s> A new fault model is proposed for the purpose of testing programmable logic arrays. It is shown that a test set for all detectable modeled faults detects a wide variety of other faults. A test generation method for single faults is then outlined. Included is a bound on the size of test sets which indicates that test sets are much smaller than would be required by exhaustive testing. Finally, it is shown that many interesting classes of multiple faults are also detected by the test sets. <s> BIB002 </s> A Survey of Fault-Tolerance Algorithms for Reconfigurable Nano-Crossbar Arrays <s> Fault Tolerance in Programmable Logic Arrays <s> The design is presented, in which a conventional PLA is modified by adding redundancy circuits. Three types of fault can be repaired: crosspoint, bridging, and stuck-at faults. <s> BIB003 </s> A Survey of Fault-Tolerance Algorithms for Reconfigurable Nano-Crossbar Arrays <s> Fault Tolerance in Programmable Logic Arrays <s> Redundancy techniques have been applied to conventional programmable logic arrays (PLAs) to allow for the repair of defective chips. When the redundancy technique is implemented in a VLSI or WSI chip design, the increased cost is proportional to the increased chip silicon area, and the additional spare lines can increase the silicon area and propagation delay. However, if the provided redundancy can be efficiently utilized to repair defective chip; then the additional spare lines may increase rather than decrease the chip yields. The possibility of yield enhancement through redundant design is analyzed, showing that the chip yield is increased significantly. > <s> BIB004 </s> A Survey of Fault-Tolerance Algorithms for Reconfigurable Nano-Crossbar Arrays <s> Fault Tolerance in Programmable Logic Arrays <s> A fault model for programmable logic arrays (PLAs) is discussed that handles four classes of faults: multiple stuck-at faults, multiple bridging faults, multiple crosspoint faults, and faults due to breaks in lines. It is shown that a test that detects all multiple crosspoint faults also detects all multiple stuck-at faults, multiple bridging faults, and any combination of the above. It is also shown that multiple faults form a substantial part of the set of all faults in PLAs. Experiments with test generators show that tests detecting all single testable crosspoint faults also detect all testable stuck-at faults. The experiments also show that the test strategies based on the single-crosspoint fault model cover the greater part of all faults in PLAs. > <s> BIB005 </s> A Survey of Fault-Tolerance Algorithms for Reconfigurable Nano-Crossbar Arrays <s> Fault Tolerance in Programmable Logic Arrays <s> A complete technique that does not use any additional components for enhancing the yield of field-programmable logic arrays (FPLAs) is presented. In this approach, the inherent sparsity (absence of devices at crosspoints) of programmable logic arrays (PLAs) is utilized to mask certain types of manufacturing defects within the unprogrammed FPLAs, thus reclaiming chips which are otherwise discarded. Two categories of faults (called type 1 and type 2) are considered. Type-1 faults, which can be diagnosed a priori, are considered first. After diagnosing type 1 faults, the mask can be reconfigured around the faulty crosspoints. A streamlined bipartite matching algorithm is presented to enhance the speed of this reconfiguration. The uniqueness of the approach is that the programming of an FPLA is formulated as a graph theoretic problem for which a polynomial time solution exists. Type-2 faults in general cannot be diagnosed a priori. Therefore, a dynamic technique is presented for the repair of type-2 faults. Unused product lines of the FPLA are utilized for the repair. With a sufficient number of excess product lines, it is shown that a defective FPLA is guaranteed to be rendered usable. A probability measure for the usability of defective FPLA is obtained both with and without the implementation of this technique. Computer studies have shown that FPLAs with even a large number of defects can be successfully repaired, thereby increasing the yield. > <s> BIB006
In a historical context, nano-crossbar structures are very similar to programmable logic arrays (PLA's) introduced in BIB001 , in terms of circuit structures, programming features, and utilization. Therefore, examining the progression of fault-tolerance studies regarding PLA's can be insightful. Particular aspects are as follows: (1) Test generation and fault detection  BIB002 , which basically deals with producing comprehensive test vectors; (2) yield analysis and redundancy employment BIB003 BIB004 , which aims to maximize yield and allocate redundant elements; and (3) fault modeling with simulations BIB005 , which formalizes the type of faults for stuck-at, bridging, missing, and broken crosspoints that is also adopted in nano-crossbar terminology. Additionally, different from these studies, in BIB006 fault tolerance is achieved with reconfiguration of a PLA by using bipartite graph model that can be considered as the archetype of the techniques used in nano-crossbars. In this study, exaggeratedly high fault rates are considered similar to the treatment in nano-crossbars. Indeed, developed with a well-established CMOS technology, PLA's do have considerably low fault rates. Therefore simple configuration approaches are adequate for fault tolerance that justifies the lack of related studies in the literature after 1990s. • Tolerated by reconfiguration or redundancy