Fast prefix adders for non-uniform input arrival times

DOI10.1007/S00453-015-0067-XzbMATH Open1403.68082arXiv1411.2917OpenAlexW2167757808MaRDI QIDQ513308FDOQ513308

Authors: Stephan Held, Sophie Spirkl 

Publication date: 6 March 2017

Published in: Algorithmica (Search for Journal in Brave)

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.

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

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

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)

Cites Work

• Parallel Prefix Computation
• Faster optimal parallel prefix sums and list ranking
• A Parallel Algorithm for the Efficient Solution of a General Class of Recurrence Equations
• The delay of circuits whose inputs have specified arrival times
• On the cost of optimal alphabetic code trees with unequal letter costs
• Delay optimization of linear depth Boolean circuits with prescribed input 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
• Title not available (Why is that?)
• The delay of circuits whose inputs have specified arrival times
• Multilevel reverse-carry addition: Single and dual adders
• Title not available (Why is that?)
• Constructing depth-optimum circuits for adders and \textsc{And}-\textsc{Or} paths

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)