A hybrid evolutionary algorithm for multiobjective variation tolerant logic mapping on nanoscale crossbar architectures

• The problem of variation tolerant logical mapping on nanoscale crossbar architectures is modeled as a bilevel multiobjective optimization problem. A hybrid multiobjective evolutionary algorithm is designed to solve the problem in a bilevel optimization framework.
• The lower level problem is modeled as a MMBM problem, and a Hungarian-based Linear Programming (HLP) method is proposed, which can 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 leveraging the domain knowledge and information from problem instances, is introduced to improve the efficiency of the algorithm.

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.

Framework of the hybrid algorithm. The input mapping vector is encoded as chromosome in the upper level multiobjective evolutionary algorithm. Fitness of each individual in the upper level is calculated via solving lower lever problem modeled as MMBM and calling HLP. The two level optimization problems share the same two optimization objectives. Local search is included in the upper level evolutionary algorithm with no extra fitness calculation cost.Figure optionsDownload as PowerPoint slide