On Parallel Design Of Q-M Algorithm And Its CUDA-based Implementation For Reversible Logic Synthesis

Reversible logic is a new research area, which has important theoretical significance and application prospects in research, development and realization of ultra-low-power ICs and quantum computers. Currently, there are many problems to be solved in the reversible logic synthesis, optimization, implementation, application, etc, and it is fundamental to significantly improve the scale and optimization degree of reversible logic synthesis algorithm. Transplantation and improvement of mature conventional(irreversible) logic synthesis, optimization algorithms, such as Quine-McCluskey algorithm(referred to as Q-M algorithm), is probably one of the effective ways to proceed the problems.Using parallel computing technology can also ease or solve the problems. The GPU(Graphic Processing Units)has many advantages in architecture processing. It is more suitable for large scale parallel computing algorithm acceleration, thus, was studied widely nowadays nationally and globally. CUDA (Compute Unified Device Architecture) based on new graphics card is the most regular GPU parallel computing architecture used in the development and application.This thesis aimes to significantly improve the scale and optimization degree of the reversible logic synthesis by transplanting, improving and paralleling Q-M algorithm and CUDA-based programming. Specific contents of the paper are as follows:Firstly, the thesis briefly introduces the principle and key points of the Q-M algorithm, advances, analyzes and demonstrates the basic idea and concrete methods of the Q-M algorithm transplantation and improvement according to the characteristics of the reversible logic, the feasibility and the effectiveness of the preceding transplantation, improvement are preliminarily validated by the design examples.Secondly, the thesis shows the background knowledge and the key development points of CUDA, it proposes the parallel implementation idea and methods of Q-M transplantation algorithm based on CUDA, and designs the concrete programming. It is hoped that the effort of this thesis can provide reference in transplantation, improvement, parallelization programming and implementation of conventional algorithm for reversible logic synthesis and optimization.