A novel Toffoli network synthesis algorithm for reversible logic

ABSTRACT

Reversible logic studies have promising potential on energy lossless circuit design, quantum computation, nanotechnology, etc. Reversible logic features a one-to-one input output correspondence which makes the logic synthesis for reversible functions differs greatly from traditional Boolean functions. Exact synthesis methods can provide optimal solutions in terms of the total number of reversible gates in the synthesis results. Unfortunately, they may suffer from long computation time, due to the fact that the search space is likely to grow exponentially as the circuit size increases. Therefore, in this paper, we propose an efficient synthesis heuristic which provides high quality synthesis results of Toffoli network in more reasonable computation time. We use a weighted, directed graph for reversible function representation and complexity measurement. The proposed algorithm maximally decreases function complexity during synthesis steps. It has the ability to climb out of local minimums and guarantees algorithm convergence. The experimental results show that our algorithm can achieve optimal or very close to optimal solutions with computation time several orders of magnitude less than the exact methods. Compared with other heuristics, our method demonstrates superior performance in terms of reversible gate count as well as computation time.

REFERENCES

• 1: S. G. Younis and T. F. Knight, "Asymptotically zero energy split-level charge recovery logic," in Proc. Wkshp. Low Power Design, 1994, pp. 177--182.
• 2: Quantum computation and quantum information, Cambridge University Press, New York, NY, 2000
• 3: R. C. Merkle, "Two types of mechanical reversible logic," Nanotechnology, vol. 4, no. 2, pp. 114--131, 1993.
• 4: R. Landauer, "Irreversibility and heat generation in the computing process," IBM J. Research & Development, vol. 5, no. 3, pp. 183--191, July 1961.
• 5: C. Bennett, "Logical reversibility of computation," IBM J. Research & Development, vol. 17, no. 6, pp. 525--532, Nov. 1973.
• 6: Robert Wille , Daniel Große, Fast exact Toffoli network synthesis of reversible logic, Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design, November 05-08, 2007, San Jose, California
• 7: Robert Wille , Hoang M. Le , Gerhard W. Dueck , Daniel Große, Quantified synthesis of reversible logic, Proceedings of the conference on Design, automation and test in Europe, March 10-14, 2008, Munich, Germany [doi>10.1145/1403375.1403620]
• 8: Vivek V. Shende , Aditya K. Prasad , Igor L. Markov , John P. Hayes, Reversible logic circuit synthesis, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.353-360, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774625]
• 9: William N. N. Hung , Xiaoyu Song , Guowu Yang , Jin Yang , Marek Perkowski, Quantum logic synthesis by symbolic reachability analysis, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996790]
• 10: D. M. Miller and G. W. Dueck, "Spectral techniques for reversible logic synthesis," in Proc. Symp. Representations & Methodology of Future Computing Technologies, Mar. 2003, pp. 56--62.
• 11: Pawel Kerntopf, A new heuristic algorithm for reversible logic synthesis, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996789]
• 12: D. Maslov, G. W. Dueck, and D. M. Miller, "Toffoli network synthesis with templates," IEEE Trans. Computer-Aided Design of Integrated Circuits & Systems, vol. 24, no. 6, pp. 807--817, June 2005.
• 13: P. Gupta, A. Agrawal, and N. K. Jha, "An algorithm for synthesis of reversible logic circuits," IEEE Trans. Computer-Aided Design of Integrated Circuits & Systems, vol. 25, no. 11, pp. 2317--2330, Nov. 2006.
• 14: Mehdi Saeedi , Mehdi Sedighi , Morteza Saheb Zamani, A novel synthesis algorithm for reversible circuits, Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design, November 05-08, 2007, San Jose, California
• 15: T. Toffoli, "Reversible computing," Tech. Rep. MIT/LCS/TM-151, MIT Lab for Computer Science, 1980.
• 16: D. Maslov, Reversible logic synthesis benchmarks webpage, http://www.cs.uvic.ca/~dmaslov/.