PARALLELIZATION OF REVERSIBLE RIPPLE-CARRY ADDERS
Abstract
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- IBM Journal of Research and Development 17, 525 (1973). Crossref, ISI, Google Scholar
-
S. A. Cuccaro , A new quantum ripple-carry addition circuit , 8th Workshop on Quantum information Processing ( 2005 ) , arXiv:quant-ph/0410184v1 . Google Scholar - Progress in Quantum Electronics 23(1), 1 (1999). Crossref, ISI, Google Scholar
- Integration, the VLSI Journal 33(2), 89 (2002). Crossref, ISI, Google Scholar
- Optics News 11, 11 (1985). Crossref, Google Scholar
- International Journal of Theroretical Physics 21(4), 219 (1982). Crossref, ISI, Google Scholar
- IBM Journal of Research Development 5(3), 183 (1961). Crossref, ISI, Google Scholar
- IET Computers & Digital Techniques 1(2), 98 (2007). Crossref, ISI, Google Scholar
- G. Moore. Transcript of interview, Intel Developer Forum, 2007. Technical report, Intel Corp . Google Scholar
- Communications of the ACM 50(9), 30 (2007). Crossref, Google 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 ScholarM. 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. Calude (Springer-Verlag, 2008) pp. 229–242. Google Scholar- Journal of Systems Architecture 54(7), 697 (2008). Crossref, ISI, Google 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- International Journal of Unconventional Computing 1(4), 339 (2005). ISI, Google Scholar
- Physical Review A 54(1), 147 (1996). Crossref, Google Scholar
P. Vitányi , Time, space, and energy in reversible computing, Conference on Computing Frontiers. Proceedings (ACM Press, 2005) pp. 435–444. Google ScholarT. 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 ScholarT. 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


