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 门成为主要目标，并且将密切关注此类发展，并采用新的合成算法或现有的算法。