Parallel Optimization of a Reversible (Quantum) Ripple-Carry Adder
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Standard
Parallel Optimization of a Reversible (Quantum) Ripple-Carry Adder. / Thomsen, Michael Kirkedal; Axelsen, Holger Bock.
Unconventional Computing: 7th International Conference, UC 2008, Vienna, Austria, August 25-28, 2008, proceedings. ed. / Cristian S. Calude; José Felix Costa; Rudolf Freund; Marion Oswald; Grzegorz Rozenberg. Springer, 2008. p. 228-241 (Lecture notes in computer science; No. 5204).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - GEN
T1 - Parallel Optimization of a Reversible (Quantum) Ripple-Carry Adder
AU - Thomsen, Michael Kirkedal
AU - Axelsen, Holger Bock
N1 - Conference code: 7
PY - 2008
Y1 - 2008
N2 - 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. The CDKM-adder is a recent garbage-less reversible (quantum) ripple-carry adder. We optimize this design with a novel parallelization scheme wherein m parallel k-bit CDKM-adders are combined to form a reversible mk-bit ripple-block carry adder with logic depth O(m+k) for a minimal logic depth O(\sqrt{mk}), thus improving on the mk-bit CDKM-adder logic depth O(mk). We also show designs for garbage-less reversible set-less-than circuits. We compare the circuit costs of the CDKM and parallel adder in measures of circuit delay, width, gate and transistor count, and find that the parallelized adder offers significant speedups at realistic word sizes with modest parallelization overhead.
AB - 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. The CDKM-adder is a recent garbage-less reversible (quantum) ripple-carry adder. We optimize this design with a novel parallelization scheme wherein m parallel k-bit CDKM-adders are combined to form a reversible mk-bit ripple-block carry adder with logic depth O(m+k) for a minimal logic depth O(\sqrt{mk}), thus improving on the mk-bit CDKM-adder logic depth O(mk). We also show designs for garbage-less reversible set-less-than circuits. We compare the circuit costs of the CDKM and parallel adder in measures of circuit delay, width, gate and transistor count, and find that the parallelized adder offers significant speedups at realistic word sizes with modest parallelization overhead.
U2 - 10.1007/978-3-540-85194-3_19
DO - 10.1007/978-3-540-85194-3_19
M3 - Article in proceedings
SN - 978-3-540-85193-6
T3 - Lecture notes in computer science
SP - 228
EP - 241
BT - Unconventional Computing
A2 - Calude, Cristian S.
A2 - Costa, José Felix
A2 - Freund, Rudolf
A2 - Oswald, Marion
A2 - Rozenberg, Grzegorz
PB - Springer
Y2 - 25 August 2008 through 28 August 2008
ER -
ID: 9353632