Your browser does not support JavaScript!
http://iet.metastore.ingenta.com
1887

access icon free Challenges and advances in Toffoli network optimisation

© The Institution of Engineering and Technology
Received 26/03/2013, Accepted 02/08/2013, Revised 24/07/2013, Published 17/09/2013

This study gives a brief overview of the current trends in reversible logic synthesis with emphasis on template matching. The basic building block for reversible circuits considered here is the multiple-control Toffoli gate. Some approaches to synthesis are reviewed and the challenges are explained. Since many practical functions are not reversible, they must be embedded into reversible ones, if they are to be implemented using reversible logic. The complexity of such embeddings is expounded. A two phase synthesis is described where particular attention is devoted to the optimisation phase via template matching. Insights into the properties of the templates, have led to algorithms that aid the generation of templates. Until recently, the application of templates has been guided by different heuristics. A review of an exact template matching algorithm with a discussion of the implications of such an algorithm is given. Exact matching affects both the generation as well as the application of templates. Results from a prototype implementation are encouraging.

Inspec keywords: logic design; pattern matching; circuit optimisation; logic gates

Other keywords: multiple-control Toffoli gate; two phase synthesis; exact template matching algorithm; reversible logic; reversible logic synthesis; reversible circuits; template generation; Toffoli network optimisation

Subjects: Logic elements; Digital circuit design, modelling and testing; Logic circuits; Logic design methods; Logic and switching circuits

References

    1. 1)
    2. 2)
      • 5. Toffoli, T.: ‘Reversible computing’. Tech memo MIT/LCS/TM-151, MIT Lab for Comp Sci.1980.
    3. 3)
    4. 4)
    5. 5)
    6. 6)
    7. 7)
    8. 8)
    9. 9)
    10. 10)
    11. 11)
    12. 12)
    13. 13)
    14. 14)
    15. 15)
    16. 16)
    17. 17)
    18. 18)
    19. 19)
    20. 20)
    21. 21)
      • 47. Rahman, M.M., Dueck, G.W., Horton, J.: ‘Exact template matching using graphs’. Technical Report TR13-224, Faculty of Computer Science, University of New Brunswick, 2013.
    22. 22)
      • 37. Patel, K.N., Markov, I.L., Hayes, J.P.: ‘Optimal synthesis of linear reversible circuits’, Quantum Inf. Comput., 2008, 8, (3), pp. 282–294.
    23. 23)
      • 20. Gupta, P., Agrawal, A., Jha, N.K.: ‘An algorithm for synthesis of reversible logic circuits’, IEEE Trans. CAD Integr. Circuits Syst., 2006, 25, (11), pp. 2317–2330 (doi: 10.1109/TCAD.2006.871622).
    24. 24)
      • 21. Wille, R., Drechsler, R.: ‘BDD-based synthesis of reversible logic for large functions’. DAC, 2009, pp. 270–275.
    25. 25)
      • 3. Bennett, C.H.: ‘Logical reversibility of computation’, IBM J. Res. Dev., 1973, 17, (6), pp. 525–532 (doi: 10.1147/rd.176.0525).
    26. 26)
      • 38. Maslov, D.: ‘Efficient reversible and quantum implementations of symmetric Boolean functions’, IEE Proc. Circuits Devices Syst., 2006, 153, (5), pp. 467–472 (doi: 10.1049/ip-cds:20045213).
    27. 27)
      • 16. Große, D., Wille, R., Dueck, G.W., Drechsler, R.: ‘Exact multiple control Toffoli network synthesis with SAT techniques’, Trans. Comput. Aided Des., 2009, 28, (5), pp. 703–715 (doi: 10.1109/TCAD.2009.2017215).
    28. 28)
      • 43. Sasanian, Z., Miller, D.M.: ‘Mapping a multiple-control Toffoli gate cascade to an elementary quantum gate circuit’. Proc. Second Workshop on Reversible Computation, 2010, pp. 83–90.
    29. 29)
      • 30. Maslov, D., Dueck, G.W., Miller, D.M.: ‘Synthesis of Fredkin-Toffoli reversible networks’, IEEE Trans. VLSI Syst., 2005, 13, (6), pp. 765–769 (doi: 10.1109/TVLSI.2005.844284).
    30. 30)
      • 19. Fazel, K., Thornton, M.A., Rice, J.E.: ‘ESOP-based Toffoli gate cascade generation’. PACRIM, 2007, pp. 206–209.
    31. 31)
      • 9. Desoete, B., Vos, A.D.: ‘A reversible carry-look-ahead adder using control gates’, Integr. VLSI J., 2002, 33, (1-2), pp. 89–104 (doi: 10.1016/S0167-9260(02)00051-2).
    32. 32)
      • 35. Somenzi, F.: ‘CUDD: CU decision diagram package release 2.3.0’ (University of Colorado at Boulder, 1998).
    33. 33)
      • 4. Berut, A., Arakelyan, A., Petrosyan, A., Ciliberto, S., Dillenschneider, R., Lutz, E.: ‘Experimental verification of Landauer's principle linking information and thermodynamics’, Nature, 2012, 483, (7388), pp. 187–189 (doi: 10.1038/nature10872).
    34. 34)
      • 29. Maslov, D., Dueck, G.W., Miller, D.M.: ‘Toffoli network synthesis with templates’, Trans. Comput. Aided Des., 2005, 24, (6), pp. 807–817 (doi: 10.1109/TCAD.2005.847911).
    35. 35)
      • 22. Miller, D.M., Maslov, D., Dueck, G.W.: ‘A transformation based algorithm for reversible logic synthesis’. Design Automation Conf.2003, pp. 318–323.
    36. 36)
      • 2. Landauer, R.: ‘Irreversibility and heat generation in the computing process’, IBM J. Res., 1961, 5, pp. 183–191 (doi: 10.1147/rd.53.0183).
    37. 37)
      • 12. Maslov, D., Dueck, G.W.: ‘Reversible cascades with minimal garbage’, IEEE Trans. CAD of Integr. Circuits Syst., 2004, 23, (11), pp. 1497–1509 (doi: 10.1109/TCAD.2004.836735).
    38. 38)
      • 46. Scott, N., Dueck, G.W., Maslov, D.: ‘Improving template matching for minimizing reversible Toffoli cascades’. Proc. Seventh Int. Symp. on Representations and Methodology of Future Computing Technologies, 2005, pp. 4–9.
    39. 39)
      • 44. Rahman, M.M., Dueck, G.W.: ‘Properties of quantum templates’. Workshop on Reversible Computation, 2012, pp. 171–183.
    40. 40)
      • 18. Saeedi, M., Zamani, M.S., Sedighi, M., Sasanian, Z.: ‘Reversible circuit synthesis using a cycle-based approach’, JETC, 2010, 6, (4), pp. 13 (doi: 10.1145/1877745.1877747).
    41. 41)
      • 15. Wille, R., Le, H.M., Dueck, G.W., Große, D.: ‘Quantified synthesis of reversible logic’ (DATE, 2008), pp. 1015–1020.
    42. 42)
      • 7. Peres, A.: ‘Reversible logic and quantum computers’, Phys. Rev. A, 1985, 32, pp. 3266–3276 (doi: 10.1103/PhysRevA.32.3266).
    43. 43)
      • 45. Dueck, G.W., Maslov, D.: ‘Generation of multiple control Toffoli network templates’. Int. Workshop on Logic Synthesis, 2007, pp. 39–44.
    44. 44)
      • 14. Große, D., Chen, X., Dueck, G.W., Drechsler, R.: ‘Exact SAT-based Toffoli network synthesis’. Great Lakes Symp. on VLSI, 2007, pp. 96–101.
    45. 45)
      • 31. Mishchenko, A., Perkowski, M.: ‘Logic synthesis of reversible wave cascades’. Int. Workshop on Logic Synthesis, 2002, pp. 197–202.
    46. 46)
      • 25. Yang, G., Song, X., Hung, W.N.N., Perkowski, M.A.: ‘Fast synthesis of exact minimal reversible circuits using group theory’. Asia and South Pacific Design Automation Conf., 2005, pp. 1002–1005.
    47. 47)
      • 6. Fredkin, E., Toffoli, T.: ‘Conservative logic’, Int. J. Theor. Phys, 1982, 21, pp. 219–253 (doi: 10.1007/BF01857727).
    48. 48)
      • 5. Toffoli, T.: ‘Reversible computing’. Tech memo MIT/LCS/TM-151, MIT Lab for Comp Sci.1980.
    49. 49)
      • 1. Dueck, G.W.: ‘Synthesis of Toffoli networks: status and challenges’. Int. Symp. on Electronic System Design, 2012.
    50. 50)
      • 47. Rahman, M.M., Dueck, G.W., Horton, J.: ‘Exact template matching using graphs’. Technical Report TR13-224, Faculty of Computer Science, University of New Brunswick, 2013.
    51. 51)
      • 17. Golubitsky, O., Falconer, S.M., Maslov, D.: ‘Synthesis of the optimal 4-bit reversible circuits’. DAC, 2010, pp. 653–656.
    52. 52)
      • 10. Arabzadeh, M., Saheb Zamani, M., Sedighi, M., Saeedi, M.: ‘Depth-optimized reversible circuit synthesis’, Quantum Inf. Process., 2013, 12, (4), pp. 1677–1699 (doi: 10.1007/s11128-012-0482-8).
    53. 53)
      • 8. Barenco, A., Bennett, C.H., Cleve, R., et al: ‘Elementary gates for quantum computation’, Am. Phys. Soc., 1995, 52, pp. 3457–3467.
    54. 54)
      • 28. Wille, R., Große, D., Teuber, L., Dueck, G.W., Drechsler, R.: ‘RevLib: an online resource for reversible functions and reversible circuits’. ISMVL, 2008, pp. 220–225.
    55. 55)
      • 42. Maslov, D., Dueck, G.W., Miller, D.M.: ‘Techniques for the synthesis of reversible Toffoli networks’, ACM Trans. Design Autom. Electron. Syst., 2007, 12, (4), article no. 42 (doi: 10.1145/1278349.1278355).
    56. 56)
      • 27. Soeken, M., Frehse, S., Wille, R., Drechsler, R.: ‘RevKit: an open source toolkit for the design of reversible circuits’. Workshop on Reversible Computation, 2011, pp. 64–76.
    57. 57)
      • 39. Perkowski, M.A., Chrzanowska-Jeske, M., Mishchenko, A., et al: ‘Regular realization of symmetric functions using reversible logic’. DSD, 2001, pp. 245–253.
    58. 58)
      • 26. Miller, D.M., Dueck, G.W.: ‘Spectral techniques for reversible logic synthesis’. Proc. Sixth Int. Symp. on Representations and Methodology of Future Computing Technologies, 2003.
    59. 59)
      • 13. Shende, V.V., Prasad, A.K., Markov, I.L., Hayes, J.P.: ‘Synthesis of reversible logic circuits’, IEEE Trans. CAD of Integr. Circuits Syst., 2003, 22, (6), pp. 710–722 (doi: 10.1109/TCAD.2003.811448).
    60. 60)
      • 32. Sanaee, Y., Dueck, G.W.: ‘ESOP-Based Toffoli network generation with transformations’. ISMVL, IEEE Computer Society, 2010, pp. 276–281.
    61. 61)
      • 33. Mishchenko, A., Perkowski, M.: ‘Fast Heuristic minimization of exclusive-sums-of-products’. Proc. Fifth Int. Reed-Muller Workshop, 2001, pp. 242–250.
    62. 62)
      • 24. Vos, A.D., Raa, B., Storme, L.: ‘Generating the group of reversible logic gates’, J. Phys. A, Math. General, 2002, 35, (33), p. 7063 (doi: 10.1088/0305-4470/35/33/307).
    63. 63)
      • 34. Bryant, R.E.: ‘Graph-based algorithms for Boolean function manipulation’, IEEE Trans. Comput., 1986, C-35, (8), pp. 677–691 (doi: 10.1109/TC.1986.1676819).
    64. 64)
      • 40. Soeken, M., Wille, R., Dueck, G.W., Drechsler, R.: ‘Window optimization of reversible and quantum circuits’. DDECS, 2010, pp. 341–345.
    65. 65)
      • 23. Storme, L., Vos, A.D., Jacobs, G.: ‘Group theoretical aspects of reversible logic gates’, J. UCS, 1999, 5, (5), pp. 307–321.
    66. 66)
      • 48. Soeken, M., Wille, R., Otterstedt, C., Drechsler, R.: ‘A synthesis flow for sequential reversible circuits’. ISMVL, 2012, pp. 299–304.
    67. 67)
      • 36. Wegener, I.: ‘Branching programs and binary decision diagrams: theory and applications. monographs on discrete mathematics and applications’ (Society for Industrial and Applied Mathematics, 2000).
    68. 68)
      • 11. Miller, D.M., Wille, R., Drechsler, R.: ‘Reducing reversible circuit cost by adding lines’, Mult.-Valued Log. Soft Comput., 2012, 19, (1-3), pp. 185–201.
    69. 69)
      • 41. Wille, R., Offermann, S., Drechsler, R.: ‘SyReC: a programming language for synthesis of reversible circuits’. System pecification and Design Languages. Lect. Notes Electr. Eng., 2012, 106, pp. 207–222 (doi: 10.1007/978-1-4614-1427-8_13).
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-cdt.2013.0055
Loading

Related content

content/journals/10.1049/iet-cdt.2013.0055
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading
Print this page
This is a required field
Please enter a valid email address