A new approach to constructing optimal parallel prefix circuits with small depth

Parallel prefix circuits are parallel algorithms performing the prefix operation for the combinational circuit model. The size of a prefix circuit is the number of operation nodes in the circuit, and the depth is the maximum level of operation nodes. A circuit with n inputs is depth-size optimal if its depth plus size equals 2n - 2. Smaller depth implies faster computation, while smaller size implies less power consumption, smaller VLSI area, and less cost. A circuit should have a small fan-out and small depth for it to be of practical use. In this paper, we present a new approach to easing the design of parallel prefix circuits, and construct a depth-size optimal parallel prefix circuit, named WE4, with fan-out 4. In many cases of n, WE4 has the smallest depth among all known depth-size optimal prefix circuits with bounded fan-out. (C) 2003 Elsevier Inc. All rights reserved.