Heuristic Minimization Techniques for Reversible Logic Synthesis

点击翻译按钮获取中文摘要

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.