Defect-and Variation-Tolerant Logic Mapping in Nanocrossbar Using Bipartite Matching and Memetic Algorithm

Bo YUAN, Bin LI, Huanhuan CHEN, Xin YAO

Research output: Journal PublicationsJournal Article (refereed)peer-review

9 Citations (Scopus)


High defect density and extreme parameter variation make it very difficult to implement reliable logic functions in crossbar-based nanoarchitectures. It is a major design challenge to tolerate defects and variations simultaneously for such architectures. In this paper, a method based on a bipartite matching and memetic algorithm is proposed for defect-and variation-tolerant logic mapping (D/VTLM) problem in crossbar-based nanoarchitectures. In the proposed method, the search space of the D/VTLM problem can be dramatically reduced through the introduction of the min-max weight maximum-bipartite-matching (MMW-MBM) and a related heuristic bipartite matching method. MMW-MBM is defined on a weighted bipartite graph as an MBM, where the maximal weight of the edges in the matching has a minimal value. In addition, a defect-and variation-aware local search (D/VALS) operator is proposed for D/VTLM and embedded in a global search framework. The D/VALS operator is able to utilize the domain knowledge extracted from problem instances and, thus, has the potential to search the solution space more efficiently. Compared with the state-of-the-art heuristic and recursive algorithms, and a simulated annealing algorithm, the good performance of our proposed method is verified on a 3-bit adder and a large set of random benchmarks of various scales. © 2016 IEEE.
Original languageEnglish
Article number7425238
Pages (from-to)2813-2826
Number of pages14
JournalIEEE Transactions on Very Large Scale Integration (VLSI) Systems
Issue number9
Early online date3 Mar 2016
Publication statusPublished - Sept 2016
Externally publishedYes

Bibliographical note

This work was supported in part by the Engineering and Physical Sciences Research Council under Grants EP/J017515/1 and EP/K001523/1; in part by the China Post-Doctoral Science Foundation under Grants 2014M560520 and 2015T80666; in part by the National Natural Science Foundation of China under Grants 61203292, 61329302, 61473271, 61503357, 61511130083, and 91546116; and in part by the Fundamental Research Funds for the Central Universities under Grant WK0110000046.


  • Fault tolerance
  • logic mapping
  • memetic algorithm (MA)
  • nanoarchitecture
  • Nanoelectronics


Dive into the research topics of 'Defect-and Variation-Tolerant Logic Mapping in Nanocrossbar Using Bipartite Matching and Memetic Algorithm'. Together they form a unique fingerprint.

Cite this