A hybrid evolutionary algorithm for multiobjective variation tolerant logic mapping on nanoscale crossbar architectures
A hybrid evolutionary algorithm for multiobjective variation tolerant logic mapping on nanoscale crossbar architectures
复制标题
纳米级交叉架构上多目标变异容错逻辑映射的混合进化算法
DOI：
10.1016/j.asoc.2015.10.053
复制
发表时间：
2016
影响因子：
8.7
通讯作者：
李斌
中科院分区：
文献类型：
--
作者：
钟福贵;袁博;李斌
纳米级交叉结构由于其巨大的潜力成为纳米电子电路中的主要构建块而受到稳定增长的兴趣。然而，由于纳米器件的极小尺寸和自下而上的自组装纳米纤维工艺，相当大的工艺变化将是交叉杆纳米架构的固有缺点。本文将可变容差逻辑映射问题转化为一个两层多目标优化问题。由于变异映射问题是一个NP完全问题，因此采用双层优化框架设计了一种混合多目标进化算法来求解该问题。最常见的低层优化问题，被建模为最小-最大-重量和最小-重量间隙二分匹配（MMBM）问题，并提出了一种基于匈牙利的线性规划（HLP）方法来解决MMBM在多项式时间。上层优化问题采用进化多目标优化算法求解，并引入贪婪的局部搜索算子，充分利用问题实例中的领域知识和信息，提高了算法的效率.数值实验结果表明，所提出的技术的变化容忍逻辑映射问题的有效性和效率。
Nanoscale crossbar architectures have received steadily growing interests as a result of their great potential to be main building blocks in nanoelectronic circuits. However, due to the extremely small size of nanodevices and the bottom-up self-assembly nanofabrication process, considerable process variation will be an inherent vice for crossbar nanoarchitectures. In this paper, the variation tolerant logical mapping problem is treated as a bilevel multiobjective optimization problem. Since variation mapping is an NP-complete problem, a hybrid multiobjective evolutionary algorithm is designed to solve the problem adhering to a bilevel optimization framework. The lower level optimization problem, most frequently tackled, is modeled as the min–max-weight and min-weight-gap bipartite matching (MMBM) problem, and a Hungarian-based linear programming (HLP) method is proposed to solve MMBM in polynomial time. The upper level optimization problem is solved by evolutionary multiobjective optimization algorithms, where a greedy reassignment local search operator, capable of exploiting the domain knowledge and information from problem instances, is introduced to improve the efficiency of the algorithm. The numerical experiment results show the effectiveness and efficiency of proposed techniques for the variation tolerant logical mapping problem.