A Survey of Fault-Tolerance Algorithms for Reconfigurable Nano-Crossbar Arrays <s> Matrix-Based <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> BIB001 </s> A Survey of Fault-Tolerance Algorithms for Reconfigurable Nano-Crossbar Arrays <s> Matrix-Based <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> BIB002
Approaches. Similar to graph-based approaches, we start our experiments with optimal size crossbars, and P D = 15%. Here, Tunali's algorithm is the clear winner in terms of the all parameters. However, it is not able to find a valid mapping for larger size examples with an only exception of the benchmark "alu4." Therefore scalability is still an important issue for matrixbased algorithms. Results are given in Table 9 . In our last two experiments, Tunali's approach also produces superior results. It is clear that Goren's approach is not scalable due mainly to its fairly complicated sorting process. However, it should be noted that Tunali's success rate for a harder case like "misex2" is inferior to Yuan's approach when stuck-at activated defects are introduced to the problem. Memetic nature of Yuan's approach fine tunes mapping process better than Tunali's sorting approach. Results are given in Tables 10 and 11 . 5.6.3 Comparisons of All Algorithms. In Table 12 , general features of the algorithms are evaluated by using four levels: poor, moderate, good, and excellent. Features of satisfiability, ILP and graph-embedding-based algorithms are interpreted through the comparison performed in the articles BIB001 BIB002 , respectively. Examining the results, we see that certain attributes need to be considered before choosing a suitable method. When area yield is an important factor, for easier cases Tunali's approach and for harder cases Yuan's 