Fast prefix adders for non-uniform input arrival times

DOI10.1007/S00453-015-0067-XMaRDI QIDQ513308zbMATH OpenOpenAlexFDO

Authors Stephan Held, Sophie Spirkl

Publication date 6 March 2017

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1411.2917

zbMATH Keywords

delaycircuitadditionnon-uniform input arrival timesparallel prefix problemprefix adder

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Numerical algorithms for computer arithmetic, etc. (65Y04)

Abstract: We consider the problem of constructing fast and small parallel prefix adders for non-uniform input arrival times. This problem arises whenever the adder is embedded into a more complex circuit, e. g. a multiplier. Most previous results are based on representing binary carry-propagate adders as so-called parallel prefix graphs, in which pairs of generate and propagate signals are combined using complex gates known as prefix gates. Adders constructed in this model usually minimize the delay in terms of these prefix gates. However, the delay in terms of logic gates can be worse by a factor of two. In contrast, we aim to minimize the delay of the underlying logic circuit directly. We prove a lower bound on the delay of a carry bit computation achievable by any prefix carry bit circuit and develop an algorithm that computes a prefix carry bit circuit with optimum delay up to a small additive constant. Furthermore, we use this algorithm to construct a small parallel prefix adder. Compared to existing algorithms we simultaneously improve the delay and size guarantee, as well as the running time for constructing prefix carry bit and adder circuits.

Recommendations

• Faster carry bit computation for adder circuits with prescribed arrival times
• Variable Latency Speculative Parallel Prefix Adders for Unsigned and Signed Operands
• scientific article; zbMATH DE number 4102994
• scientific article; zbMATH DE number 4057452
• Fast Parallel-Prefix Architectures for Modulo 2n-1 Addition with a Single Representation of Zero
• A novel parallel prefix adder for optimized radix-2 FFT processor
• Accelerated shift-and-add algorithms
• The flagged prefix adder and its applications in integer arithmetic

Cites work

• A Parallel Algorithm for the Efficient Solution of a General Class of Recurrence Equations
• Delay optimization of linear depth Boolean circuits with prescribed input arrival times
• Faster optimal parallel prefix sums and list ranking
• On the cost of optimal alphabetic code trees with unequal letter costs
• Parallel Prefix Computation
• The delay of circuits whose inputs have specified arrival times

Cited in

(7)

• The flagged prefix adder and its applications in integer arithmetic
• Faster carry bit computation for adder circuits with prescribed arrival times
• scientific article; zbMATH DE number 2081107 (Why is no real title available?)
• The delay of circuits whose inputs have specified arrival times
• Multilevel reverse-carry addition: Single and dual adders
• Constructing depth-optimum circuits for adders and \textsc{And}-\textsc{Or} paths
• scientific article; zbMATH DE number 4057452 (Why is no real title available?)

This page was built for publication: Fast prefix adders for non-uniform input arrival times

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q513308)