Scheduling malleable tasks with precedence constraints

ABSTRACT

In this paper we propose an approximation algorithm for scheduling malleable tasks with precedence constraints. Based on an interesting model for malleable tasks with continuous processor allotments by Prasanna and Musicus [22, 23, 24], we define two natural assumptions for malleable tasks: the processing time of any malleable task is non-increasing in the number of processors allotted, and the speedup is concave in the number of processors. We show that under these assumptions the work function of any malleable task is non-decreasing in the number of processors and is convex in the processing time.Furthermore, we propose a two-phase approximation algorithm for the scheduling problem. In the first phase we solve a linear program to obtain a fractional allotment for all tasks. By rounding the fractional solution, each malleable task is assigned a number of processors. In the second phase a variant of the list scheduling algorithm is employed. In the phases we use two parameters μ ∈{1... ⌊ (m+1)/2⌋} and ρ ∈ [0,1] for the allotment and the rounding, respectively, where m is the number of processors. By choosing appropriate values of the parameters, we show (via a nonlinear program) that the approximation ratio of our algorithm is at most 100/63+100(√6469+13)/5481 ≈ 3.291919. We also show that our result is very close to the best asymptotic one.

REFERENCES

• 1: A. Agarwal, D. Chaiken, K. Johnson, D. Kranz, J. Kubiatowicz, K. Kurihara, B.-H. Lim, G. Maa, and D. Nussbaum, The MIT Alewife machine: a large-scale distributed-memory multiprocessor, Proceedings of the 1st Workshop on Scalable Shared Memory Multiprocessors, 1991.
• 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: David E. Culler , Richard M. Karp , David Patterson , Abhijit Sahay , Eunice E. Santos , Klaus Erik Schauser , Ramesh Subramonian , Thorsten von Eicken, LogP: a practical model of parallel computation, Communications of the ACM, v.39 n.11, p.78-85, Nov. 1996 [doi>10.1145/240455.240477]
• 4: David E. Culler , Anoop Gupta , Jaswinder Pal Singh, Parallel Computer Architecture: A Hardware/Software Approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1997
• 5: J. Du , J. Y.-T. Leung, Complexity of scheduling parallel task systems, SIAM Journal on Discrete Mathematics, v.2 n.4, p.473-487, Nov. 1989 [doi>10.1137/0402042]
• 6: P.-F. Dutot, G. Mounié and D. Trystram, Scheduling parallel tasks -- approximation algorithms, in Handbook of Scheduling: Algorithms, Models, and Performance Analysis, J. Y.-T. Leung (Eds.), CRC Press, Boca Raton, 2004.
• 7: M. Garey and R. Graham, Bounds for multiprocessor scheduling with resource constraints, SIAM Journal on Computing, 4 (1975), 187--200.
• 8: R. L. Graham, Bounds for certain multiprocessing anomalies, Bell System Technical Journal, 45 (1966), 1563--1581.
• 9: Jing-Jang Hwang , Yuan-Chieh Chow , Frank D. Anger , Chung-Yee Lee, Scheduling precedence graphs in systems with interprocessor communication times, SIAM Journal on Computing, v.18 n.2, p.244-257, April 1989 [doi>10.1137/0218016]
• 10: Klaus Jansen, Scheduling Malleable Parallel Tasks: An Asymptotic Fully Polynomial-Time Approximation Scheme, Proceedings of the 10th Annual European Symposium on Algorithms, p.562-573, September 17-21, 2002
• 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: K. Jansen and H. Zhang, Improved approximation algorithms for scheduling malleable tasks with precedence constraints, Technical Report, http://www.informatik.uni-kiel.de/~hzh/malle.ps.
• 13: K. Jansen and H. Zhang, An approximation algorithm for scheduling malleable tasks under general precedence constraints, manuscript.
• 14: Tomasz Kalinowski , Iskander Kort , Denis Trystram, List scheduling of general task graphs under LogP, Parallel Computing, v.26 n.9, p.1109-1128, Aug. 2000 [doi>10.1016/S0167-8191(00)00031-4 ]
• 15: J. K. Lenstra and A. H. G. Rinnooy Kan, Complexity of scheduling under precedence constraints, Operations Research, 26 (1978), 22--35.
• 16: R. Lepère, G. Mounié and D. Trystram, An approximation algorithm for scheduling trees of malleable tasks, European Journal of Operational Research, 142(2), (2002), 242--249.
• 17: R. Lepère, D. Trystram and G. J. Woeginger, Approximation algorithms for scheduling malleable tasks under precedence constraints, International Journal of Foundations of Computer Science, 13(4), (2002), 613--627.
• 18: Walter Ludwig , Prasoon Tiwari, Scheduling malleable and nonmalleable parallel tasks, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.167-176, January 23-25, 1994, Arlington, Virginia, United States
• 19: 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]
• 20: G. Mounié, C. Rapine and D. Trystram, A 3/2-dual approximation algorithm for scheduling independent monotonic malleable tasks, manuscript.
• 21: G. N. S. Prasanna, Structure Driven Multiprocessor Compilation of Numeric Problems, Technical Report MIT/LCS/TR-502, Laboratory for Computer Science, MIT, April 1991.
• 22: G. N. Srinivasa Prasanna , Bruce R. Musicus, Generalised multiprocessor scheduling using optimal control, Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.216-228, July 21-24, 1991, Hilton Head, South Carolina, United States [doi>10.1145/113379.113399]
• 23: G. N. Srinivasa Prasanna , Bruce R. Musicus, Generalized multiprocessor scheduling for directed acyclic graphs, Proceedings of the 1994 conference on Supercomputing, p.237-246, December 1994, Washington, D.C., United States
• 24: G. N. S. Prasanna and B. R. Musicus, The Optimal Control Approach to Generalized Multiprocessor Scheduling, Algorithmica, 15(1), (1996), 17--49.
• 25: Yu-Li Chou , H. Edwin Romeijn , Robert L. Smith , Martin Skutella, Approximation Algorithms for the Discrete Time-Cost Tradeoff Problem, Mathematics of Operations Research, v.23 n.4, p.909-929, Nov. 1998
• 26: 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]
• 27: H. Zhang, Approximation Algorithms for Min-Max Resource Sharing and Malleable Tasks Scheduling, PhD thesis, University of Kiel, Germany, 2004.

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:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

General Terms:
Algorithms

Keywords:
approximation algorithms, malleable tasks, precedence constraints, scheduling