A Survey of Fault-Tolerance Algorithms for Reconfigurable Nano-Crossbar Arrays <s> Evaluation of Algorithms <s> Molecular electronics offer an alternative pathway to construct nanoscale circuits in which the critical dimension is naturally associated with molecular sizes. We describe the fabrication and testing of nanoscale molecular-electronic circuits that comprise a molecular monolayer of [2]rotaxanes sandwiched between metal nanowires to form an 8 × 8 crossbar within a 1 µm 2 area. The resistance at each cross point of the crossbar can be switched reversibly. By using each cross point as an active memory cell, crossbar circuits were operated as rewritable, nonvolatile memory with a density of 6. 4G bits cm −2 .B ys etting the resistances at specific cross points, two 4 × 4s ubarrays of the crossbar were configured to be a nanoscale demultiplexer and multiplexer that were used to read memory bits in a third subarray. <s> BIB001 </s> A Survey of Fault-Tolerance Algorithms for Reconfigurable Nano-Crossbar Arrays <s> Evaluation of Algorithms <s> We present an algorithm for graph isomorphism and subgraph isomorphism suited for dealing with large graphs. A first version of the algorithm has been presented in a previous paper, where we examined its performance for the isomorphism of small and medium size graphs. The algorithm is improved here to reduce its spatial complexity and to achieve a better performance on large graphs; its features are analyzed in detail with special reference to time and memory requirements. The results of a testing performed on a publicly available database of synthetically generated graphs and on graphs relative to a real application dealing with technical drawings are presented, confirming the effectiveness of the approach, especially when working with large graphs. <s> BIB002 </s> A Survey of Fault-Tolerance Algorithms for Reconfigurable Nano-Crossbar Arrays <s> Evaluation of Algorithms <s> Polynomial algorithms are given for the following two problems: given a graph with $n$ vertices and $m$ edges, where $m \ge 3 n^{3/2}$, find a complete balanced bipartite subgraph with parts about $\ln n/(\ln (n^2/m))$, given a graph with $n$ vertices, find a decomposition of its edges into complete balanced bipartite graphs having altogether $O(n^2 / \ln n)$ vertices. Previous proofs of the existence of such objects, due to K\H{o}v\'ari-S\'os-Tur\'an, Chung-Erd\H{o}s-Spencer, Bublitz and Tuza were non-constructive. <s> BIB003 </s> A Survey of Fault-Tolerance Algorithms for Reconfigurable Nano-Crossbar Arrays <s> Evaluation of Algorithms <s> The maximum balanced biclique problem (MBBP), an NP-hard combinatorial optimization problem, has been attracting more attention in recent years. Existing node-deletion-based algorithms usually fail to find high-quality solutions due to their easy stagnation in local optima, especially when the scale of the problem grows large. In this paper, a new algorithm for the MBBP, evolutionary algorithm with structure mutation (EA/SM), is proposed. In the EA/SM framework, local search complemented with a repair-assisted restart process is adopted. A new mutation operator, SM, is proposed to enhance the exploration during the local search process. The SM can change the structure of solutions dynamically while keeping their size (fitness) and the feasibility unchanged. It implements a kind of large mutation in the structure space of MBBP to help the algorithm escape from local optima. An MBBP-specific local search operator is designed to improve the quality of solutions efficiently; besides, a new repair-assisted restart process is introduced, in which the Marchiori’s heuristic repair is modified to repair every new solution reinitialized by an estimation of distribution algorithm (EDA)-like process. The proposed algorithm is evaluated on a large set of benchmark graphs with various scales and densities. Experimental results show that: 1) EA/SM produces significantly better results than the state-of-the-art heuristic algorithms; 2) it also outperforms a repair-based EDA and a repair-based genetic algorithm on all benchmark graphs; and 3) the advantages of EA/SM are mainly due to the introduction of the new SM operator and the new repair-assisted restart process. <s> BIB004
The presented algorithms directly use a graph representation of a defective nano-crossbar as an input. They do not deal with defect types and their representations in graphs. Indeed, one can directly find a graph representation of a crossbar by erasing edges for stuck-at deactivated defects and nodes for stuck-at activated defects as previously explained in Section 4.1. A real concern of defect-unaware methods is their considerably low yield or (k/n) 2 , especially for high defect rates. When n = 250 and the fault rate is 15% that is a reasonable value for nano arrays BIB001 , the best algorithm finds k values as high as 30. It means that only 1% of the crossbar can be used. This phenomena undermines the basic attraction of nano-crossbars offering superior density features. Another concern is that all of the mentioned articles study only stuck-at deactivated defects except for Tahoori (2006) . Tahoori shows that in case of having stuck-at activated defects that results in removal of all corresponding nodes, yield is impractically low. All of the examined heuristic algorithms have polynomial runtime complexities. As long as crossbar size is under 1000 × 1000 and defect rates smaller than 15%, they run in a micro second domain that is quite satisfactory. Another interesting observation is that, the algorithms are immune to the differentiation of fault rates. In the next subsection, we conduct detailed simulations regarding their runtime and yield. As a final note, defect-unaware methods in principle try to solve the problem of finding the maximum biclique in a bipartite graph. For this reason, similar problem formulations used in different fields such as those proposed in BIB003 and BIB004 can be directly applied to the defect-unaware methods especially for the improvement of yield. It is reasonable to assume that defect rates of nano-crossbars is high up to 20% that dramatically elevate the computational load of the algorithms. Because of that, runtime parameter of the algorithms can be considered as the major factor in evaluations. Generally, ILP and graph embedding approaches yield poor runtime results. Especially, recursive nature of the embedding algorithm causes impractical runtimes for larger crossbar sizes. On the other hand, heuristic nature of maximum bipartite matching approaches provides an upper hand in terms of runtime. Nevertheless constructing the bipartite graph is very time-consuming. Also, if the graph is rather sparse, meaning that a few edges are present for possible matchings, exact algorithms need to be applied, which is also time-consuming. As for matrix matching approaches, runtime results are fairly satisfactory for even larger size logic functions. However, since matching is advancing through one dimension (rows), increase of the column size drastically worsens the success rate of the algorithms. Considering the yield, maximum bipartite-matching-and matrix-matching-based algorithms produce the best results. However, a prevalent trend in the literature is realizing a logic function with a larger size crossbar, generally 1.5 times larger, than the optimal size. Therefore, yield analysis is not conducted extensively for most of the studies. Another important point is the algorithms' capability of handling multiple-type defects. As we previously mention, only (Gören et al. 2011) fine-tunes the algorithm according to defect types. The rest of the articles only consider stuck-at deactivated types, so their proposed heuristics perform under this restriction. If multiple-type defects were to be considered, then bipartite graphs would be sparser (lower possibility of matching between products and outputs) that makes harder to find a maximum bipartite matching. This problem is also applicable for graph embedding and ILP-based methods. As a final note, defect-aware methods use a wide range of different problem formalizations not necessarily proposed for nano-crossbar arrays. Therefore studies related to subgraph isomorphism BIB002 ) and assignment problems (Chu and Beasley 1997) can be directly applied to the defect-aware methods.