A new memetic algorithm with fitness approximation for the defect-tolerant logic mapping in crossbar-based nanoarchitectures

Bo YUAN, Bin LI, Thomas WEISE, Xin YAO

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

32 Citations (Scopus)

Abstract

The defect-tolerant logic mapping (DTLM), which has been proved to be an NP-complete combinatorial search problem, is a key step for logic implementation in emerging crossbar-based nano-architectures. However, no practically satisfactory solution has been suggested for the DTLM until now. In this paper, the problem of DTLM is first modeled as a combinatorial optimization problem through the introduction of maximum-bipartite-matching. Then, a new memetic algorithm with fitness approximation (MA/FA) is proposed to solve the optimization problem efficiently. In MA/FA, a new greedy reassignment local search operator, capable of utilizing the domain knowledge and information from problem instances, is designed to help the algorithm find optimal logic mapping with consumption of relatively lower computational resources. A fitness approximation method is adopted to reduce the time consumption of fitness evaluation dramatically. In addition, a hybrid fitness evaluation strategy that combines the exact and approximated fitness evaluation methods is presented to balance the accuracy and time efficiency of fitness evaluation. The effectiveness and efficiency of the proposed methods are testified and evaluated on a large set of benchmark instances of various scales, and the advantage of MA/FA on keeping good balance between effectiveness and efficiency is also observed. © 1997-2012 IEEE.
Original languageEnglish
Article number6655961
Pages (from-to)846-859
Number of pages14
JournalIEEE Transactions on Evolutionary Computation
Volume18
Issue number6
Early online date20 Nov 2014
DOIs
Publication statusPublished - Dec 2014
Externally publishedYes

Funding

This work was supported in part by the National Natural Science Foundation of China under Grant 61071024, Grant 61331051, Grant 61175065, Grant 61150110488, and Grant 61329302, in part by the European Union Seventh Framework Program under Grant 247619, in part by the National Natural Science Foundation of Anhui Province under Grant 1108085J16, in part by the Chinese Academy of Sciences Fellowship for Young International Scientists under Grant 2011Y1GB01, and in part by the Special Financial Grant 201104329 from the China Post- Doctoral Science Foundation.

Keywords

  • crossbar-based nanoelectronics
  • defect-tolerant logic mapping (DTLM)
  • fitness approximation
  • local search
  • maximum-bipartite-matching (MBM)
  • Memetic algorithms

Fingerprint

Dive into the research topics of 'A new memetic algorithm with fitness approximation for the defect-tolerant logic mapping in crossbar-based nanoarchitectures'. Together they form a unique fingerprint.

Cite this