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