Queueing performance analysis of co-scheduling in a pool of processors environment
Pages 313 - 322
Abstract
We consider a connected set of workstations as a “pool of processors” and develop a queueing model to analyze the performance of optimal co-scheduling algorithms. The pool of processors model was originally developed for the Amoeba operating system. It was also used in the design of the recent IBM supercomputer model 9076 SP1. Recently, co-scheduling has been suggested as an approach for scheduling computationally intensive tasks in the pool of processors model. Co-scheduling algorithms select the best possible subset of workstations for a task to minimize its completion time.
We develop a queueing model which allows us to investigate the dynamic performance of co-scheduling algorithms from the system point of view under several queueing strategies. We use six different queueing strategies in combination with co-scheduling and compare the results to the M/M/m system where arriving tasks would be assigned to workstations as whole computations, and no co-scheduling would take place. The results show that the co-scheduling approach is viable under a wide range of system parameters. Moreover, performance differences of queueing strategies tend to diminish as the number of workstations grows. This suggests that co-scheduling is universally applicable across the queueing disciplines considered here when there are a large number of workstations.
References
[1]
M.J. Atallah, C. Lock, D.C. Marinescu, H.J. Siegel, and T.L. Casavant, "Models and Algorithms for Co- Scheduling Compute-Intensive Tasks on a Network of Workstations," Journal of Parallel and Distributed Computing, Vol. 16, December 1992, pp. 319-327.
[2]
D. Bertsekas and R. Gallager, "Data Networks," Prentice Hall, New Jersey, 1987.
[3]
H. Clark and B. McMillin, "DAWGS-A Distributed Compute Srever Utilizing Idle Workstations," Journal of Parallel and Distributed Computing, Feb 1992, pp. 175-186.
[4]
F. Douglis, and J. Ousterhout, "Process Migration in the Sprite Operating System," Proc. 7th Intn'l Conference on Dislmbuled Computing Systems, 1987, pp. 18-25.
[5]
K. Efe and M. Schaar, "Dyllamic Perfornl~nce of Co- Scheduling Compute Intensive Tasks on a Network of Workstations," ICDCS, Pittsburgh, PA, May 1993, pp. 525-531.
[6]
R. Hagman, "Process Server: Sharing Processing Power in a Workstation Environment," Proc. 6th lntn'l Conf. Distributed Computing Systems, 1986, pp. 260-267.
[7]
L. Kleinrock and W. Korfhage, "Collecting Unused Processing Capacity: An Analysis of Transient Distributed Systems," IEEE Transactions on Parallel and Distributed Systems, Vol. 4, No. 5, May 1993, pp. 535- 546.
[8]
P. Krueger, and R. Chawla, "The Stealth Distributed Scheduler," Proc. 11th Intn'l conf. Distributed Computing Systems, 1991, pp. 336-343.
[9]
M.J. Litzkow, M. Livny, and M.W. Mutka, "Condor- A Hunter of the Idle Workstations," Proc. 8th lntn'l. Con}. Distributed Computing systems, 1988, pp. 104-111.
[10]
D.A. Nichols, "Using idle Workstations in a Shared Computing Environment," llth ACM Symposium on Operating System Principles, Nov. 1987, pp. 5-12.
[11]
K. Ousterhout, A.R. Cherenston, F. Douglis, M.N. Nelson, and B.B. Welch, "The Sprite Network Operating System." ('omputer. February 1988, pp. 23-36.
[12]
S. Pulidas, D. ~lbwsley, and J. A. Stankovic, "Imbedding Gradient Estimators in Load Balancing Algorithms," Proc. 8th International Conference on Dis. tmbuted Computing Systems, 1988, pp. 482-490.
[13]
A.S. Tanenbaum and S.J. Mullender, "An Overview of the Amoeba Distributed Operating System," ACM Operating Systems Review, Vol. 15, No. 3, July 1981, pp. 51-64.
Index Terms
- Queueing performance analysis of co-scheduling in a pool of processors environment
Recommendations
Research: Effective queueing strategies for co-scheduling in a pool of processors
We consider a connected set of workstations as a 'pool of processors' and develop a queueing model to analyse the performance of optimal co-scheduling algorithms. The pool of processors model was originally developed for the Amoeba operating system. It ...
Adaptive scheduling with parallelism feedback
PPoPP '06: Proceedings of the eleventh ACM SIGPLAN symposium on Principles and practice of parallel programmingMultiprocessor scheduling in a shared multiprogramming environment is often structured as two-level scheduling, where a kernel-level job scheduler allots processors to jobs and a user-level task scheduler schedules the work of a job on the allotted ...
Performance of Hierarchical Processor Scheduling in Shared-Memory Multiprocessor Systems
Processor scheduling policies for multiprocessor systems can be broadly divided into space-sharing and time-sharing policies. Space-sharing policies divide the system processors into a number of partitions and each partition is exclusively allocated to ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © 1994 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 16 July 1994
Check for updates
Author Tags
Qualifiers
- Article
Conference
ICS94
Sponsor:
Acceptance Rates
ICS '94 Paper Acceptance Rate 45 of 114 submissions, 39%;
Overall Acceptance Rate 629 of 2,180 submissions, 29%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 229Total Downloads
- Downloads (Last 12 months)19
- Downloads (Last 6 weeks)8
Reflects downloads up to 22 Nov 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in