A Survey of Fault-Tolerance Algorithms for Reconfigurable Nano-Crossbar Arrays <s> Variation Tolerance in Nano-Crossbar Arrays <s> Nanowire building blocks provide a promising path to small feature size and thus the ability to more densely pack logic. However, the small feature size and novel, bottom-up manufacturing process will exhibit extreme variation and produce many devices that operate outside acceptable operating ranges. One-mapping-fits-all, prefabrication assignment of logical functions to physical transistors that exhibit high threshold variation will not work—combining the wide range of physical variation in transistor threshold voltage with the wide range of fanouts in the design produces an unworkably large composite range of possible delays. Nonetheless, by carefully matching the fanout of each net to the physical threshold voltages of devices after fabrication, it is possible to reduce the net range of path delays sufficiently to achieve high system yield. By adding a modest amount of extra resources, we achieve 100% yield for systems built out of devices with 38% variation, the ITRS prediction for threshold variation in 5nm transistors. Moreover, for these systems, we maintain delay, energy and area close to the variation-free nominal case. <s> BIB001 </s> A Survey of Fault-Tolerance Algorithms for Reconfigurable Nano-Crossbar Arrays <s> Variation Tolerance in Nano-Crossbar Arrays <s> High defect density and extreme process variation for nanoscale self-assembled crossbar-based architectures have been expected to be as fundamental design challenges. Consequently, defect and variation issues must be considered on logic mapping on nanoscale crossbars. In this paper, we investigate a greedy algorithm for the variation and defect aware logic mapping of crossbar arrays. Based on Mont-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. <s> BIB002 </s> A Survey of Fault-Tolerance Algorithms for Reconfigurable Nano-Crossbar Arrays <s> Variation Tolerance in Nano-Crossbar Arrays <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> Variation Tolerance in Nano-Crossbar Arrays <s> Abstract 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 and defects in emerging nano architectures. In this paper, we present different solutions for variation tolerant logic mapping for molecular (diode-based) crossbar array nano architectures using Simulated Annealing as well as a heuristic algorithm. Experimental results and comparisons with exhaustive search and defect-unaware mapping shows the effectiveness of the proposed methods in variation and defect tolerance as well as run time improvement. <s> BIB004 </s> A Survey of Fault-Tolerance Algorithms for Reconfigurable Nano-Crossbar Arrays <s> Variation Tolerance in Nano-Crossbar Arrays <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> BIB005 </s> A Survey of Fault-Tolerance Algorithms for Reconfigurable Nano-Crossbar Arrays <s> Variation Tolerance in Nano-Crossbar Arrays <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
Considering that similar techniques are used in fault and variance tolerance, it is worth mentioning studies considering variations in crosspoint delay values for performance optimization of nano-crossbar arrays. As an earlier example, BIB001 used fan-out matching to minimize the path delays and extrapolate delay values from Committee et al. (2008) . In BIB002 and BIB005 , the authors focus on minimizing the maximum variation of the overall crossbar. A bipartite graph and integer linear programming models are used respectively. In BIB003 and BIB004 , two objectives are employed as minimizing the maximum delay and minimizing the output variations. As an algorithmic aspect, they use a simulated annealing approach. In , the problem is formulated as a multiojbective optimization problem, and an evolutionary algorithm is utilized. In BIB006 , a hybrid evolutionary algorithm is used and the problem is formulated as a bilevel multiobjective optimization.