Efficient Parallelization of Line-Sweep Computations

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.Le "multi-partitionnement" est une stratégie de partitionnement multi-dimensionnel de tableaux sur un ensemble de processeurs. grâce au multi-partitionnement, des calculs qui nécessitent la résolution de récurrences 1D le long de chaque dimension d'un tableau multi-dimensionnel peut être parallélisée efficacement. les techniques précédentes de multi-partitionnement fournissant des parallélisations efficaces pour des tableaux 3D mais uniquement pour un nombre de processeurs égal à un carré parfait. Dans ce rapport nous considérons le problème général du calcul d'un multi-partitionnement optimal pour des volumes de données en dimension d pour un nombre quelconque de processeurs. Nous donnons un algorithme qui calcule un multi-partitionnement optimal pour ce cas général ce qui permet la parallélisation efficace des calculs par vagues 1D dans n'importe quelles conditions? Finalement, nous décrivons également un prototype d'implantation dans le compilateur dHPF de Rice et les résultats de performances obtenues lorsque le nombre de processeurs vari