Translation of Divide-and-Conquer Algorithms to Nested Parallel Loop Programs

Christoph Herrmann and Christian Lengauer

We present a top-down classification of Divide-and-Conquer by skeletons expressed in the functional language Haskell.

Depending on the specializations made, the resulting skeleton can be transformed into a nested parallel loop schema using equational reasoning. Building this into a compiler allows the user to translate a recursive Divide- and-Conquer algorithm, expressed in terms of a skeleton, automatically to an imperative, data-parallel loop program, e.g., in HPF. The advantages of a loop program are that it can be optimized for a given objective function, using integer linear programming, and that it can be implemented on various architectures using existing compilers.

The ease of use of our skeletons is illustrated by the non-trivial example of Strassen's matrix multiplication.