Heuristic Minimization Techniques for Reversible Logic Synthesis

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

• 批准号: RGPIN-2014-06455
• 负责人: Dueck, Gerhard
• 金额: $ 1.46万
• 依托单位: University of New Brunswick
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2017
• 资助国家: 加拿大
• 起止时间: 2017-01-01 至 2018-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=634407
• 关键词: 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-Gates的减少成为主要目标。此类发展将受到仔细遵循，并开发了新的综合算法或现有的算法将得到调整。