Heuristic Minimization Techniques for Reversible Logic Synthesis

可逆逻辑综合的启发式最小化技术

• 批准号: RGPIN-2014-06455
• 负责人: Dueck, Gerhard
• 金额: $ 1.46万
• 依托单位: University of New Brunswick
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2019
• 资助国家: 加拿大
• 起止时间: 2019-01-01 至 2020-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=677173
• 关键词: Heuristic; Minimization; Techniques; Reversible; Logic

Heat dissipation is an increasing concern in circuit design. Some of the energy loss is due to the irreversibility of the computations. If computations were reversible, energy loss due to the loss of information would not occur. Thus reversible logic has emerged as an active area of research with applications in quantum computing, low power devices, and nanotechnologies. Reversible functions can be represented as Toffoli networks. Different cost metrics have been suggested for such networks. Clearly, the implementation cost of a function depends on the target technology. CMOS implementations will have different metrics than quantum realizations. **The problem can be formalized as follows: given a reversible function and a cost metric, find a realization with low cost. Due to the complexity of the problem, exact solutions are only possible for functions with few variables. Therefore heuristics are required. Reversible logic synthesis can be accomplished in a two-step process. First, find any realization for the given function-this may be far from minimal. Second, apply iterative transformations to reduce the cost. Transformations can be given in the form of rewriting rules (also known as templates.) Recently, some important advances have been made in the understanding and application of templates. One objective of the proposed research is to find efficient ways of applying templates. The number of potential templates is very large. It has been shown that some templates are applied more often, thus contributing significantly to the cost reduction. On the other hand, the application of some templates has never been observed while optimizing benchmark functions. This is due to the fact that the networks to be optimized are obtained in such a way that certain patterns never occur. A classification of templates will help to apply templates more efficiently. **Developments in quantum computing may yield new ways of implementation. Reversible functions will then be mapped to such building blocks. Elementary gates will have different associated cost. Existing methods will be adapted to such evolving structures. For example, in the recent past the quantum T-gate has been proposed as a building block in fault tolerant computing. However, the cost of the T-gate is on the order of 100 times more costly than other gates. Thus, the reduction of T-gates becomes the primary objective. Such developments will be closely followed and new synthesis algorithms developed or existing ones will be adapted.

散热越来越受到电路设计的关注。一些能量损失是由于计算的不可逆性造成的。如果计算是可逆的，则不会发生由于信息丢失而导致的能量损失。因此，可逆逻辑已成为一个活跃的研究领域，应用于量子计算、低功耗器件和纳米技术。可逆函数可以表示为 Toffoli 网络。针对此类网络提出了不同的成本指标。显然，功能的实​​现成本取决于目标技术。 CMOS 实现将具有与量子实现不同的指标。 **问题可以形式化如下：给定可逆函数和成本度量，找到低成本的实现。由于问题的复杂性，只有很少变量的函数才有可能得到精确的解。因此需要启发式方法。可逆逻辑综合可以通过两步过程完成。首先，找到给定函数的任何实现——这可能远远不是最小的。其次，应用迭代变换来降低成本。转换可以以重写规则（也称为模板）的形式给出。最近，在模板的理解和应用方面取得了一些重要进展。拟议研究的目标之一是找到应用模板的有效方法。潜在模板的数量非常大。事实证明，某些模板的应用更为频繁，从而大大有助于降低成本。另一方面，在优化基准函数时从未观察到某些模板的应用。这是因为要优化的网络是通过某些模式永远不会出现的方式获得的。对模板进行分类将有助于更有效地应用模板。 **量子计算的发展可能会产生新的实现方式。然后可逆函数将被映射到这样的构建块。基本门将有不同的相关成本。现有方法将适应这种不断发展的结构。例如，最近，量子 T 门被提议作为容错计算的构建块。然而，T型门的成本比其他门高出100倍左右。因此，减少T-gate成为首要目标。我们将密切关注此类进展，并对开发的新合成算法或现有算法进行调整。