HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadata

Cited literature [11 references]  Display  Hide  Download

Contributor : Jens Gustedt Connect in order to contact the contributor
Submitted on : Wednesday, December 22, 2010 - 10:51:12 PM
Last modification on : Friday, February 26, 2021 - 3:28:02 PM
Long-term archiving on: : Wednesday, March 23, 2011 - 2:23:22 AM


  • HAL Id : inria-00107672, version 1



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⟩



Record views


Files downloads