A Comparative Analysis of Binary Decision Diagram Reordering Algorithms for Reversible Circuit Synthesis
Publication Type
Conference abstract/paper published in a peer review journal
Authors

As billions of transistors are being placed on a few square millimeters of silicon, power dissipation is becoming a more crucial factor to be tackled for high performance computing. Reversible circuit synthesis has been considered as a promising direction for low power design due to its information lossless behavior. In addition, it forms the basis for quantum computing. However, synthesis of reversible circuits cannot be achieved with the classical approaches for irreversible logic due to the additional imposed constraints, consequently, neither fan-out nor feedback are allowed. Binary Decision Diagrams (BDDs) have been proposed as a compact data structure to represent a boolean function. They have been exploited to synthesize reversible circuits through proper mapping of each BDD's node into a cascade of reversible Toffoli gates. Nevertheless, reordering of BDD's nodes before circuit synthesis significantly impacts the overall cost of the synthesized circuit. In this paper, we present a comparative study for BDD reordering algorithms in terms of the cost of the generated reversible circuit. The studied algorithms include greedy, dynamic programming, and heuristic based approaches. The cost metric includes the number of lines, gate count, quantum cost, and computation time. We conclude with a proposal for a new framework for reversible logic synthesis.

 

Journal
Title
2018 SYMPOSIUM SERIES ON COMPUTATIONAL INTELLIGENCE
Publisher
SSCI 2018
Publisher Country
India
Publication Type
Prtinted only
Volume
--
Year
--
Pages
--