Randomized Permutations in a Coarse Grained Parallel Environment [extended abstract] - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2003

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

Jens Gustedt

Résumé

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.
Fichier principal
Vignette du fichier
A03-R-186.pdf (110 Ko) Télécharger le fichier
Loading...

Dates et versions

inria-00107672 , version 1 (22-12-2010)

Identifiants

  • HAL Id : inria-00107672 , version 1

Citer

Jens Gustedt. Randomized Permutations in a Coarse Grained Parallel Environment [extended abstract]. Fifteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures - SPAA'03, ACM, Jun 2003, San Diego, CA, United States. pp.248-249. ⟨inria-00107672⟩
55 Consultations
53 Téléchargements

Partager

Gmail Facebook X LinkedIn More