Efficient Parallelization of Line-Sweep Computations

Abstract : Multipartitioning is a strategy for partitioning multi-dimensional arrays on a collection of processors. With multipartitioning, computations that require solving 1D recurrences along each dimension of a multi-dimensional array can be parallelized effectively. Previous techniques for multipartitioning yield efficient parallelizations over 3D domains only when the number of processors is a perfect square. This paper considers the general problem of computing optimal multipartitionings for d-dimensional data volumes on an arbitrary number of processors. We describe an algorithm that computes an optimal multipartitioning for this general case, which enables efficient parallelizations of line-sweep computations under arbitrary conditions. Finally, we describe a prototype implementation of generalized multipartitioning in the Rice dHPF compiler and performance results obtained when using it to parallelize a line sweep computation for different numbers of processors.
Document type :
Reports
Complete list of metadatas

https://hal-lara.archives-ouvertes.fr/hal-02101907
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:09:31 AM
Last modification on : Friday, May 17, 2019 - 1:39:23 AM

File

RR2001-45.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02101907, version 1

Collections

Citation

Daniel Chavarría-Miranda, Alain Darte, Robert Fowler, John Mellor-Crummey. Efficient Parallelization of Line-Sweep Computations. [Research Report] LIP RR-2001-45, Laboratoire de l'informatique du parallélisme. 2001, 2+34p. ⟨hal-02101907⟩

Share

Metrics

Record views

3

Files downloads

7