An efficient scheduling algorithm for multiprogramming on parallel
computing systems
169. B. B. Zhou, R. P. Brent and X. Qu,
An efficient scheduling algorithm for multiprogramming on parallel
computing systems,
Australian Computer Science Communications 19, 1 (1997), 336-345.
Paper:
dvi (37K),
pdf (109K),
ps (61K).
Abstract
In conventional coscheduling, or gang scheduling of parallel
workloads a round-robin queueing algorithm is adopted
and the length of scheduling slots is fixed.
However, the characteristics of parallel workloads can be quite different
from sequential workloads.
The system may not perform effectively using the simple round-robin
algorithm.
In this paper we introduce a new queueing algorithm.
Our new system consists of two queues, a service queue which
can hold more than one processes and a waiting queue which has multiple
levels.
This system has several potential advantages over some conventional
queueing systems in scheduling parallel workloads.
For example, it may achieve a higher system throughput and also a higher
cache hit ratio,
so the problems encountered in conventional coscheduling are alleviated.
The issue of implementation of our algorithm is also discussed.
Comments
Related papers are
[180,
181,
189,
192,
194,
198,
202].
Go to next publication
Return to Richard Brent's index page