Randomized permutations in a coarse grained parallel environment

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

REFERENCES

• 1: A. Czumaj, P. Kanarek, M. Kutylowski, and K. Lorys. Fast generation of random permutations via networks simulation. Algorithmica, 21 (1):2--20, 1998.
• 2: Mohamed Essaïdi, Isabelle Guérin Lassous, and Jens Gustedt. SSCRAP: An environment for coarse grained algorithms. In Fourteenth IASTED International Conference on Parallel and Distributed Computing and Systems (PDCS 2002), 2002.
• 3: Assefaw Hadish Gebremedhin , Isabelle Guérin Lassous , Jens Gustedt , Jan Arne Telle, PRO: A Model for Parallel Resource-Optimal Computation, Proceedings of the 16th Annual International Symposium on High Performance Computing Systems and Applications, p.106, June 16-19, 2002
• 4: Michael T. Goodrich, Randomized fully-scalable BSP techniques for multi-searching and convex hull construction, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.767-776, January 05-07, 1997, New Orleans, Louisiana, United States
• 5: Isabelle Guérin Lassous and Éric Thierry. Generating random permutations in the framework of parallel coarse grained models. In Proceedings of OPODIS'2000, volume 2 of Studia Informatica Universalis, pages 1--16, 2000.
• 6: Jens Gustedt. Randomized permutations in a coarse grained parallel environment. Technical Report RR-4639, INRIA, November 2002.
• 7: Torben Hagerup, Fast parallel generation of random permutations, Proceedings of the 18th international colloquium on Automata, languages and programming, p.405-416, June 1991, Madrid, Spain
• 8: Clyde P. Kruskal , Larry Rudolph , Marc Snir, A complexity theory of efficient parallel algorithms, Theoretical Computer Science, v.71 n.1, p.95-132, 13 March 1990 [doi>10.1016/0304-3975(90)90192-K]
• 9: Kyle Siegrist. Virtual Laboratories in Probability and Statistics, chapter C.4, Finite Sampling Models: The Multivariate Hypergeometric Distribution. University of Alabama, 2001. URL http://www.math.uah.edu/stat/urn/urn4.html.
• 10: Leslie G. Valiant, A bridging model for parallel computation, Communications of the ACM, v.33 n.8, p.103-111, Aug. 1990 [doi>10.1145/79173.79181]
• 11: H. Zechner. Efficient sampling from continuous and discrete unimodal distributions. PhD thesis, Technical University Graz, Austria, 1994.

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Distributed programming

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Permutations and combinations

General Terms:
Algorithms, Performance, Theory

Keywords:
coarse grained parallelism, randomized permutations, uniformly generated communication matrix