Hostname: page-component-78c5997874-8bhkd Total loading time: 0 Render date: 2024-11-05T16:19:16.345Z Has data issue: false hasContentIssue false

Parallelization of divide-and-conquer by translation to nested loops

Published online by Cambridge University Press:  01 May 1999

CHRISTOPH A. HERRMANN
Affiliation:
Fakultät für Mathematik und Informatik, Universität Passau, Germany (e-mail: [email protected] [email protected])
CHRISTIAN LENGAUER
Affiliation:
Fakultät für Mathematik und Informatik, Universität Passau, Germany (e-mail: [email protected] [email protected])
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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
Copyright
1999 Cambridge University Press
Submit a response

Discussions

No Discussions have been published for this article.