Z4: A New Depth-Size Optimal Parallel Prefix Circuit with Small Depth

摘要

Parallel prefix algorithms for the combinational circuit model are called parallel prefix circuits. An n-input prefix circuit with depth d and size s is depth-size optimal if d + s = 2n - 2. Smaller depth implies faster computation, while smaller size implies less power consumption, smaller VLSI area, and less cost. The fan-out of a prefix circuit should not be large for it to be of practical use. In this paper, we present a new depth-size optimal parallel prefix circuit, named Z4, with small depth and fan-out 4. For most values of n, there are no earlier depth-size optimal prefix circuits with bounded fan-out that have a depth less than that of Z4.