On the construction of zero-deficiency parallel prefix circuits with minimum depth
Haikun Zhu, Chung‐Kuan Cheng, Ronald Graham · ACM Transactions on Design Automation of Electronic Systems · 2006
A parallel prefix circuit has n inputs x 1 , x 2 , …, x n , and computes the n outputs y i = x i • x i −1 •…• x 1 , 1 ≤ i ≤ n , in parallel, where • is an arbitrary binary associative operator. Snir proved that the depth t and size s of any parallel prefix circuit satisfy the inequality t + s ≥2 n −2. Hence, a parallel prefix circuit is said to be of zero-deficiency if equality holds. In this article, we provide a different proof for Snir's theorem by capturing the structural information of zero-deficiency prefix circuits. Following our proof, we propose a new kind of zero-deficiency prefix circuit Z ( d ) by constructing a prefix circuit as wide as possible for a given depth d . It is proved that the Z ( d ) circuit has the minimal depth among all possible zero-deficiency prefix circuits.