A Survey of Fault-Tolerance Algorithms for Reconfigurable Nano-Crossbar Arrays <s> Maximum Bipartite Matching <s> The present paper shows how to construct a maximum matching in a bipartite graph with n vertices and m edges in a number of computation steps proportional to (m+n) n. <s> BIB001 </s> A Survey of Fault-Tolerance Algorithms for Reconfigurable Nano-Crossbar Arrays <s> Maximum Bipartite Matching <s> Recent developments suggest both plausible fabrication techniques and viable architectures for building sublithographic programmable logic arrays using molecular-scale wires and switches. Designs at this scale will see much higher defect rates than in conventional lithography. However, these defects need not be an impediment to programmable logic design as this scale. We introduce a strategy for tolerating defective crosspoints and develop a linear-time, greedy algorithm for mapping PLA logic around crosspoint defects. We note that P-term fanin must be bounded to guarantee low overhead mapping and develop analytical guidelines for bounding fanin. We further quantify analytical and empirical mapping overhead rates. Including fanin bounding, our greedy mapping algorithm maps a large set of benchmark designs with 13% average overhead for random junction defect rates as high as 20%. <s> BIB002 </s> A Survey of Fault-Tolerance Algorithms for Reconfigurable Nano-Crossbar Arrays <s> Maximum Bipartite Matching <s> As the end of the semiconductor roadmap for CMOS approaches, architectures based on nanoscale molecular devices are attracting attention. Among several alternatives, silicon nanowires and carbon nanotubes are the two most promising nanotechnologies according to the ITRS. These technologies may enable scaling deep into the nanometer regime. However, they suffer from very defect-prone manufacturing processes. Although the reconfigurability property of the nanoscale devices can be used to tolerate high defect rates, it may not be possible to locate all defects. With very high device densities, testing each component may not be possible because of time or technology restrictions. This points to a scenario in which even though the devices are tested, the tests are not very comprehensive at locating defects, and hence the shipped chips are still defective. Moreover, the devices in the nanometer range will be susceptible to transient faults which can produce arbitrary soft errors. Despite these drawbacks, it is possible to make nanoscale architectures practical and realistic by introducing defect and fault tolerance. In this article, we propose and evaluate a hybrid nanowire-CMOS architecture that addresses all three problems—namely high defect rates, unlocated defects, and transient faults—at the same time. This goal is achieved by using multiple levels of redundancy and majority voters. A key aspect of the architecture is that it contains a judicious balance of both nanoscale and traditional CMOS components. A companion to the architecture is a compiler with heuristics to quickly determine if logic can be mapped onto partially defective nanoscale elements. The heuristics make it possible to introduce defect-awareness in placement and routing. The architecture and compiler are evaluated by applying the complete design flow to several benchmarks. <s> BIB003
In a defective nano-crossbar, arbitrary assignment of products of the given function to the crossbar outputs might result in an error as previously visualized in Figure 5 . To determine the erroneous cases, one can use a bipartite graph having product (P) and output (O) nodes. If there is an edge Fan-in is # of variables in a product 2: while P ∅ do 3: Choose the first P i 4: while between a product and an output, then the product can be mapped to the output. Thus, all possible mapping configurations can be represented by edges. An example is given in Figure 9 . After the graph construction, finding a maximum or perfect matching that corresponds to a set of edges such that every node is incident to exactly one edge, would yield a valid mapping. For this purpose, exact algorithms can be used including Ford-Fulkerson maximum flow network (Ford Jr and Fulkerson 1955) and Hopcroft-Karp algorithm BIB001 . However, constructing a bipartite graph is a costly process especially for high defect rates seen in nano-crossbars, so certain heuristics are proposed. Naeimi proposes a greedy heuristic algorithm without constructing a bipartite graph; instead he uses expected values of node degrees BIB002 . Since a product with a high number of variables (fan-in) are harder to map, its node degree would be smaller. The algorithm starts matching products in a decreasing order of fan-in's with choosing random output nodes. Naemi's approach is fairly competent in terms of scalability. A pseudocode of the algorithm is given in Algorithm 2. Simsir also uses a heuristic algorithm with partially constructing the bipartite graph BIB003 ). First, variables from most common to least common (fan-out values) are assigned to least defective to most defective input lines, respectively. This process is named as pin assignment. Second, a distinct edge is found for every product node and then an exact algorithm is performed to find a maximum matching. In case no matching is found, an extra edge is searched for product nodes of bipartite graph and the exact algorithm is performed at the end. This process continues until a valid matching is found or another pin assignment is tried in case of no matching. A pseudocode of the algorithm is given in Algorithm 3. Yuan proposes a memetic algorithm with fitness approximation ). Unlike Simsir's approach, an initial random input assignment is made and fitness of the assignment is evaluated with an objective function f . Ford-Fulkerson's maximum flow method is mainly used for finding a maximum bipartite matching. Furthermore while searching for a matching, a greedy reassignment is performed by changing the input assignment for better fitness. Greediness factor (λ) of the method determines the number of input assignments to be changed. In addition, for every 10 trials (chosen as an exact evaluation gap Δ in the article), an approximate matching algorithm is used for the first 9 and an exact matching algorithm is used just for the last one that is very similar to Naeimi's greedy method. A pseudocode of the algorithm is given in Algorithm 4.