Review of

Multiprocessor Scheduling for High-Variability Service Time Distribution

(Eric W. Parsons and Kenneth C. Sevcik)

by:
 
 

1.0 Purpose:

Many disciplines have been proposed for scheduling and processor allocation in multiprogrammed multiprocessors for parallel processing. These have been, for the most part, designed and evaluated for workloads having relatively low variability in service demand. It has been proven with different reports that variability of service demand in any given software system can be very high.
 
 

In this paper, the authors examine the performance of two well known static scheduling disciplines and one dynamic scheduling discipline, and propose preemptive versions of static scheduling disciplines that offer much better mean response times when the variability in service demand is high.

2.0 Background

2.1 Proof of the existence of problem:

In 1980, in a detailed study of the anticipated workload, NASA specified a workload consisting of eight different types of computational tasks with expected mean service requirements differing by as much as a factor of 3500 [NAS80]. This high degree of variability is further supported by another study recently done by same NASA facility in 1995 [FN95]. Assuming an exponential service demand, the variability is calculated by co-efficient of variation (CV or Cd) which is the ratio of standard deviation of service times to its mean. In the above case it is 7.23. A study done by Chiang, Mansharamani and Vernon in 1994, reports the co-efficient of variation to be between 2.5 and 6, with 40% above 4 [CMV94]. Also some measurements from Cray YMP sites, CV ranged from 30 to 70 [Ver94].
 
 

2.2 Processor Scheduling:

There are two main kinds of processor scheduling available: Uniprocessor Scheduling and Multiprocessor Scheduling. Each is further divided in to different disciplines. Below, is a diagram that shows the scheduling and their disciplines which the authors have explained in quite a detail in this paper.

Fig 1: The hierarchy of the scheduling disciplines.
 
 

3.0 Thesis

In this paper, the authors have proposed two disciplines of Static Quantum-Based scheduling; Feed Back Processors Working Set (FB-PWS) and Feed Back Adaptive Static Partitioning (FB-ASP) and compare them to two Static Run-To-Completion disciplines (PWS and ASP), and one dynamic discipline, Ideal Equipartitioning (IEQ). The authors have given a very detailed easy to understand explanation of each proposed discipline. A summary of each is as follows:

3.1 Standard Discipline:

PWS of a job is the maximum number of processors that maximizes the ratio of its speed up. In standard PWS discipline, when a job arrives in the system, and there are free processors, it is allocated the lesser of the number of free processors and its pws. If the job leaves then the scheduler repeatedly examines the jobs in the queue and selects the first one whose pws fits in the available processors; if none fit, then the first job is given the remaining processors.

3.1.2 ASP:

When the job arrives to the system, it is given the lesser of its maximum parallelism and the number of free processors. When a job is completed, the processors are allocated evenly among jobs that are waiting. A job's maximum parallelism is the number or processors for which its speedup function is maximized.

3.1.3 IEQ:

When a job's arrival or departure occurs, the processors are dynamically reallocated to the current set of jobs in such a way that (P mod J_total) jobs are allocated [P/J_total +1] processors and the rest one less, where J_total is the total number of jobs in the system.

3.2 Proposed disciplines:

Each job is allocated a fraction of P processors that corresponds to it’s share of the total anticipated number of processors allocated in the system.

3.2.2 FB-ASP:

An arriving job is configured with round (P/J_total) processors, except that if there are twice as many available processors as the computed partition size, then one more processor is given (to account for uneven partition size).
 
 
 
 

4.0 Proof of Thesis

To test their new proposed disciplines, several simulations were run on a system model. The system model consisted of 100 functionally equivalent processors. All the cost of scheduling and de-scheduling were introduced in the simulations. The reallocating of processors in IEQ was assumed to be 0. There were three workload models that were run on the system model. Two of the workload models were home made and the one was obtained from NASA.

The results obtained from running simulations on all of the workload are summarized as follows.

- IEQ does very well, in fact better than all if the overhead is near zero; in the simulation it was 0. This was the ideal case and one can not do equipartitioning without overheads.

- If estimates of the "pws" for each job are available, FB-PWS does as well as IEQ.

- If only an estimate of each job's maximum parallelism is available for use in scheduling, then FB-ASP is the best to use.
 
 

5.0 Open Research:

One issue that the study does not consider is the resource requirements of jobs. In particular, none of the disciplines examined, esp. IEQ, will perform well if memory is over committed. The future scheduling disciplines must take all jobs' resource requirements in to account including processor, memory and I/O.
 
 

6.0 References:

[CMV94] Su-Hui Chiang, Rajesh K. Mansharamani, and Mary K. Vernon. Use of applica-tion characteristics and limited preemption for run-to-completion parallel processor scheduling policies. In Proceedings of the 1994 ACM SIGMETRICS Conference on Measurement and Modelling of Computer Systems, pages 33 44, 1994.

[FN95] Dror G. Feitelson and Bill Nitzberg. Job characteristics of a production parallel sci-entific workload on the NASA Ames iPSC/860. In Job Scheduling Strategies for Parallel Processing, D. G. Feitelson and L. Rudolph (eds.), Lecture Notes in Com-puter Science Vol. 949. Springer-Verlag, 1995.

[NAS80] Numerical aerodynamic simulator processing system. Technical Report PC320-02, NASA Ames Research Center, September 1980.

[Ver94] Mary K. Vernon. Private communication, September 1994