Efficient emulation of MIMD behavior on SIMD machines

SIMD computers have proved to be a useful and cost effective approach
to massively parallel computation. On the other hand, there are
algorithms which are very inefficient when directly translated into a
data-parallel program.This paper presents a number of simple
transformations which are able to reduce this SIMD overhead to
a moderate constant factor. It also introduces techniques for
reducing the remaining overhead using Markov chain models of control
flow. The optimization problems involved are NP-hard in general but
there are many useful heuristics, and closed form optimizations for a
probabilistic variant.