Skip to Main content Skip to Navigation
Reports

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 :
Reports
Complete list of metadata

Cited literature [15 references]  Display  Hide  Download

https://hal.inria.fr/inria-00071946
Contributor : Rapport de Recherche Inria <>
Submitted on : Tuesday, May 23, 2006 - 7:20:07 PM
Last modification on : Friday, February 26, 2021 - 3:28:07 PM
Long-term archiving on: : Sunday, April 4, 2010 - 10:45:45 PM

Identifiers

  • HAL Id : inria-00071946, version 1

Collections

Citation

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

Share

Metrics

Record views

222

Files downloads

142