K. Achatz et W. Schulte, MASSIVE PARALLELIZATION OF DIVIDE-AND-CONQUER ALGORITHMS OVER POWERLISTS, Science of computer programming, 26(1-3), 1996, pp. 59-78
We present transformation rules to parallelize divide-and-conquer (DC)
algorithms over powerlists. These rules convert the parallel control
structure of DC into a sequential control flow, thereby making the imp
licit massive data parallelism in a DC scheme explicit. The results gi
ven here are illustrated by many examples including Fast Fourier Trans
form and Batcher's bitonic sort.