Article contents
Parallelization of divide-and-conquer by translation to nested loops
Published online by Cambridge University Press: 01 May 1999
Abstract
We present a hierarchical classification of specializations of the divide-and-conquer paradigm. The aim is to identify a subclass of divide-and-conquer algorithms with an efficient parallel implementation which can be viewed as a static space-time mapping. The specializations impose a balanced call tree, a fixed degree of the problem division, and elementwise operations. The correctness of our compile-time transformations is proved by equational reasoning in Haskell; recursion and iteration are handled by induction. We demonstrate the practicality of the skeleton by some examples, one of which is Strassen's matrix multiplication.
- Type
- Research Article
- Information
- Copyright
- 1999 Cambridge University Press
- 7
- Cited by
Discussions
No Discussions have been published for this article.