MASSIVE PARALLELIZATION OF DIVIDE-AND-CONQUER ALGORITHMS OVER POWERLISTS

Authors
ACHATZ K SCHULTE W
Citation
K. Achatz et W. Schulte, MASSIVE PARALLELIZATION OF DIVIDE-AND-CONQUER ALGORITHMS OVER POWERLISTS, Science of computer programming, 26(1-3), 1996, pp. 59-78
Citations number
18
Categorie Soggetti
Computer Sciences","Computer Science Software Graphycs Programming
Journal title
Science of computer programming → ACNP
ISSN journal
01676423
Volume
26
Issue
1-3
Year of publication
1996
Pages
59 - 78
Database
ISI
SICI code
0167-6423(1996)26:1-3<59:MPODAO>2.0.ZU;2-#
Abstract
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 imp licit massive data parallelism in a DC scheme explicit. The results gi ven here are illustrated by many examples including Fast Fourier Trans form and Batcher's bitonic sort.