TOWARD MASSIVELY-PARALLEL DESIGN OF MULTIPLIERS

Current efficient multipliers have computation delays that increase as O(log n), where n is the number of bits in the inputs. In fact, this asymptotic time complexity for multiplication cannot be improved if th e fan-in of the circuits is bounded above by a constant independent of n. In this paper, we study the potential gain in the speed of arithme tic computation provided by massive parallelism (i.e., unbounded fan-i n/fan-out) and examine the tradeoffs between the speed and the amount of hardware in large but restricted fan-in threshold circuits. Thresho ld circuits are chosen because the potential speed-up in AND-OR circui ts for multiplication is minimal even if the fan-in is allowed to be a rbitrarily large. It is well known in complexity theory that any arbit rary fan-in AND-OR circuit for multiplication of two n-bit integers mu st have omega(log n/log log n) computation delays if the circuit size is bounded by a polynomial in n. Threshold circuits, on the other hand , are more powerful and we present here threshold circuits for multipl ication with fan-in bounded by m, size O(2-d/2n2m1/(2d-1)square-rootlo g m), and depth O(d log n/log m) for every fixed integer d > 0. Simila r results are also shown for symmetric functions such as the parity. W ith the rapid advance of VLSI technology and the promise of large scal e implementations of cheap and reliable threshold gates, our results c ould be used for the design of massively parallel high-speed multiplie rs. (C) 1995 Academic Press, Inc.