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 -