Optimizing computation and communication in shuffle-exchange processors

Abstract

The implementation of shuffle exchange processors (e.g. FFT, sotting, Viterbi algorithm) is dominated by two problems, a massive computational task and a severe routing/communication problem. A new combined solution is presented for both problems. The novel bit-slice architecture offers a good improvement in processor speed and efficiency, as well as a reduction of the communication complexity by at least an order of magnitude. A VLSI design example shows the significance of the results.