Depth-size trade-offs for parallel prefix computation

Research output: Contribution to journalArticlepeer-review

Abstract

A prefix circuit has n inputs x1,...,xn, and computes the n outputs x1 {ring operator} ... {ring operator} xi, i = 1, ..., n, where {ring operator} is an associative operation. It is shown that the depth t and the size s of parallel prefix circuits are related by the inequality t + s ≥ 2n -2. This is true even if arbitrary binary operations can be performed at each node. For 2 lg n - 2 < t < n - 1 optimal circuits with t + s = 2n - 2 are built. The depth and size of carry-lookahead circuits with n outputs are related by the inequality t + s ≥ 4n. The depth of parallel prefix circuits of width w is shown to be 2n (w + 1) + O(1).

Original languageEnglish (US)
Pages (from-to)185-201
Number of pages17
JournalJournal of Algorithms
Volume7
Issue number2
DOIs
StatePublished - Jun 1986
Externally publishedYes

ASJC Scopus subject areas

  • Control and Optimization
  • Computational Mathematics
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'Depth-size trade-offs for parallel prefix computation'. Together they form a unique fingerprint.

Cite this