Leo Liberti, James Ostrowski
Journal of Global Optimization
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.
Leo Liberti, James Ostrowski
Journal of Global Optimization
Matthew A Grayson
Journal of Complexity
Minghong Fang, Zifan Zhang, et al.
CCS 2024
Alfred K. Wong, Antoinette F. Molless, et al.
SPIE Advanced Lithography 2000