A Survey of Fault-Tolerance Algorithms for Reconfigurable Nano-Crossbar Arrays <s> DISCUSSIONS <s> While the exact manufacturing process for nanoscale computing devices is uncertain, it is abundantly clear that future technology nodes will see an increase in defect rates. Therefore, it is of paramount importance to construct new architectures and design methodologies that can tolerate large numbers of defects. Defect maps are a necessity in the future design flows, and research on their practical construction is essential. In this work, we study the use of Bloom filters as a data structure for defect maps. We show that Bloom filters provide the right tradeoff between accuracy and space-efficiency. In particular, they can help simplify the nanosystem design flow by embedding defect information within the nanosystem delivered by the manufacturers. We develop a novel nanoscale memory design that uses this concept. It does not rely on a voting strategy, and utilizes the device redundancy more effectively than existing approaches. <s> BIB001 </s> A Survey of Fault-Tolerance Algorithms for Reconfigurable Nano-Crossbar Arrays <s> DISCUSSIONS <s> Current manufacturing of molecular electronics introduces defects, but circuits can be implemented by including redundant components. We identify reliability thresholds for implementing binary adders in the crossbar approach to molecular electronics. These thresholds vary among different implementations of the same logical formula, giving a tradeoff between yield and circuit area. For instance, one implementation has at least 90% yield with up to 30% defects for an area 1.8 times larger than the minimum required for a defect-free crossbar. <s> BIB002 </s> A Survey of Fault-Tolerance Algorithms for Reconfigurable Nano-Crossbar Arrays <s> DISCUSSIONS <s> Bottom-up self-assembly nanofabrication process yields nanodevices with significantly more variations compared to the conventional top-down lithography used in CMOS fabrication. This is in addition to an increased defect density expected for self-assembled nanodevices. Therefore, it is one of the major design challenges to tolerate variation, in addition to defect tolerance, in emerging nano architectures. In this paper, we present a solution for variation tolerant logic mapping for FET based crossbar array nano architectures using Simulated Annealing. Furthermore, we extended the framework for defect tolerance. Experimental results including comparison with exact method confirm the effectiveness of the proposed approach. <s> BIB003 </s> A Survey of Fault-Tolerance Algorithms for Reconfigurable Nano-Crossbar Arrays <s> DISCUSSIONS <s> This paper proposes an approach for testing a nanocrossbar switch; fault detection is considered in the presence of faulty switches and nets (of a permanent nature only) in the crossbar. To ensure detection, a one-to-one (onto) relationship in the setting (programming) of the switches is established in each of the configurations of the crossbar. This is accomplished using a constant-sum transformation of the characteristic matrix of the crossbar by utilizing different graph algorithms in O(N4.5) where N is the matrix dimension. Matrix properties are related to graph algorithms to generate permutation matrices as corresponding to the configurations (phases) of the crossbar. The conditions by which multiple faults are detected by the modified counting sequence (as test set), are proved. Simulation results are provided to further substantiate the validity of the proposed approach to test nanocrossbars of very large dimension and with different switch distribution. <s> BIB004 </s> A Survey of Fault-Tolerance Algorithms for Reconfigurable Nano-Crossbar Arrays <s> DISCUSSIONS <s> Nanotechnology-based manufacturing, relying on self-assembly of nanotubes or nanowires, has shown promising potentials for future nanoscale circuit designs. However, high defect density and extreme process variations for crossbar-based nanoarchitectures are expected to be fundamental design challenges. Consequently, defect and variation issues must be considered in logic mapping on nanoscale crossbars. In this paper, we establish a mathematical model for the simultaneous variation and defect-aware logic mapping of multi-outputs crossbar arrays. We model this problem using a new sub-weighted-graph isomorphism problem and propose a greedy algorithm for the variation- and defect-aware logic mapping. Based on Monte-Carlo simulation, we compare the proposed technique with other logic mapping techniques such as, variation-unaware and exhaustive search mapping in terms of accuracy as well as runtime. Results show that the effectiveness of our new mapping technique in variation and defect tolerance as well as run time improvement. <s> BIB005 </s> A Survey of Fault-Tolerance Algorithms for Reconfigurable Nano-Crossbar Arrays <s> DISCUSSIONS <s> Framework of the hybrid algorithm. The input mapping vector is encoded as chromosome in the upper level multiobjective evolutionary algorithm. Fitness of each individual in the upper level is calculated via solving lower lever problem modeled as MMBM and calling HLP. The two level optimization problems share the same two optimization objectives. Local search is included in the upper level evolutionary algorithm with no extra fitness calculation cost. The problem of variation tolerant logical mapping on nanoscale crossbar architectures is modeled as a bilevel multiobjective optimization problem. A hybrid multiobjective evolutionary algorithm is designed to solve the problem in a bilevel optimization framework.The lower level problem is modeled as a MMBM problem, and a Hungarian-based Linear Programming (HLP) method is proposed, which can solve MMBM in polynomial time.The upper level optimization problem is solved by evolutionary multiobjective optimization algorithms, where a greedy reassignment local search operator, capable of leveraging the domain knowledge and information from problem instances, is introduced to improve the efficiency of the algorithm. Nanoscale crossbar architectures have received steadily growing interests as a result of their great potential to be main building blocks in nanoelectronic circuits. However, due to the extremely small size of nanodevices and the bottom-up self-assembly nanofabrication process, considerable process variation will be an inherent vice for crossbar nanoarchitectures. In this paper, the variation tolerant logical mapping problem is treated as a bilevel multiobjective optimization problem. Since variation mapping is an NP-complete problem, a hybrid multiobjective evolutionary algorithm is designed to solve the problem adhering to a bilevel optimization framework. The lower level optimization problem, most frequently tackled, is modeled as the min-max-weight and min-weight-gap bipartite matching (MMBM) problem, and a Hungarian-based linear programming (HLP) method is proposed to solve MMBM in polynomial time. The upper level optimization problem is solved by evolutionary multiobjective optimization algorithms, where a greedy reassignment local search operator, capable of exploiting the domain knowledge and information from problem instances, is introduced to improve the efficiency of the algorithm. The numerical experiment results show the effectiveness and efficiency of proposed techniques for the variation tolerant logical mapping problem. <s> BIB006
In this study, we survey fault-tolerance algorithms of reconfigurable nano-crossbar arrays applicable in logic mapping and configuration processes. Both permanent and transient faults with different fault modeling approaches are covered. We conduct comprehensive simulations to evaluate the proposed algorithms using different fault rates on industrial benchmark functions. In addition, different area yield values, and multiple type defect occurrences are considered. To make concrete discussions with future directions, brief explanations of the historical development of fault tolerance in nano-crossbar arrays are given as follows. Nano-crossbar arrays were first proposed in 1990s to overcome the upcoming challenges of integrated circuit miniaturization. Its configurable/reconfigurable attributes as well as inherent fault-tolerance capabilities attracted numerous researchers. However, as expected, this new technology comes with some challenges and fault tolerance is one of the significant ones. Fault rates are much higher for nano-crossbars compared to those of conventional CMOS circuits. Therefore, developing efficient fault-tolerance techniques for nano-crossbars is a must. At first, defect-unaware methods were proposed motivated by the fact that, configuring defective crossbars would be time-consuming and impractical. However, area yields of defect-unaware approaches are proven to be less than ideal. In addition, we show that, stuck-at activated defects severely decrease the already low area yield values. As a result, although the number of studies in this field is limited, improving the yield remains to be a strong motivation for future studies with the fact that achieving defect-free sub crossbars enables us to use existing and well-studied tools. The line of research that has the most abundant studies is defect-aware methods. Although research on defect-aware approaches can be considered as mature, there are still important problems waiting to be solved, including a need for specific algorithms to fine-tune the mapping problem according to multiple-type defect occurrences and different defect distributions. Additionally, current methods such as fitness approximation and matrix sorting are only able to respond to low defect rates; this issue should be solved. Another important research direction is developing techniques to restore defect mappings during the configuration process. A similar attempt using probabilistic data structure is presented in BIB001 using bloom filters. Last but not least, in terms of area yield, current methods are not fully equipped to produce optimum results for the realization of given logic functions. Inspiring studies considering both fault tolerance and yield analysis through the manipulation of logic function are presented in  and BIB002 . New methods producing better results under stricter area yield constraints would be a good line of investigation. Additionally, presented approaches can be applicable for memory structures due to similar problem formalizations  BIB004 , as well as for variance tolerance of the crossbars BIB003 BIB005 BIB006 . Another trend is to develop transient fault-tolerance techniques. Fault masking and reconfiguration with online testing have been proposed. Even though presented methods are competent, without the field data it is hard to justify the results. In addition, only configuration level faults are considered in the literature; component level faults (or regarding the functionality) are open to further investigation. Also, physical realization of the architectures is still in infancy, so this line of inquiry is more reasonable with robust development and wide fabrication of nano-crossbars. As a summary, we can list the future directions for fault-tolerance techniques for nano-crossbar arrays as follows: -Fine-tuning for multiple-type faults and different fault distributions; -Compression and representation of defect maps; -Improvement of area yield to increase density; -Decomposition of given logic functions for area optimization; -Developing variance tolerance techniques; -Developing fault-tolerance techniques for nano-crossbar-based memory structures; -Transient fault-tolerance covering component level faults; -Reliability forecasting for nano-crossbar arrays; -Developing architectural level transient fault-tolerance techniques; and 79:32 O. Tunali and M. Altun -Developing fault-tolerance techniques for new technologies based on crossbar arrays including resistive/memristive networks.