Study On Reversible Logic Circuit Synthesis Based On Evolutionary Methods

The heat dissipation of CMOS chips limits their integration level,and the heat dissipation is mainly caused by the irreversible operation of traditional logic gates.To avoid the heat dissipation,circuit must be constructed by reversible gates.Therefore,the applications of reversible circuit are more pervasive in reversible computing,low energy CMOS design,optical calculation,quantum and DNA computing.Reversible logic circuit synthesis has become a flourishing research area in the recent years.Existing reversible logic circuit(RLC)synthesis methods are often classified into three categories: deterministic approaches,heuristic techniques and evolutionary ones.Some deterministic approaches can find a solution efficiently even for a large scale problem,but the results often need to be post-optimized further.However the post-optimization needs repeated iteration and play a limited role.Other deterministic algorithms often use exhaustive search to find an optimum solution.They are often characterized by the high computational cost and cannot solve the problems with more than 4-bit.The heuristic algorithms employ the greedy heuristic strategy and rapidly prune the search space by the heuristic information.They are applicable to small and medium scale reversible problems and the post-optimization is also required.Evolutionary algorithms are already used in reversible circuit synthesis owing to its global search ability.However,compared to the first two classes,only small-scale and simple functions were tested and no superior results were obtained.This paper aims at research on RLC synthesis using evolutionary algorithm and focuses on solving small and medium-scale reversible problems for which the exhaustive algorithms cannot work under current computer system.We try to improve the quality of solutions through analyzing and attacking the key issues in evolutionary RLC synthesis.The problem is formulated as a cost-minimization problem with equality constraint,where the constraint is defined as the validity of the circuit,and the objective is the circuit cost.The bloat control of variable-length encoding,equality constraint solving,diversity conservation strategy and hybrid evolutionary method are mainly studied,considering the characteristics of RLC problems,such as the large and multimodal search space,the unknown length of the optimum and high epistasis.Some fruitful results have been achieved and summarized as follow.1)The basic variable-length evolutionary algorithm is formulated.The new constraint violation(CV)evaluation is obtained through the different terms between the Positive-Polar Reed-Muller(PPRM)expression of the reversible function and that of identity function.It is different from the commonly used CV evaluation by the distance of matrix trace and it avoids the computationally expensive matrix multiplication and Kronecker product.The maximum length and the initial length of the circuit are obtained by the number of factors from the PPRM of a reversible function.Maximum size limit and nondestructive crossover operator are used to ensure the increasing growth of the length of chromosomes and avoid chromosome bloat.2)Two equality constraint solving methods are designed.The first one employs the mechanism of the separation of objectives and constraints to solve equality constraints.It emphasis the comparison of infeasible ones and makes a better balance between the decreasing of the constraint violation and the increasing of the objective value through introducing the parsimony pressure,which consequently effectively avoids chromosome bloat.The second one employs preference-based multi-objective optimization to solve equality constraint.Usually,the decreasing of CV often means the increasing of the objective value in RLC problem.The reference point is determined dynamically according to the distribution of solutions.A new crowding comparative operator is fabricated to guide the search toward the CV decreasing direction.3)The diversity maintaining mechanism for variable length evolution is studied.We borrowed and improved the species detection and seeds preservation mechanism.The distance between chromosomes of different length is given.The feasible ratio and the solution quality are improved through the species deletion and updating method.4)A hybrid algorithm is designed which combines evolutionary algorithms and heuristic methods.The preferable gate library is constructed through subtracting factors from the PPRM of a chromosome and is used to update the individual when evolutionary stagnation.It can speed up the convergence speed and improve the feasible ratio.5)An evolutionary algorithm for logic synthesis with memritor-based implication gate is proposed by combining the research results on RLC synthesis with the characteristic of the problem.Besides the framework of VLEA_RLC,the algorithm uses a new chromosome encoding and fitness evaluation method,and a novel local search method to improve the feasible ratio.The experiments show the validity of the algorithm.The key problems involved in RLC synthesis were studied in this paper.Experimental results show that the designs are effective for small and medium reversible functions,and the expectative purpose of design is achieved.The ideas from VLEA_RLC can be generated to other logic synthesis problems with the variable encoding.