A Comparative Analysis of Binary Decision Diagram Reordering Algorithms for Reversible Circuit Synthesis
Ahmed Awad, Baker K. Abdalhaq, Amjad Hawash, Douglas Johnson · 2018
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, and quantum cost. Experimental results show that meta heuristic-based BDD reordering algorithms outperform other algorithms in terms of the overall synthesized circuit cost with slightly additional runtime. Thereafter, we conclude with a proposal for a new framework for reversible logic synthesis.