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 <>
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