World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.
Special Issue on Unconventional ComputingNo Access

PARALLELIZATION OF REVERSIBLE RIPPLE-CARRY ADDERS

    The design of fast arithmetic logic circuits is an important research topic for reversible and quantum computing. A special challenge in this setting is the computation of standard arithmetical functions without the generation of garbage.

    Here, we present a novel parallelization scheme wherein m parallel k-bit reversible ripple-carry adders are combined to form a reversible mk-bit ripple-block carry adder with logic depth for a minimal logic depth , thus improving on the mk-bit ripple-carry adder logic depth . The underlying mechanisms of the parallelization scheme are formally proven correct. We also show designs for garbage-less reversible comparison circuits.

    We compare the circuit costs of the resulting ripple-block carry adder with known optimized reversible ripple-carry adders in measures of circuit delay, width, gate, transistor count, and relative power efficiency, and find that the parallelized adder offers significant speedups at realistic word sizes with modest parallelization overhead.

    References

    • H. B. Axelsen, R. Glück and T. Yokoyama, Reversible machine code and its abstract processor architecture, Computer Science – Theory and Applications. Proceedings4649, LNCS, eds. V. Diekert, M. V. Volkov and A. Voronkov (Springer-Verlag, 2007) pp. 56–69. Google Scholar
    • C. H. Bennett, IBM Journal of Research and Development 17, 525 (1973). Crossref, ISIGoogle Scholar
    • S. A.   Cuccaro et al. , A new quantum ripple-carry addition circuit , 8th Workshop on Quantum information Processing ( 2005 ) ,   arXiv:quant-ph/0410184v1 . Google Scholar
    • A. De Vos, Progress in Quantum Electronics 23(1), 1 (1999). Crossref, ISIGoogle Scholar
    • B. Desoete and A. De Vos, Integration, the VLSI Journal 33(2), 89 (2002). Crossref, ISIGoogle Scholar
    • R. Feynman, Optics News 11, 11 (1985). CrossrefGoogle Scholar
    • E. Fredkin and T. Toffoli, International Journal of Theroretical Physics 21(4), 219 (1982). Crossref, ISIGoogle Scholar
    • R. Landauer, IBM Journal of Research Development 5(3), 183 (1961). Crossref, ISIGoogle Scholar
    • D. Maslov and D. M. Miller, IET Computers & Digital Techniques 1(2), 98 (2007). Crossref, ISIGoogle Scholar
    • G. Moore. Transcript of interview, Intel Developer Forum, 2007. Technical report, Intel Corp . Google Scholar
    • T. Munakata, Communications of the ACM 50(9), 30 (2007). CrossrefGoogle Scholar
    • M. Skoneczny, Y. Van Rentergem and A. De Vos, Reversible fourier transform chip, Proceedings of the 15th International Conference Mixed Design of Integrated Circuits and Systems (2008) pp. 281–286. Google Scholar
    • M. K. Thomsen and H. B. Axelsen, Parallel optimization of a reversible (quantum) ripple-carry adder, Proceedings of the 7th International Conference on Unconventional Computing5204, LNCS, eds. C. S. Caludeet al. (Springer-Verlag, 2008) pp. 229–242. Google Scholar
    • M. K. Thomsen and R. Glück, Journal of Systems Architecture 54(7), 697 (2008). Crossref, ISIGoogle Scholar
    • T. Toffoli, Reversible computing, Proceedings of the 7th Colloquium on Automata, Languages and Programming85, LNCS, eds. J. W. de Bakker and J. van Leeuwen (Springer-Verlag, 1980) pp. 632–644. Google Scholar
    • Y. Van Rentergem and A. De Vos, International Journal of Unconventional Computing 1(4), 339 (2005). ISIGoogle Scholar
    • V. Vedral, A. Barenco and A. Ekert, Physical Review A 54(1), 147 (1996). CrossrefGoogle Scholar
    • P. Vitányi, Time, space, and energy in reversible computing, Conference on Computing Frontiers. Proceedings (ACM Press, 2005) pp. 435–444. Google Scholar
    • T. Yokoyama, H. B. Axelsen and R. Glück, Principles of a reversible programming language, Conference on Computing Frontiers. Proceedings (ACM Press, 2008) pp. 43–54. Google Scholar
    • T. Yokoyama and R. Glück, A reversible programming language and its invertible self-interpreter, Partial Evaluation and Program Manipulation. Proceedings (ACM Press, 2007) pp. 144–153. Google Scholar