Skip to Main content Skip to Navigation
New interface
Reports (Research report)

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 (Research report)
Complete list of metadata
Contributor : Colette ORANGE Connect in order to contact the contributor
Submitted on : Wednesday, April 17, 2019 - 9:09:31 AM
Last modification on : Wednesday, October 26, 2022 - 8:14:26 AM


Files produced by the author(s)


  • HAL Id : hal-02101907, version 1



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⟩



Record views


Files downloads