Application-specific array processors for binary prefix sum computation

The main contribution of this work is to propose two application-specific bus architectures for computing the prefix sums of a binary sequence. Our architectures feature the following characteristics: all broadcasts occur on buses of length 15 or 63; we use a new technique that we call shift switching which allows switches to cyclically permute an incoming signal, dramatically improving the performance of the reconfigurable bus system. As it turns out, our special-purpose architectures improve the performance of the best algorithms known to date by a significant factor. Specifically, our solutions require no adders, are faster, and use less VLSI area than the architectures of the state of the art