new bounds for parallel prefix circuits
In this paper, new upper and lower bounds are obtained for the number of gates in parallel prefix circuits with minimum depth when the number of inputs is a power of two. In addition, structural information concerning these circuits is described. Parallel prefix circuits with bounds imposed on the fan-out of the gates are also considered. In both cases, the upper and lower bounds obtained differ by small constant factors.
parallel circuits paper lower bound power structure informal factor