Load Balancing Analysis of a Parallel Hierarchical Algorithm on the Origin2000

Xavier Cavin 1
1 ISA - Models, algorithms and geometry for computer graphics and vision
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : The ccNUMA architecture of the SGI Origin2000 has been shown to perform and scale for a wide range of scientific and engineering applications. This paper focuses on a well known computer graphics hierarchical algorithm - wavelet radiosity - whose parallelization is made challenging by its irregular, dynamic and unpredictable characteristics. Our previous experimentations, based on a naive parallelization, showed that the Origin2000 hierarchical memory structure was well suited to handle the natural data locality exhibited by this hierarchical algorithm. However, our crude load balancing strategy was clearly insufficient to benefit from the whole Origin2000 power. We present here a fine load balancing analysis and then propose several enhancements, namely "lazy copy" and "lure", that greatly reduce locks and synchronization barriers idle time. The new parallel algorithm is experimented on a 64 processors Origin2000. Even if in theory, a communication over-cost has been introduced, we show that data locality is still preserved. The final performance evaluation shows a quasi optimal behavior, at least until the 32-processor scale. Hereafter, a problematic trouble spot has to be identified to explain the performance degradation observed at the 64-processor scale.
Type de document :
Communication dans un congrès
Fifth European SGI/Cray MPP Workshop, 1999, Bologna, Italy, 10 p, 1999
Liste complète des métadonnées

Littérature citée [16 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00107796
Contributeur : Publications Loria <>
Soumis le : jeudi 19 octobre 2006 - 09:09:44
Dernière modification le : jeudi 11 janvier 2018 - 06:19:48
Document(s) archivé(s) le : mercredi 29 mars 2017 - 13:03:40

Fichier

Identifiants

  • HAL Id : inria-00107796, version 1

Collections

Citation

Xavier Cavin. Load Balancing Analysis of a Parallel Hierarchical Algorithm on the Origin2000. Fifth European SGI/Cray MPP Workshop, 1999, Bologna, Italy, 10 p, 1999. 〈inria-00107796〉

Partager

Métriques

Consultations de la notice

94

Téléchargements de fichiers

62