A fast Binary Decision Diagram (BDD)-based reversible logic optimization engine driven by recent meta-heuristic reordering algorithms. (August 2021)

• Record Type: Journal Article
• Authors: Abdalhaq, Baker; Awad, Ahmed; Hawash, Amjad
• Is Part Of: Microelectronics and reliability. Volume 123(2021)
• Publication Date: 2021-08
• Subjects: Quantum Cost (QC) -- Binary Decision Diagram (BDD) -- Swarm -- Genetic Algorithm (GA) -- Crossover -- Mutation; Electronic apparatus and appliances -- Reliability -- Periodicals; Miniature electronic equipment -- Periodicals; Appareils électroniques -- Fiabilité -- Périodiques; Équipement électronique miniaturisé -- Périodiques; Electronic apparatus and appliances -- Reliability; Miniature electronic equipment; Periodicals; 621.3815
• DOI: 10.1016/j.microrel.2021.114168
• Languages: English
• ISSNs: 0026-2714

Abstract

Abstract: Reversible logic has recently gained a remarkable interest due to its information lossless property, which minimizes power dissipation in the circuit. Furthermore, with their natural reversibility, quantum computations can profit from the advances in reversible logic synthesis, as the latter can be easily applied to map practical logic designs to quantum architectures. Although numerous algorithms have been proposed to synthesize reversible circuits with low cost, the increasing demands for scalable synthesis techniques represent a serious barrier in the synthesis process. Furthermore, the enhanced reliability of the synthesized circuits comes at the cost of redundancy in the quantum architecture of the gates composing that circuit, which increases the overall manufacturing cost for fault-tolerant circuits. Binary Decision Diagram (BDD) based synthesis has demonstrated a great evidence in reversible logic synthesis, due to its scalability in synthesizing complex circuits within a reasonable time. However, the cost of the synthesized circuit is roughly correlated to its corresponding BDD size. In this paper, we propose a fast reversible circuit synthesis methodology driven by a BDD-reordering optimization engine implemented by recent meta-heuristic optimization algorithms. Experimental results show that Genetic Algorithm (GA) based reordering supported with Alternating Crossover (AX) and swap mutation outperforms others as it is the least destructive for low-cost BDDs during the optimization recipe. Highlights: We propose a fast BDD-based synthesis algorithm for reversible circuits driven by a BDD-reordering optimization engine under the guidance of BDD size as an evaluation metric in the proposed algorithm. We integrate recent swarm optimization algorithms into the BDD-reordering optimizer. We integrate Genetic Algorithm (GA) supported with recent effective crossover/mutation operators into the BDD-reordering optimization engine We evaluate the different algorithms when integrated with our proposed optimization engine in terms of the size of the resultant BDD. This evaluation has been done on the public benchmarks.