基于常规逻辑设计理论与技术移植的较大规模可逆逻辑电路设计方法

Reversible logic circuits (RLCs) can avoid loss of information and consequent power consumption and heat generation. RLCs also coincide with implementations of quantum computing perfectly, which are inherently reversible. Thus, RLCs play an important role, i.e., basis and prerequisite, in research, development and realization of ultra-low-power ICs and quantum computers. But unfortunately, theory, methods and tools for RLCs design are so far either weak or even unborn. This project seeks to significant improvement on RLCs design capability, mainly by transplanting and using EDA techniques. Towards a rather comprehensive and systematic investigation, the research plan was drafted regarding both deferent circuit-level such as component-level, gate-level and system-level, and each of design steps including synthesis, optimization, validation, and debugging. The main research topics are as follows: transplanting and improving the Quine-McCluskey algorithm and the Espresso algorithm for simplications of RLCs; transformation-based optimization methods for minimization of circuit quantum cost; evolutionary design methods for reversible logic gates; parallel implement of the above algorithm based on the CUDA parallel computing technique; approaches based on EDA for high-level expression of design specifications, and that for verification and debugging of RLCs designed. Moreover, some large-scale benmark RLCs, e.g., an 8-bit reversible ALU, are to be designed by using the above methods, mainly for the sake of validation and demonstration of their performances. This project promises effective methods for optimal design of large-scale reversible logic circuits, thus contributing to development of the relevant theory, methods and techniques, and promoting the emergence and development of quantum design automation.

可逆逻辑电路(Reversible Logic Circuits)既可根绝源于信息损失的能耗和发热，又是量子计算的内在实现方式，因而是研发和实现超低功耗IC和量子计算机的基础和前提。但有关的设计理论、方法和工具还很稚嫩甚至空白。本项目寻求通过移植常规逻辑设计理论和技术，显著提高可逆逻辑设计能力。将针对元件级、门级、系统级等层次和综合、优化、验证、调试等步骤，较全面、系统地开展研究，包括：Quine-McCluskey算法和Espresso算法的移植和改进；基于变换的电路量子代价优化方法；可逆逻辑门的进化设计方法；上述算法的CUDA并行化实现；基于EDA技术的设计规格表达和设计结果验证、调试方法；并通过16位可逆ALU等较大规模功能模块的优化设计，检验和展示上述方法的性能。预期可获得适用于较大规模可逆逻辑电路的优化设计方法，丰富和发展有关的理论、方法和技术，并促进量子设计自动化的产生和发展。

可逆逻辑电路(Reversible Logic Circuit)泛指以硬件a/o软件实现的可逆操作（运算）序列，因其可避免信息损失和相应的能耗与发热，被视为降低集成电路功耗和延续相关技术、产业发展的必由之路；它还是内在可逆的量子计算（机）的逻辑表达形式和研究、实现基础，因而已成为国际性的研究前沿和热点。因受可逆性约束等的限制，其设计和实现等不再适用现行的常规（非可逆）逻辑电路理论和技术，已有研究普遍另起炉灶、从头开始，因而进展缓慢、遭遇严重瓶颈。但我们研究发现，尽管可逆逻辑和常规逻辑之间存在着显著差异，逻辑代数仍是它们共同的理论基础和连接纽带，故将常规逻辑电路设计的理论和技术（部分）移植、复用于可逆逻辑，不但在理论上可行，而且十分必要和迫切。本项目即主要研究通过移植常规逻辑设计的理论与技术，实现较大规模可逆逻辑优化设计的有效途径。具体针对元件级、门级、系统级等不同逻辑层次和综合、优化、验证、调试等各个设计步骤，较全面、系统地开展了理论和实验研究，主要包括：Quine-McCluskey算法和Espresso算法的移植和改进；基于变换的电路量子代价优化方法；基于遗传算法（GA）、差分进化算法（DE）和基因表达式编程（GEP、MGEP）的可逆逻辑（门）进化设计方法；上述算法基于CUDA技术的（部分）并行化实现；基于EDA技术平台的可逆逻辑设计规格表达和设计结果验证、调试方法，特别是基于原理图和硬件描述语言（Verilog）的设计、优化方法；时序、多值可逆逻辑电路的初步研究；并通过对于较大规模、较复杂功能模块的优化设计，检验和展示上述方法的性能及本项目的研究成果。本项研究获得了适用于较大规模可逆逻辑电路的多层次设计优化方法和设计实验平台（原型），以及多种（新型）可逆逻辑门和16位可逆ALU等较大规模功能模块的优化设计结果，从而丰富和发展了可逆逻辑设计的理论、方法和技术，并为其未来发展开辟了新的有效途径；相信对于量子设计自动化（QDA）以及超低功耗IC设计、量子计算（机）等相关领域和方向的发展也有一定的促进作用。