ISSN:
1432-0541
Keywords:
Addition
;
Area
;
Time
;
VLSI circuits
;
Input/output ports
;
Boundary layouts
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract The complexity of adding twon-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 logn. 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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01759034
Permalink
