Faster optimal parallel prefix circuits: New algorithmic construction

摘要

Parallel prefix circuits are parallel prefix algorithms on the combinational circuit model. A prefix 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, less VLSI area, and less cost. To be of practical use, the depth and fan-out of a depth-size optimal prefix circuit should be small. A circuit with a smaller fan-out is in general faster and occupies less VLSI area. In this paper, we present a new algorithm to design parallel prefix circuits, and construct a class of depth-size optimal parallel prefix circuits, named SU4, with fan-out 4. When n ≥ 30, SU4 has the smallest depth among all known depth-size optimal prefix circuits with fan-out 4.