Parallelization of Reversible Ripple-carry Adders
Research output: Contribution to journal › Journal article › Research › peer-review
Standard
Parallelization of Reversible Ripple-carry Adders. / Thomsen, Michael Kirkedal; Axelsen, Holger Bock.
In: Parallel Processing Letters, Vol. 19, No. 2, 2009, p. 205-222.Research output: Contribution to journal › Journal article › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - JOUR
T1 - Parallelization of Reversible Ripple-carry Adders
AU - Thomsen, Michael Kirkedal
AU - Axelsen, Holger Bock
PY - 2009
Y1 - 2009
N2 - The design of fast arithmetic logic circuits is an importantresearch topic for reversible and quantum computing. A specialchallenge in this setting is the computation of standardarithmetical functions without the generation of \emph{garbage}.Here, we present a novel parallelization scheme wherein $m$ parallel$k$-bit reversible ripple-carry adders are combined to form areversible $mk$-bit \emph{ripple-block carry adder} with logic depth$\mathcal{O}(m+k)$ for a \emph{minimal} logic depth$\mathcal{O}(\sqrt{mk})$, thus improving on the $mk$-bitripple-carry adder logic depth $\mathcal{O}(m\cdot k)$. Theunderlying mechanisms of the parallelization scheme are formallyproven correct. We also show designs for garbage-less reversiblecomparison circuits.We compare the circuit costs of the resulting ripple-block carryadder with known optimized reversible ripple-carry adders inmeasures of circuit delay, width, gate, transistor count, andrelative power efficiency, and find that the parallelized adderoffers significant speedups at realistic word sizes with modestparallelization overhead.
AB - The design of fast arithmetic logic circuits is an importantresearch topic for reversible and quantum computing. A specialchallenge in this setting is the computation of standardarithmetical functions without the generation of \emph{garbage}.Here, we present a novel parallelization scheme wherein $m$ parallel$k$-bit reversible ripple-carry adders are combined to form areversible $mk$-bit \emph{ripple-block carry adder} with logic depth$\mathcal{O}(m+k)$ for a \emph{minimal} logic depth$\mathcal{O}(\sqrt{mk})$, thus improving on the $mk$-bitripple-carry adder logic depth $\mathcal{O}(m\cdot k)$. Theunderlying mechanisms of the parallelization scheme are formallyproven correct. We also show designs for garbage-less reversiblecomparison circuits.We compare the circuit costs of the resulting ripple-block carryadder with known optimized reversible ripple-carry adders inmeasures of circuit delay, width, gate, transistor count, andrelative power efficiency, and find that the parallelized adderoffers significant speedups at realistic word sizes with modestparallelization overhead.
KW - Faculty of Science
KW - reversible circuits
KW - ripple-carry adders
KW - parallelization
KW - comparison circuits
KW - ripple-block carry adder
U2 - 10.1142/S0129626409000171
DO - 10.1142/S0129626409000171
M3 - Journal article
VL - 19
SP - 205
EP - 222
JO - Parallel Processing Letters
JF - Parallel Processing Letters
SN - 0129-6264
IS - 2
ER -
ID: 12704396