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

Research output: Contribution to journalArticle

Standard

A new memetic algorithm with fitness approximation for the defect-tolerant logic mapping in crossbar-based nanoarchitectures. / Yuan, Bo; Li, Bin; Weise, Thomas; Yao, Xin.

In: IEEE Transactions on Evolutionary Computation, Vol. 18, No. 6, 6655961, 01.12.2014, p. 846-859.

Research output: Contribution to journalArticle

Harvard

APA

Vancouver

Author

Bibtex

@article{3877fe1c84ae413c8ff17f04c82ec2c3,
title = "A new memetic algorithm with fitness approximation for the defect-tolerant logic mapping in crossbar-based nanoarchitectures",
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 = "crossbar-based nanoelectronics, defect-tolerant logic mapping (DTLM), fitness approximation, local search, maximum-bipartite-matching (MBM), Memetic algorithms",
author = "Bo Yuan and Bin Li and Thomas Weise and Xin Yao",
year = "2014",
month = dec,
day = "1",
doi = "10.1109/TEVC.2013.2288779",
language = "English",
volume = "18",
pages = "846--859",
journal = "IEEE Transactions on Evolutionary Computation",
issn = "1089-778X",
publisher = "Institute of Electrical and Electronics Engineers (IEEE)",
number = "6",

}

RIS

TY - JOUR

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

AU - Yuan, Bo

AU - Li, Bin

AU - Weise, Thomas

AU - Yao, Xin

PY - 2014/12/1

Y1 - 2014/12/1

N2 - 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.

AB - 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.

KW - crossbar-based nanoelectronics

KW - defect-tolerant logic mapping (DTLM)

KW - fitness approximation

KW - local search

KW - maximum-bipartite-matching (MBM)

KW - Memetic algorithms

UR - http://www.scopus.com/inward/record.url?scp=84914097965&partnerID=8YFLogxK

U2 - 10.1109/TEVC.2013.2288779

DO - 10.1109/TEVC.2013.2288779

M3 - Article

AN - SCOPUS:84914097965

VL - 18

SP - 846

EP - 859

JO - IEEE Transactions on Evolutionary Computation

JF - IEEE Transactions on Evolutionary Computation

SN - 1089-778X

IS - 6

M1 - 6655961

ER -