Concurrent Gang: Towards a Flexible and Scalable Gang Scheduler

• Fabricio Alves Barbosa da Silva Universite Pierre et Marie Curie
• Isaac D. Scherson Universite Pierre et Marie Curie / University of California

DOI: https://doi.org/10.5753/sbac-pad.1999.19796

Resumo

Gang scheduling has been widely used as a practical solution to the dynamic parallel job scheduling problem. Parallel tasks of a job are scheduled for simultaneous execution on a partition of a parallel computer. Gang Scheduling has many advantages, such as responsiveness, efficient sharing of resources and ease of programming. However, there are two major problems associated with gang scheduling: scalability and the decision of what to do when a task blocks. In this paper we propose a class of scheduling policies, dubbed Concurrent Gang, that is a generalization of gang-scheduling, and allows for the flexible simultaneous scheduling of multiple parallel jobs with different characteristics. Besides that, scalability in Concurrent Gang is achieved through the use of a global clock that coordinates the gang scheduler among different processors.

Palavras-chave: Parallel job scheduling, Gang scheduling

Referências

J. Jann et al. Modeling of Workloads in MPP. Job Scheduling Strategies for Parallel Processing, LNCS 1291:95-116. 1997.

Patrick G. Solbalvarro et al. Dynamic Coscheduling on Workstation Clusters. Job Scheduling Strategies for Parallel Processing. LNCS 1459:231-256. 1998.

D. Feitelson and M. A.Jette. Improved Utilization and Responsiveness with Gang Scheduling. Job Scheduling Strategies for Parallel Processing, LNCS 1291:238-261,1997.

D. Feitelson and L. Rudolph. Distributed Hierarchical Control for Parallel Processing. IEEE Computer, pages 65-77. May 1990.

D. Feitelson and L. Rudolph. Gang Scheduling Performance Benefits for Fine-Grain Synchronization. Journal of Parallel and Distributed Computing, 16:306-318.1992.

D. Fcitelson and L. Rudolph. Evaluation of Design Choices for Gang Scheduling Using Distributed Hierarchical Control. Journal of Parallel and Distributed Computing. 35: 18-34, 1996.

D. Feitelson and L. Rudolph. Metrics and Bechmarking for Parallel Job Scheduling. Job Scheduling Strategies for Parallel Processing, LNCS 1459:1-24, 1998.

M. A. Jette. Performance Characteristics of Gang Scheduling In Multiprogrammed Environments. In Proceedings of SC'97, 1997.

W. Lee. M. Frank, V. Lee. K. Mackenzie. and L. Rudolph. lmplications of I/O for Gang Scheduled Workloads. Job Scheduling Strategies for Parallel Processing, LNCS 1291:215-237. 1997.

R. Motwani. S. Phillips. and E. Tomg. Non-clairvoyant scheduling. Theoretical Computer Science. 130(1): 17-47, 1994.

J.K. Ousterhoul. Scheduling Techniques for Concurrent Systems. In Proceedings of the 3rd International Conference on Distributed Comp. Systems. pages 22-30. 1982.

F.A.B. Silva, L.M. Campos. and I.D. Scherson. A Lower Bound for Dynamic Scheduling of Data Parallel Programs. In Proceedings EUROPAR' 98, 1998.

F.A.B. Silva and I.D. Scherson. Improvements in Parallel Job Scheduling Using Gang Service. In Proceedings 1999 International Symposium on Parallel Architectures. Algorithms and Networks, 1999.

L. G. Valiant. A bridging model for parallel computations. Communications of the ACM. 33(8): 103-111, 1990.