Bi-criteria algorithm for scheduling jobs on cluster platforms

ABSTRACT

We describe in this paper a new method for building an efficient algorithm for scheduling jobs in a cluster. Jobs are considered as parallel tasks (PT) which can be scheduled on any number of processors. The main feature is to consider two criteria that are optimized together. These criteria are the makespan and the weighted minimal average completion time (minsum). They are chosen for their complementarity, to be able to represent both user-oriented objectives and system administrator objectives.We propose an algorithm based on a batch policy with increasing batch sizes, with a smart selection of jobs in each batch. This algorithm is assessed by intensive simulation results, compared to a new lower bound (obtained by a relaxation of ILP) of the optimal schedules for both criteria separately. It is currently implemented in an actual real-size cluster platform.

REFERENCES

• 1: The top500 organization website. http://www.top500.org.
• 2: Foto N. Afrati , Evripidis Bampis , Aleksei V. Fishkin , Klaus Jansen , Claire Kenyon, Scheduling to Minimize the Average Completion Time of Dedicated Tasks, Proceedings of the 20th Conference on Foundations of Software Technology and Theoretical Computer Science, p.454-464, December 13-15, 2000
• 3: Amnon Barak , Oren La'adan, The MOSIX multicomputer operating system for high performance cluster computing, Future Generation Computer Systems, v.13 n.4-5, p.361-372, March, 1998 [doi>10.1016/S0167-739X(97)00037-X ]
• 4: Henri Casanova , Graziano Obertelli , Francine Berman , Rich Wolski, The AppLeS parameter sweep template: user-level middleware for the grid, Proceedings of the 2000 ACM/IEEE conference on Supercomputing (CDROM), p.60-es, November 04-10, 2000, Dallas, Texas, United States
• 5: Walfredo Cirne , Francine Berman, A Model for Moldable Supercomputer Jobs, Proceedings of the 15th International Parallel & Distributed Processing Symposium, p.59, April 23-27, 2001
• 6: David E. Culler , Anoop Gupta , Jaswinder Pal Singh, Parallel Computer Architecture: A Hardware/Software Approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1997
• 7: P.-F. Dutot, G. Mounié, and D. Trystram. Handbook of Scheduling, chapter Scheduling Parallel Tasks - Approximation Algorithms. CRC Press, 2004. chapter 28 of this book.
• 8: D. G. Feitelson. Scheduling parallel jobs on clusters. In R. Buyya, editor, High Performance Cluster Computing, volume 1, Architectures and Systems, pages 519--533. Prentice Hall PTR, Upper Saddle River, NJ, 1999. Chap. 21.
• 9: Dror G. Feitelson , Larry Rudolph, Parallel Job Scheduling: Issues and Approaches, Proceedings of the Workshop on Job Scheduling Strategies for Parallel Processing, p.1-18, April 25, 1995
• 10: Ian Foster , Carl Kesselman, The grid: blueprint for a new computing infrastructure, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 11: M. R. Garey and R. L. Graham. Bounds on multiprocessor scheduling with resource constraints. SIAM Journal on Computing, 4:187--200, 1975.
• 12: Leslie A. Hall , Andreas S. Schulz , David B. Shmoys , Joel Wein, Scheduling to minimize average completion time: off-line and on-line approximation algorithms, Mathematics of Operations Research, v.22 n.3, p.513-544, Aug. 1997
• 13: Robert L. Henderson, Job Scheduling Under the Portable Batch System, Proceedings of the Workshop on Job Scheduling Strategies for Parallel Processing, p.279-294, April 25, 1995
• 14: David B. Jackson , Quinn Snell , Mark J. Clement, Core Algorithms of the Maui Scheduler, Revised Papers from the 7th International Workshop on Job Scheduling Strategies for Parallel Processing, p.87-102, June 16, 2001
• 15: R. Jain. The art of computer systems performance analysis. John Wiley, New York, 1991.
• 16: M. J. Litzkow, M. Livny, and M. W. Mutka. Condor : A hunter of idle workstations. In 8th International Conference on Distributed Computing Systems (ICDCS '88), pages 104--111, Washington, D.C., USA, June 1988. IEEE Computer Society Press.
• 17: 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]
• 18: E. Romagnoli, Y. Denneulin, and D. Trystram. A synthetic workload generator for cluster computing. In 3rd International Workshop on Performance Modeling, Evaluation, and Optimization of Parallel and Distributed Systems (PMEO-PDS'2004) in conjunction with IPDPS'04, Santa Fe, New Mexico, 2004.
• 19: Uwe Schwiegelshohn , Walter Ludwig , Joel L. Wolf , John Turek , Philip S. Yu, Smart SMART Bounds for Weighted Response Time Scheduling, SIAM Journal on Computing, v.28 n.1, p.237-253, Feb. 1999 [doi>10.1137/S0097539795286831]
• 20: Hadas Shachnai , John J. Turek, Multiresource malleable task scheduling to minimize response time, Information Processing Letters, v.70 n.1, p.47-52, April 01, 1999 [doi>10.1016/S0020-0190(99)00030-7 ]
• 21: David B. Shmoys , Joel Wein , David P. Williamson, Scheduling Parallel Machines On-line, SIAM Journal on Computing, v.24 n.6, p.1313-1331, Dec. 1995 [doi>10.1137/S0097539793248317]

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:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Scheduling; Concurrency

General Terms:
Algorithms, Management

Keywords:
algorithms, bi-criteria, moldable tasks, parallel computing, parallel tasks, scheduling