Randomized Permutations in a Coarse Grained Parallel Environment [extended abstract]

Jens Gustedt 1
1 ALGORILLE - Algorithms for the Grid
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : We show how to uniformly distribute data at random (not to be confounded with permutation routing) in a coarse grained parallel environment with p processors. In contrast to previously known work, our method is able to fulfill the three criteria of uniformity, work-optimality and balance among the processors simultaneously. To guarantee the uniformity we investigate the matrix of communication requests between the processors. We show that its distribution is a generalization of the multivariate hypergeometric distribution and we give algorithms to compute it efficiently.
Type de document :
Communication dans un congrès
Friedhelm Meyer auf der Heide. Fifteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures - SPAA'03, Jun 2003, San Diego, CA, United States. ACM Press, pp.248-249, 2003
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00107672
Contributeur : Jens Gustedt <>
Soumis le : mercredi 22 décembre 2010 - 22:51:12
Dernière modification le : jeudi 11 janvier 2018 - 06:19:48
Document(s) archivé(s) le : mercredi 23 mars 2011 - 02:23:22

Identifiants

  • HAL Id : inria-00107672, version 1

Collections

Citation

Jens Gustedt. Randomized Permutations in a Coarse Grained Parallel Environment [extended abstract]. Friedhelm Meyer auf der Heide. Fifteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures - SPAA'03, Jun 2003, San Diego, CA, United States. ACM Press, pp.248-249, 2003. 〈inria-00107672〉

Partager

Métriques

Consultations de la notice

172

Téléchargements de fichiers

104