About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Algorithmica
Paper
Optimal tradeoffs for addition on systolic arrays
Abstract
The complexity of adding two n-bit numbers on a two-dimensional systolic array is investigated. We consider different constraints on the systolic array, including: whether or not the input and output ports lie on the periphery of the array, constraints placed on the arrival and departure times of inputs and outputs . For all combinations of the above constraints, we obtain optimal tradeoffs among the resources of area, pipeline delay, and worst-case time. It turns out that there is a subtle interplay among the constraints and some of our results seem counterintuitive. For instance, we show that allowing more-significant bits to arrive earlier than less-significant bits can speed up addition by a factor of log n. We also show that multiplexing can often result in a smaller array. On the other hand, we show that some known results, such as Chazelle and Monier's bounds for arrays that have input/output ports on the perimeter, also hold in less constrained models. © 1991 Springer-Verlag New York Inc.