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.
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
https://hal.inria.fr/inria-00107672
Contributeur : Jens Gustedt
<>
Soumis le : mercredi 22 décembre 2010 - 22:51:12
Dernière modification le : dimanche 20 mai 2018 - 20:20:10
Document(s) archivé(s) le : mercredi 23 mars 2011 - 02:23:22
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〉
