Introduction

In this research we address the problem of scheduling many adaptively parallel jobs on a multiprocessor system[4,5,6]. An adaptively parallel job is a job that can change its parallelism in the course of its execution. Today, most multiprocessor systems use static allocation, where a fixed number of processors is allocated to the job for its lifetime. This policy places the burden of estimating the parallelism of the job on the programmer. In addition, since the parallelism of the job may change during execution, there are programs for which any static allocation will lead to either inefficiency or unnecessary slowdown. Static allocation schemes may also lead to the starvation of some jobs if other jobs are using all the processors in the system. Ideally, we would like to adaptively change the number of processors allotted to a particular job as the job's parallelism and the state of the system changes.

Specifically, we address the problem of how an adaptively parallel job should request processors from the operating system's scheduler. If it requests too many processors, it may run faster, but it may use the processors inefficiently (i.e., waste processor cycles). If it requests too few processors, it may run efficiently, but unnecessarily slowly. In this project, we are looking for provably effective and practical algorithms for making processor requests, obviating the need for the user to estimate the parallelism of his/her job. We have two competing performance metrics, namely, running time, the time to completion of the parallel job, and waste, the total number of processor cycles wasted by the job in the course of its execution. We try to bound both of these metrics and exhibit trade-offs between them.

Approach

Our model for jobs interacting with the operating system is as follows. At certain points in the computation, the job requests some number of processors, but it does not know how many it can actually use. It can see its history of utilization, but it cannot predict the future for even one step. Upon receiving the job's request, the operating system has some number of processors available that it can allocate to the job. If the job requests more processors than are available, the job receives all the available processors. If it requests fewer processors than are available, it receives its request. In either case, the job then schedules its work on the received processors for a (relatively) small interval. At the end of this interval, the job makes another request for the next interval.

We make no assumptions about the allocation policy of the operating system Instead we treat the operating system is an adversary and assume that the operating system will have the worst possible processor availability profile to make the job run as slow as possible and/or make it waste many processors. For example, the operating system may make the processor availability high whenever the job has low desire and vice versa, thus keeping the allotment of the job always low and increasing the running time of the job. Treating the OS as a malicious adversary allows us to abstract away all the other environmental factors (presence/absence of other jobs, etc.) as part of the operating system. Thus, we do not have to worry about these external factors and can now concentrate on a single job, and bound its running time and waste.

Progress

We have developed an exponential-increase-exponential-decrease algorithm for making processor requests. With this algorithm, if the job sees indications that it has not been using processors efficiently, it multiplicatively decreases its request. Similarly if it has been efficient, it increases the number of processors requested. To quantify our results, let be the a posteriori work of a job and let be the length of its critical path. The waste is the number of processor cycles that a job is alloted, but doesn't use. Let P be the largest number of processors available and P' be the average number of processors available over all but the time steps with the largest processor availability. We first looked at the case where the requests and allotments are made on every time step, and the job can use a greedy scheduler[2,3] to schedule the ready work on allotted processors. In this simple case, the above algorithm can schedule the job to run with waste at most and in time for any . These results exhibit the trade-off between the completion time and waste. As increases, the time to completion reduces, but the waste increases.

Future Work

We are working to prove the time and waste bounds in a more general case, where the allotment is done over a longer interval (more than one step), and we use a more practical scheduler, like the randomized work-stealing scheduler described in [1]. In addition, we are trying to prove similar bounds in the case where the job doesn't have perfect information about the utilization history. One possible approach is for the job to use samples to guess the history.

Acknowledgment

Thanks to Jim Sukha and Gideon Stupp for their help in developing the algorithm and everyone in the Supercomputing Technologies Group for their feedback and comments.

Research Support

This research is supported in part by Singapore-MIT Alliance and by NSF grants ACI-0324974 and CNS-0305606.

References

[1] Robert D. Blumofe and Charles E. Leiserson. Scheduling Multithreaded Computations by Work Stealing. In Journal of the ACM, pp. 720--748, September, 1999.

[2] Richard. P. Brent. The parallel evaluation of general arithmetic expressions. In Journal of the ACM, 21(2):pp. 201--206, April 1974.

[3] Ronald. L. Graham. Bounds on multi processor anomalies. In Journal of the Applied Mathematics, 17(2):pp. 416--429, March 1969.

[4] C. G. Plaxton, N. S. Arora, R. D. Blumofe. Thread scheduling for multiprogrammed multiprocessors. In Proceedings of the 10th ACM Symposium of Parallel Algorithms and Architectures, pp. 119--129, Puerto Vallarta, Mexico, June 1998.

[5] Siddhartha Sen. Dynamic Processor Allocation for Adaptively Parallel Jobs. Master's thesis, Massachusetts Institute of Technology, September 2004.

[6] B. Song. Scheduling adaptively parallel jobs. Master's thesis, Massachusetts Institute of Technology, January 1998.