Efficient Parallelization of Line-Sweep Computations - LARA - Libre accès aux rapports scientifiques et techniques Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2001

Efficient Parallelization of Line-Sweep Computations

Résumé

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 varie
Fichier principal
Vignette du fichier
RR2001-45.pdf (500.88 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-02101907 , version 1 (17-04-2019)

Identifiants

  • HAL Id : hal-02101907 , version 1

Citer

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⟩
19 Consultations
50 Téléchargements

Partager

Gmail Mastodon Facebook X LinkedIn More