LIMITED WIDTH PARALLEL PREFIX CIRCUITS

In this paper, we present lower and upper bounds on the size of limited width, bounded and unbounded fan-out parallel prefix circuits. The lower bounds on the sizes of such circuits are a function of the depth, width, and number of inputs. The size requirement of an N input bounded fan-out parallel prefix circuit having limited width W and extra depth k (the difference between allowed and minimum possible depth) is shown to be Ω(N log2W/2k + N) for k ≤ log2W. This implies that insisting on minimum depth causes the circuit size to be nonlinear, while as little as log2log2W of extra depth can possibly reduce the size to linear. Also, we show that there is a clear difference between the two cases of bounded and unbounded fan-out by proving the size of a limited width, unbounded fan-out parallel prefix circuit lies between a lower bound of Ω((2 + 21-k/3)N) and an upper bound of O((2 + 21-k)N). Uniform, systolic constructions of limited width parallel prefix circuits are provided here and shown to be asymptotically optimal. By associating the width of the circuit with the number of processors and the fan-out capabilities of the circuit with the interconnection structure of a multiprocessor, time- and processor-efficient algorithms may be developed. © 1990 Kluwer Academic Publishers.