Using emulations to enhance the performance of parallel architectures

We illustrate the potential of techniques and results from the theory of network emulations to enhance the performance of a parallel architecture. The vehicle for this demonstration is a suite of algorithms that endow an N-processor bit-serial processor array A with a "meta-instruction" GAUGE k, which (logically) reconfigures A into an N/k-processor virtual machine B/sub k/ that has: 1) a datapath and memory bus whose emulated width is k bits, as opposed to A´s 1-bit width and 2) an instruction set that operates on k-bit words, in contrast to A´s instruction set, which operates on 1-bit words. In order to stress the strength of the approach, we show (via pseudocode) how our emulation techniques can be implemented efficiently even if A operates in strict SIMD mode, with only single-bit masking capabilities and with no indexed memory accesses. We describe at an algorithmic level how to implement our technique-including datapath conversion ("corner-turning") and the creation of the word-parallel instruction sets-on arrays of any regular network topology. We instantiate our technique in detail for arrays based on topologies with quite disparate characteristics: the hypercube, the de Bruijn network, and a genre of mesh with reconfigurable buses. Importantly, the emulations that underlie our technique do not alter the native machine´s instruction set, hence allowing an invariant programming model across gauges.