Heuristic Minimization Techniques for Reversible Logic Synthesis

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

• 批准号: RGPIN-2014-06455
• 负责人: Dueck, Gerhard
• 金额: $ 1.46万
• 依托单位: University of New Brunswick
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2014
• 资助国家: 加拿大
• 起止时间: 2014-01-01 至 2015-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=567816
• 关键词: 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门成为首要目标。这些发展将密切关注和新的合成算法开发或现有的将适应。