Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

University of New Brunswick

$20,000.00

Heuristic Minimization Techniques for Reversible Logic Synthesis

FY 2019-20

Summary
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.
Program
Discovery Grants Program - Individual
Location
New Brunswick, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
RGPIN-2014-06455
Name nom
Dueck, Gerhard
Department département
Office of Research Services (ORS)
Organization id
75
Institution établissement
University of New Brunswick
Province en
New Brunswick
Province fr
Nouveau-Brunswick
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2019
Competition year année de concours
2014
Award amount
20000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR LA DÉCOUVERTE
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
802
Area of application group en
Information and communication services
Area of application group fr
Services d'information et de télécommunications
Area of application en
Information systems and technology
Area of application fr
Systèmes d'information et technologie de l'information
Research subject code
2701
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Computer hardware
Research subject fr
Matériel informatique
Installment
inst:5 - 5
Partie
5
Nb partie
5
Application title
Heuristic Minimization Techniques for Reversible Logic Synthesis
Keyword
NSERC
Application summary
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.
University of New Brunswick - $20,000 Grant (2019-20) | Canada Spends