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

Randomized Permutations in a Coarse Grained Parallel Environment

Jens Gustedt 1
1 RESEDAS - Software Tools for Telecommunications and Distributed Systems
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : We show how to distribute data at random (not to be confounded with permutation routing) in a coarse grained parallel environment with $p$ processors. Previously known methods were not 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 give algorithms to compute it efficiently.
Document type :
Complete list of metadata

Cited literature [15 references]  Display  Hide  Download

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Tuesday, May 23, 2006 - 7:20:07 PM
Last modification on : Friday, February 4, 2022 - 3:21:50 AM
Long-term archiving on: : Sunday, April 4, 2010 - 10:45:45 PM


  • HAL Id : inria-00071946, version 1



Jens Gustedt. Randomized Permutations in a Coarse Grained Parallel Environment. [Research Report] RR-4639, INRIA. 2002, pp.12. ⟨inria-00071946⟩



Record views


Files downloads