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