A Survey of Fault-Tolerance Algorithms for Reconfigurable Nano-Crossbar Arrays <s> ILP-Based Algorithms <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> BIB001 </s> A Survey of Fault-Tolerance Algorithms for Reconfigurable Nano-Crossbar Arrays <s> ILP-Based Algorithms <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
Yang and Zamani propose to transform the logic mapping problem into a constrained integer linear programming (ILP) problem in BIB001 and BIB002 . To obtain a valid mapping, constraint equations are derived. Parameters X and Y respectively show the matching status of the rows corresponding to function product and crossbar output, and columns corresponding to function variable and crossbar input. If a product P 1 can be matched with an output O 1 , then X P 1 _O 1 becomes 1; otherwise, X P 1 _O 1 = 0. The same condition is defined for Y for column matching. To map a k 1 x k 2 function matrix to n 1 x n 2 crossbar matrix following constraints need to be met. If the ith row (product P) of a function matrix can be matched with the jth row (output O) of a crossbar matrix, then X i_j = 1; otherwise, X i_j = 0. For a valid row mapping two conditions are imposed: (1) Each row in the function matrix should be matched with only a single row in the crossbar matrix, and (2) each row in the crossbar matrix should be matched at most one row in the function matrix. The following constraint (1) formalize these conditions. Same procedures are applied for column matching as given in a constraint (2). One more parameter is introduced Z i_j,i _j such that it takes the value of 1 if X i_j = Y i _j = 1; otherwise, Z = 0. To find a valid mapping, every element of a function matrix requires a valid mapping. The below constraint (3) ensures this condition, By using these three constraints, a valid mapping can be found. An important point is that the proposed algorithm helps to prune solution space and decrease the computation time by finding impossible matchings corresponding to zero valued X 's and Y 's.