Reversible Logic Synthesis Method Based On Genetic Algorithm And Its Cuda-Dased Parallel Implementation

With the increase and enhance of integration scale, energy issues of integrated circuits have become increasingly prominent, which hinder the promotion of the impact of integration. Nowadays the energy consumption of integrated circuits is mainly from the irreversible operation of calculation process. According to the theorem of Landauer, reversible logic circuit can eradicate the power consumption and heat of information loss. It seems that the information loss is minor, but it can’t be eliminated by improving the semiconductor technology, and become more and more significant with the increasing density of integrated circuits.Reversible logic synthesis is the use of the given reversible logic gates, according to the network without fan in and out, no feedback, to achieve the appropriate reversible logic circuits and makes the quantum cost as small as possible. In order to reduce quantum cost, reversible logic optimization is appeared, which restructure, replace the circuit, without changing its function, to reduce the number of logic gate and the costs. Some methods combine the synthesis and optimization and have become a mainstream integrated approach. Reversible logic synthesis method based on genetic algorithm is such an algorithm.GPU parallel computing architecture is particularly suitable for handling the problem that the algorithm has a high strength and can be expressed as parallel computing. Meanwhile, in order to reduce the development cycle and the difficulty, NVIDIA extend the C language and introduce CUDA programming model to support GPU general computing. CUDA programming model makes parallelize programs development simple, and provides a convenient development platform for general-purpose GPU.In this thesis, we use reversible logic gate to set up model for genetic algorithm and search the reversible logic circuits. In order to apply it to quantum reversible logic circuits, we improve the genetic algorithm and combined it with CUDA parallel computing, which greatly improve the searching speed of genetic algorithm, improve the efficiency of genetic algorithm, avoid the algorithm trapped in local optimal solutions, and able to quickly search the quantum reversible logic circuits with the minimum cost. Tested by four, six and seven input Toffoli gate, the running speed and experimental results are very significant. As long as make some corresponding change for the truth table, it can be applied to other reversible logic gates library, which has wide application scope and broad prospects.