Reconfigurable buses with shift switching: concepts and applications

We propose to enhance traditional broadcast buses by the addition of a new feature that we call shift switching. We show that on a linear array of processors enhanced with shift switching, the prefix sums of n bits can be computed in [log(n+1)/log w] broadcasts, each over n switches, assuming a global bus of width w. Next our prefix sums algorithm is used in conjunction with broadcasting on short buses to obtain several efficient architectural designs for the following fundamental problems: 1) ranking linked lists, 2) counting the number of 1´s in a sequence of n bits, and 3) sorting small sets. We see our main contribution in showing that the new bus feature leads to designs that are both theoretically interesting and practically relevant