A Survey of Fault-Tolerance Algorithms for Reconfigurable Nano-Crossbar Arrays <s> Matrix Matching <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 Matching <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
A logic function and a defective nano-crossbar can be both denoted with matrices similar to incident matrices of graphs. Figures 10(a) and (b) , respectively, show a function matrix (FM) and a crossbar matrix (CM) of the logic function and the defective nano-crossbar previously used in Figure 9 . If we define which elements of logic and crossbar matrices can be matched, then it is possible to decide a valid mapping between a product and an output by checking corresponding rows. Figure 10 (c) demonstrates a compatibility table for matching. The key idea behind matrix matching is to make two matrices easily matchable by assigning proper elements for defects and variables. As follows, we examine two studies. In the first study, Goren appoints k-neighbor values to all rows and columns individually BIB001 . After determining the values, rows and columns are sorted in ascending order according to the k-neighbor values. A 1-neighbor value of a row or a column of an FM (CM) is the number of +1's (0's and +1's) in the corresponding row or column. A 2-neighbor value of a row of an FM (CM) is the sum of 1-neighbor values of the columns having intersections of +1's (0's and +1's) with the row. Following the same logic, to find a k-neighbor value of a row of an FM (CM), we add (k-1)-neighbor values of the columns if they are +1 (0 or +1). The same procedure is applied for columns. An example for finding 2-neighbor values is shown in Figure 11(a) . After the initial operations, a two-dimensional sorting is applied to rows and columns of matrices. Every row/column is regarded as a k-ary number (radix or base equals to k) with most to least significant bits (MSB and LSB) being arranged from left to right and from top to bottom. In Figures 11(b) and (c), manipulation of the FM and CM is shown according to the radix values. To sort rows and columns, radix sort algorithm is used in ascending order. Starting with the rows, radix sort begins with the LSB and sorts the rows and moves to the next bit (next column in our context) until it reaches the MSB. The same process is applied to the columns as well. This interleaving sorting continues till a stable sort is obtained. Important point is that, since an FM and a CM has two and three different elements, respectively, radix being 2 and 3 is applied. After all of these sorting processes are finalized, the matrices are matched row by row using the element compatibility as previously given in Figure 10 (c). The pseudocode is given in Algorithm 5. In the second study, Tunali first sorts matrix columns according to the number of compatible elements and rows with placing most defective rows at the top of the crossbar matrix BIB002 . Then a greedy row by row matching using Hadamard multiplication is applied with backtracking excluding previously matched rows. Since most defective rows are at the top, harder matchings are eliminated in the beginning of the process. If no matching is found for a row even with backtracking, then column permutation is altered and row by row matching is initialized again. It should be noted that, greedy row by row matching discard the overhead of the bipartite graph construction. The pseudocode is given in Algorithm 6.