Scalable hardware-algorithms for binary prefix sums

Abstract. The main contribution of this work is to propose a number of broadcast-efficient VLSI architectures for computing the sum and the prefix sums of a w k-bit, k 2, binary sequence using, as basic building blocks, linear arrays of at most w2 shift switches. An immediate consequence of this feature is that in our designs broadcasts are limited to buses of length at most w2 making them eminently practical. Using our design, the sum of a wk-bit binary sequence can be obtained in the time of 2k 2 broadcasts, using 2wk2 + O(wk3) blocks, while the corresponding prefix sums can be computed in 3k 4 broadcasts using (k + 2)wk2 +O(kwk3) blocks.