Massive parallelization of divide-and-conquer algorithms over powerlists

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 implicit massive data parallelism in a DC scheme explicit. The results given here are illustrated by many examples including Fast Fourier Transform and Batcherʹs bitonic sort.