A Survey of Fault-Tolerance Algorithms for Reconfigurable Nano-Crossbar Arrays <s> Simulation Results of Algorithms <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> Simulation Results of Algorithms <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> BIB002
In this section, we present experimental results of the examined defect-unaware algorithms. We generate defective nano-crossbars with assigning an independent defect probability/rate to each crosspoint that shows a uniform distribution. All defects are modeled as configuration level defects either stuck-at activated or stuck-at deactivated that is the common tendency in the literature. Monte Carlo simulations are performed for assessment with a sample size of 200. We observe that fluctuating of parameter values stabilize nearly after this threshold value. All algorithms are implemented in MATLAB. All experiments run on a 3.30GHz Intel Core i5 CPU (only single core used) with 4GB memory. To evaluate the performance of the algorithms, two different parameters are used: runtime and area yield. Area yield is the ratio of the defect-free sub-crossbar size to the initial defective crossbar size. In simulations, two defect settings are used to evaluate the four proposed heuristics. For the first setting, we only consider stuck-at deactivated types with a corresponding defect rate of P D having values of 5%, 10%, and 15%. In the second setting, stuck-at activated defects are also included with a corresponding defect rate P A = 1% with P D = 10%. As a reminder, we define yield as (k/n) 2 with respect to k 2 being the size of a defect-free sub-crossbar and n 2 being the size of an initial defective crossbar. Results of the first setting are given in Table 3 . Here, we select crossbar sizes up to 200 × 200 after which yield values become impratically low. The table shows that area yield values differ at most 6% and Heuristic 4 is the most efficient one in terms of runtime. However, yield values are still inadequate that kills the main advantage of using nano-crossbars having high area density. In the best case scenario, only 33% of a nano-crossbar can be utilized and it significantly decreases for larger crossbar sizes. Results of the second setting are given in Figure 8 . We see that defect-unaware methods is very vulnerable to stuck-at activated defects that cause eliminating both input and output lines as we previously explain in Section 4. Although we select a relatively low value of 1% for P A , area yield values are not satisfactorily. Due to the very low yield values, we pursue no other experiments regarding stuck-at activated defects higher than 1%. Table 4 summarizes the general features of the algorithms by using four levels: poor, moderate, good, and excellent. Defect-unaware algorithms produce poor area yield results. Also, stuck-at activated defects severely decrease the already very low yield values. Their runtime results are satisfactory, but it is not not generally acceptable to discard all other features for a straightforward mapping process. Obviously, this inference is obtained by considering the existing Matrix-based greedy backtracking BIB002 methods; further increase of the yield would clearly make defect-unaware approaches much more attractive. The same system and simulation settings of defect-unaware methods are also used in this section. Unlike defect-unaware algorithms for which the algorithms' performance are independent of the implemented functions, defect-aware algorithms give different results for different functions. Therefore, we use standard benchmark circuits presented in  . To evaluate the performance of the algorithms, four different parameters are used: success rate, runtime and its standard deviation, and area yield. Area yield is defined as the ratio of the optimal size defect-free array to the defective crossbar size adequate to realize a given benchmark function. For example, a logic function with 4 variables and 10 products would require an optimal crossbar size of 10 × 8 (10 for outputs and 8 for inputs with 4 variables and 4 negated forms). We also introduce a new parameter logic inclusion ration (IR) to help us to form a more intuitive understanding of the mapping problem. The number of switching crosspoints adequate to realize a logic function is denoted by IR in the form of percentage. For example, if the optimal crossbar size to implement a logic function is 10 × 10 and IR = 40%, then it means that a logic function has a literal count of 40 and we need 40 switching crosspoints to implement the function. Since we can use stuck-at activated defects as switching crosspoints, higher IR values ease the tolerance of stuck-at activated defects. Oppositely, lower IR values are preferred for the tolerance of stuck-at deactivated defects. Therefore, it is possible to categorize the easiness of the tolerance or mapping problem by considering the values of IR/P A and (1-IR)/P D for stuck-at activated and deactivated defects, respectively. As an empirical measure, if these values below three, then the sample space shrinks significantly that makes the problem very hard. We state this threshold phenomena as an experimental tendency based on our observations during the simulations of mapping trials rather than a strict compliance. Different defect distributions such as clustered, or a different set of benchmark functions might certainly produce a different threshold. Therefore, when we say easier or harder to solve, reader should understand the categorization context in terms of our experimental settings. We use three defect settings. For the first and the second ones, benchmark functions are respectively mapped to optimal (n/n = 100% yield) and 1.5 larger size ((n/(1.5 × n)) 2 ≈ 44% yield) crossbars with P D = 15%. For the third setting, 1.5 larger size crossbars are used with P D = 10% and P A = 5%. We choose those three settings to evaluate the algorithms' response to stricter area conditions and multiple-type defects. On the selection of the approaches previously given in the subsections of Section 5, we have excluded satisfiability, graph embedding and integer linear programming based ones from simulations. The reason behind that, SAT approach is already shown to be inferior to matrix model in BIB001 . In addition, graph embedding algorithm adopts a recursive characteristic and is also demonstrated to be inferior to maximum bipartite matching in . Finally, ILP needs to cope with very large number of constraint equations that requires a drastic computational operations.