Paper Info
Title
Compile-time transformations and optimization of parallel Divide-and-Conquer algorithms
Abstract
In this paper we show how it is often possible to transform and optimize parallel algorithms based on the Divide-and-Conquer paradigm at compile time. Our goal is to make Divide-and-Conquer algorithms suitable for implementation on hypercube-like parallel architectures, such as the Connection Machine, even if the original algorithm implies a division function that is not the left-right division and/or communication pattern that cannot be implemented by direct-neighbor communication.Our tools are the formal model of the Divide-and-Conquer paradigm developed in [4] and the parallel programming language derived from this model: Divacon [2], [3].Our main results concern the replacement of last-k communication (broadcast) and mirror image communication with correspondent communication and the transformation from odd-even division to left-right division and vice versa. By using each of the techniques described in this paper it is possible to improve many Divide-and-Conquer algorithms by a factor of log(n).
Year
DOI
Venue
1991
10.1145/122616.122620
SIGPLAN Notices
Keywords
Field
DocType
parallel divide-and-conquer algorithm,direct-neighbor communication,correspondent communication,odd-even division,mirror image communication,divide-and-conquer algorithm,left-right division,compile-time transformation,divide-and-conquer paradigm,division function,communication pattern,last-k communication,divide and conquer,parallel programming language,parallel algorithm
Analysis of parallel algorithms,Programming language,Computer science,Compile time,Parallel algorithm,Embarrassingly parallel,Theoretical computer science,Parallel programming model,Divide and conquer algorithms,Bulk synchronous parallel,Cost efficiency
Journal
Volume
Issue
ISSN
26
10
0362-1340
Citations 
PageRank 
References 
9
1.06
1
Authors
2
Name
Order
Citations
PageRank
B. Carpentieri113612.01
G. Mou291.06