Data structures and algorithms for simplifying reversible circuits

ABSTRACT

Reversible logic is motivated by low-power design, quantum circuits, and nanotechnology. We develop a compact representation of small reversible circuits to generate and store optimal circuits for all 40,320 three-input reversible functions, and millions of four-input circuits. This allows implementing a function optimally in constant time for use in the peephole optimization of larger circuits produced by existing techniques, and guarantees that every three-bit subcircuit is optimal. To generate subcircuits, we use a graph-based data structure and algorithms for circuit restructuring. Finally, we demonstrate a suboptimal circuit for which peephole optimization fails.

REFERENCES

• 1: Abhinav Agrawal , Niraj K. Jha, Synthesis of Reversible Logic, Proceedings of the conference on Design, automation and test in Europe, p.21384, February 16-20, 2004
• 2: Barenco, A., Bennett, C. H., Cleve, R., Di Vincenzo, D. P., Margolus, N., Shor, P., Sleator, T., Smolin, J., and Weinfurter, H. 1995. Elementary gates for quantum computation. Phys. Rev. A 52, 3457--3467.
• 3: Bennett, C. 1973. Logical reversibility of computation. IBM J. Res. Develop. 17, 525--532.
• 4: Jason Cong , Michail Romesis , Min Xie, Optimality, scalability and stability study of partitioning and placement algorithms, Proceedings of the 2003 international symposium on Physical design, April 06-09, 2003, Monterey, CA, USA [doi>10.1145/640000.640021]
• 5: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 6: Joel Darnauer , Wayne Wei-Ming Dai, A method for generating random circuits and its application to routability measurement, Proceedings of the 1996 ACM fourth international symposium on Field-programmable gate arrays, p.66-72, February 11-13, 1996, Monterey, California, United States [doi>10.1145/228370.228380]
• 7: John A. Darringer , Daniel Brand , John V. Gerbi , William H. Joyner, Jr. , Louise Trevillyan, LSS: a system for production logic synthesis, IBM Journal of Research and Development, v.28 n.5, p.537-545, September 1984
• 8: Bart Desoete , Alexis De Vos, A reversible carry-look-ahead adder using control gates, Integration, the VLSI Journal, v.33 n.1, p.89-104, December 2002 [doi>10.1016/S0167-9260(02)00051-2]
• 9: de Vos, A., Raa, B., and Storme, L. 2002. Generating the group of reversible logic gates. J. Phys. A 35, 7063--7078.
• 10: Feynman, R. 1985. Quantum mechanical computers. Optics News, 11, 11--20.
• 11: Lov K. Grover, A framework for fast quantum mechanical algorithms, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.53-62, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276712]
• 12: Kazuo Iwama , Yahiko Kambayashi , Shigeru Yamashita, Transformation rules for designing CNOT-based quantum circuits, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA [doi>10.1145/513918.514026]
• 13: 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]
• 14: MacWilliams, F. J. and Sloane, N. J. A. 1977. The Theory of Error-Correcting Codes. North-Holland, Amsterdam.
• 15: Dmitri Maslov , GerhardW. Dueck , D. Michael Miller, Simplification of Toffoli Networks via Templates, Proceedings of the 16th symposium on Integrated circuits and systems design, p.53, September 08-11, 2003
• 16: Dmitri Maslov , Gerhard W. Dueck , D. Michael Miller, Fredkin/Toffoli Templates for Reversible Logic Synthesis, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.256, November 09-13, 2003 [doi>10.1109/ICCAD.2003.73]
• 17: Architectural Enhancements for Fast Subword Permutations with Repetitions in Cryptographic Applications, Proceedings of the International Conference on Computer Design: VLSI in Computers & Processors, p.453, September 23-26, 2001
• 18: W. M. McKeeman, Peephole optimization, Communications of the ACM, v.8 n.7, p.443-444, July 1965 [doi>10.1145/364995.365000]
• 19: D. Michael Miller , Dmitri Maslov , Gerhard W. Dueck, A transformation based algorithm for reversible logic synthesis, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775915]
• 20: Quantum computation and quantum information, Cambridge University Press, New York, NY, 2000
• 21: Shende, V. V., Prasad, A. K., Markov, I. L., and Hayes, J. P. 2003. Synthesis of reversible logic circuits. IEEE Trans. Comput. Aided Des., 710--722.
• 22: Dirk Stroobandt , Peter Verplaetse , Jan van Campenhout, Towards synthetic benchmark circuits for evaluating timing-driven CAD tools, Proceedings of the 1999 international symposium on Physical design, p.60-66, April 12-14, 1999, Monterey, California, United States [doi>10.1145/299996.300023]
• 23: Toffoli, T. 1980. Reversible computing. Tech. Memo MIT/LCS/TM-151, MIT Laboratory for Computer Science.
• 24: Younis, S. and Knight, T. 1994. Asymptotically zero energy split-level charge recovery logic. In Proceedings of the Workshop on Low Power Design.
• 25: Zhirnov, V. V., Cavin, R. K., Hutchby, J. A., and Bourianoff, G. I. 2003. Limits to binary logic switch scaling---A Gedanken model. In Proc. IEEE 91, 1934--1939.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.1 Design Styles

General Terms:
Algorithms

Keywords:
Circuit simplification, circuit libraries, optimal subcircuit