Daniel Chavarría-Miranda, Alain Darte, Robert Fowler, and John Mellor-Crummey. On efficient parallelization of line-sweep computations. Research Report 2001-45, Laboratoire de l'Informatique du Parallélisme, École Normale Supériore de Lyon, November 2001. [ps], [pdf]

Multipartitioning is a strategy for partitioning multi-dimensional arrays among a collection of processors so that line-sweep computations can be performed efficiently. With multipartitioning, computations that require solving 1D recurrences along each dimension of a multidimensional 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 obtains when using ti to parallelize a line-sweep computation for different numbers of processors.

Keywords: loop parallelization, array mapping, generalized latin squares, High Performance Fortran.