Efficient scan operators for bit-serial processor arrays

A fast algorithm is presented for broadcasting a word of length w on an n×n single-instruction multiple-data (SIMD) array of bit-serial processing elements, in time O( n+w). Data-skewing problems caused by SIMD restrictions are solved by assuming that each processing element contains a shift register and an activity flag that allows each processing element to conditionally ignore instructions. The broadcasting algorithm is then extended to a fast segmented-scan (prefix) algorithm that runs in time O(n+(w+t)log n), where t is the time needed to perform the arbitrary, user-defined operation on which the scan is based. Because of the versatility of scan operations, many algorithms written for more powerful SIMD computers, such as the connection machine, can easily be adapted to bit-serial arrays. Slightly less efficient algorithms are also presented for processing elements that lack shift registers