A New Memetic Algorithm With Fitness Approximation for the Defect-Tolerant Logic Mapping in Crossbar-Based Nanoarchitectures
A New Memetic Algorithm With Fitness Approximation for the Defect-Tolerant Logic Mapping in Crossbar-Based Nanoarchitectures
复制标题
一种新的具有适应度近似的模因算法，用于基于 Crossbar 的纳米结构中的缺陷容忍逻辑映射
DOI：
10.1109/tevc.2013.2288779
复制
发表时间：
2014-12
影响因子：
14.3
通讯作者：
Yuan B
中科院分区：
文献类型：
--
作者：
Yuan Bo;Li Bin;Weise Thomas;Li Bin;Yao Xin;Yao Xin;Yuan B
容错逻辑映射（DTLM）已被证明是一个NP完全组合搜索问题，是新兴的基于交叉开关的纳米架构中逻辑实现的关键步骤。然而，到目前为止，还没有针对 DTLM 提出实际令人满意的解决方案。在本文中，首先通过引入最大二部匹配将 DTLM 问题建模为组合优化问题。然后，提出了一种新的适应度近似的模因算法（MA/FA）来有效地解决优化问题。在MA/FA中，设计了一种新的贪婪重分配局部搜索算子，能够利用来自问题实例的领域知识和信息，帮助算法以相对较低的计算资源消耗找到最佳逻辑映射。采用适应度近似方法，大大减少了适应度评估的时间消耗。此外，提出了一种结合精确适应度评估方法和近似适应度评估方法的混合适应度评估策略，以平衡适应度评估的准确性和时间效率。所提出方法的有效性和效率在大量不同规模的基准实例上得到了验证和评估，并且还观察到了MA/FA在有效性和效率之间保持良好平衡的优势。
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.
登录
查看更多内容
DOI：
10.1145/1167943.1167945
发表时间：
2006-07
期刊：
ACM J. Emerg. Technol. Comput. Syst.
影响因子：
--
作者：
M. Tahoori
通讯作者：
M. Tahoori
DOI：
10.1145/1543438.1543441
发表时间：
2009-07
期刊：
ACM J. Emerg. Technol. Comput. Syst.
影响因子：
--
作者：
M. Crocker;X. Hu;M. Niemier
通讯作者：
M. Crocker;X. Hu;M. Niemier
DOI：
10.1109/tcsi.2007.907875
发表时间：
2007-11
期刊：
IEEE Transactions on Circuits and Systems I: Regular Papers
影响因子：
--
作者：
Ahmad A. Al-Yamani;S. Ramsundar;D. Pradhan
通讯作者：
Ahmad A. Al-Yamani;S. Ramsundar;D. Pradhan
DOI：
10.1016/j.sysarc.2008.01.001
发表时间：
2008-08
期刊：
J. Syst. Archit.
影响因子：
--
作者：
Y. Yellambalase;Minsu Choi
通讯作者：
Y. Yellambalase;Minsu Choi
DOI：
10.1109/tsmcb.2006.883268
发表时间：
2007-02
期刊：
IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics)
影响因子：
--
作者：
Maolin Tang;X. Yao
通讯作者：
Maolin Tang;X. Yao