Scheduling on hierarchical clusters using malleable tasks

ABSTRACT

The model of malleable task (MT) was introduced some years ago and has been proved to be an efficient way for implementing parallel applications. It considers a target application at a larger level of granularity than in other models (corresponding typically to numerical routines) where the tasks can themselves be executed in parallel.

Clusters of SMP (symmetric Multi-Processors) are a cost effective alternative to parallel supercomputers. Such hierarchical clusters are parallel systems made from m SMP composed each by k identical processors. They are more and more popular, however, designing efficient software that tale full advantage of such systems remains difficult. This work describes a 2 — 2÷k approximation algorithm for scheduling a set of independent malleable tasks for the minimization of the parallel execution time, where k is a power of 2 (k > 2). For k = 2, a special treatment leads to the bound of 3/2 which is the best known for non hierarchical tasks. The algorithm presented here is a fully polynomial approximation scheme running in &Ogr;(nmk) time.

REFERENCES

• 1: R. Baker, E.G. Coffman, and R.L. Rivest. Orthogonal packings in two dimensions. SIAM Journal on Computing, 9(4):846-855, 1980.
• 2: Eric Blayo , Laurent Debreu , Gregory Mounie , Denis Trystram, Dynamic Load Balancing for Ocean Circulation Model with Adaptive Meshing, Proceedings of the 5th International Euro-Par Conference on Parallel Processing, p.303-312, August 31-September 03, 1999
• 3: R. Blumafe and D.S. Park. Scheduling on networks of workstations. 3rd Intel. Symp. of High Performance Distr. Computing, pages 96-105, 1994.
• 4: E.G. Coffman, M.R. Garey, D.S. Johnson, and R.E. Tarjan. Performance bounds for level-oriented two-dimensional packing algorithms. SIAM Journal on Computing, 9(4):808-826, 1980.
• 5: David E. Culler , Anoop Gupta , Jaswinder Pal Singh, Parallel Computer Architecture: A Hardware/Software Approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1997
• 6: Thomas Decker , Werner Krandick, Parallel Real Root Isolation Using the Descartes Method, Proceedings of the 6th International Conference on High Performance Computing, p.261-268, December 17-20, 1999
• 7: Dror G. Feitelson , Larry Rudolph , Uwe Schwiegelshohn , Kenneth C. Sevcik , Parkson Wong, Theory and Practice in Parallel Job Scheduling, Proceedings of the Job Scheduling Strategies for Parallel Processing, p.1-34, April 05, 1997
• 8: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 9: R. Giroudeau. L'impact des delais de communications hierarchiques sur la complexite et l'approximation des problemes d'ordonnancement. PhD thesis, Universite d' Evry, December 2000. in french.
• 10: Dorit S. Hochbaum , David B. Shmoys, Using dual approximation algorithms for scheduling problems theoretical and practical results, Journal of the ACM (JACM), v.34 n.1, p.144-162, Jan. 1987 [doi>10.1145/7531.7535]
• 11: Klaus Jansen , Lorant Porkolab, Linear-time approximation schemes for scheduling malleable parallel tasks, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.490-498, January 17-19, 1999, Baltimore, Maryland, United States
• 12: Walter T. Ludwig, Algorithms for scheduling malleable and nonmalleable parallel tasks, University of Wisconsin at Madison, Madison, WI, 1996
• 13: G. Mounie. Efficient scheduling of parallel application : the monotonic malleable tasks. PhD thesis, Institut National Polytechnique de Grenoble, June 2000. in french.
• 14: Gregory Mounie , Christophe Rapine , Dennis Trystram, Efficient approximation algorithms for scheduling malleable tasks, Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures, p.23-32, June 27-30, 1999, Saint Malo, France [doi>10.1145/305619.305622]
• 15: G. Mounie, C. Rapine, and D. Trystram. A approximation algorithm for independent scheduling malleable tasks. submitted for publication 2001.
• 16: V. J. Rayward-Smith, UET scheduling with unit interprocessor communication delays, Discrete Applied Mathematics, v.18 n.1, p.55-71, Nov. 1987 [doi>10.1016/0166-218X(87)90042-4]
• 17: A. Steinberg, A Strip-Packing Algorithm with Absolute Performance Bound 2, SIAM Journal on Computing, v.26 n.2, p.401-409, April 1997 [doi>10.1137/S0097539793255801]
• 18: T. Sterling and D. Becker et al. Beowulf: A parallel workstation for scientific computation. In ICPP'95, volume 1, pages 11-14, 1995.
• 19: John Turek , Joel L. Wolf , Philip S. Yu, Approximate algorithms scheduling parallelizable tasks, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.323-332, June 29-July 01, 1992, San Diego, California, United States [doi>10.1145/140901.141909]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Scheduling

General Terms:
Algorithms, Measurement, Performance, Theory, Verification

Keywords:
cluster computing, fully polynomial time approximation scheme, malleable tasks, scheduling