DocumentCode :
81507
Title :
A New Memetic Algorithm With Fitness Approximation for the Defect-Tolerant Logic Mapping in Crossbar-Based Nanoarchitectures
Author :
Bo Yuan ; Bin Li ; Weise, Thomas ; Xin Yao
Author_Institution :
USTC-Birmingham Joint Res. Inst. in Intell. Comput. & Its Applic. (UBRI), Univ. of Sci. & Technol. of China, Hefei, China
Volume :
18
Issue :
6
fYear :
2014
fDate :
Dec. 2014
Firstpage :
846
Lastpage :
859
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.
Keywords :
CMOS logic circuits; approximation theory; circuit optimisation; combinatorial mathematics; computational complexity; greedy algorithms; nanoelectronics; search problems; CMOS techniques; DTLM; MA-FA; NP-complete combinatorial search problem; combinatorial optimization problem; computational resources; crossbar-based nanoarchitectures; defect-tolerant logic mapping; fitness approximation; greedy reassignment local search operator; hybrid fitness evaluation strategy; maximum-bipartite-matching; memetic algorithm with fitness approximation method; Algorithm design and analysis; Approximation algorithms; Approximation methods; Bipartite graph; Heuristic algorithms; Logic functions; Search problems; Crossbar-based nanoelectronics; Memetic algorithms; crossbar-based nanoelectronics; defect-tolerant logic mapping (DTLM); fitness approximation; local search; maximum-bipartite-matching (MBM); memetic algorithms;
fLanguage :
English
Journal_Title :
Evolutionary Computation, IEEE Transactions on
Publisher :
ieee
ISSN :
1089-778X
Type :
jour
DOI :
10.1109/TEVC.2013.2288779
Filename :
6655961
Link To Document :
بازگشت