A Comparative Analysis of Binary Decision Diagram Reordering Algorithms for Reversible Circuit Synthesis
Publication Type
Conference Paper

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 fanout
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.
Index Terms—reversible circuit, binary decision diagram, sifting
algorithm, quantum cost, transistor cost, gate count.

Conference Title
Conference Country
Conference Date
Nov. 18, 2018 - Nov. 21, 2018
Conference Sponsor
IEEE Computational Intelligence Society
Additional Info
Conference Website