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 inverted right perpendicular log(n+1)/log w inverted left perpendicular 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.