A topic of interest and some debate in recent studies has been how to use job characteristics in multiprocessor scheduling algorithms and whether or not their use offers significant benefits (mainly, reductions in mean response time).
An algorithm that has been derived from a technique called Process Control [33, 13], and has been widely studied and extensively compared with other processor allocation policies [36, 19, 18, 22, 5] is called equipartition. The equipartition algorithm simply allocates an equal number of processors to each job in the system by dynamically reallocating processors whenever jobs arrive or depart. It is a very practical algorithm in the sense that it can be easily implemented since no job characteristics are required for making allocation decisions. Moreover, it is robust in that it provides acceptable mean response times over a wide variety of workloads. Studies by some researchers have concluded that a desirable property of a good scheduler is that it share processing power equally among all jobs in the system [19, 18]. It is our hypothesis that a good scheduler should be able to produce mean response times that are significantly lower than equipartition, if given information about the execution characteristics of jobs.
Majumdar, Eager, and Bunt [20] compare policies having accurate knowledge or an estimate of a job's cumulative service demand with policies having no such information. They report that policies using knowledge of service demands improve mean response times significantly over Round Robin and First Come First Served (policies that have no information about service demand). They make no comparison with equipartition since it did not exist at the time.
In order to analytically compare the performance of equipartition with optimal algorithms Brecht [3] examines a number of scheduling algorithms in restricted environments. By assuming that there are no new job arrivals, that all jobs execute with perfect efficiency and considering a batch scheduling environment (i.e., all jobs are available to be scheduled at time zero), equipartition is shown to produce mean response times that are guaranteed to be within a factor of two of the optimal algorithm (LWF). Also, when new arrivals are considered (i.e., no longer using batch scheduling) the mean response time of equipartition can (under pessimal workloads) be a factor of N times (where N is the number of jobs executed) worse than the optimal algorithm Least Remaining Work First (LRWF).
When developing and comparing static scheduling algorithms
a number of researchers have
considered characteristics related
to the efficiency of a job's execution
such as a job's average,
minimum, maximum and variation in
parallelism, the knee of the execution
time - efficiency profile, and the
processor working set
[8, 31, 11, 21].
Eager, Zahorjan, and Lazowska
[8]
suggest that the number of processors to allocate
to each job in a multiprogrammed environment
could be made based on
the point at which the
ratio of efficiency to execution time,
/ 
, is maximized
( 
is the number of processors
allocated to job 
,
is the job's efficiency and
is its execution time,
when allocated processors).
Ghosal, Serazzi, and Tripathi
[11]
introduce another characterization
of a parallel program called the
processor working set
(pws).
Pws
has been defined as the minimum
number of processors that maximizes
the speedup per unit of cost
associated with the allocation of a processor.
The pws
is also shown to be equivalent
to the knee for a linear cost function.
They study a number of static scheduling
algorithms that use information about
a job's pws and show that they
perform well under a varying system load.
Majumdar, Eager and Bunt
[21]
also report that in a static scheduling environment,
allocating a number of processors
near the knee was effective in producing low
mean response times over a broad range of system loads.
Chiang, Mansharamani, and Vernon [5] study a number of static (run-to-completion) algorithms that use information about a job's execution rate characteristics (average parallelism and pws). They assert that policies using execution rate characteristics do not improve performance (compared with policies that use none) especially when the coefficient of variation of job service demand is greater than one (because jobs with long execution times are allocated too many processors).
Sevcik [31] finds that static policies that consider additional information about an application's parallelism, such as the minimum, maximum, and variation in parallelism, improve mean response time over methods that only consider average parallelism. Sevcik [32] also identifies a number of useful parameters for characterizing parallel applications and examines the problem of statically allocating processors to a batch of parallel applications given a priori knowledge of these parameters.
Zahorjan and McCann [36] and McCann, Vaswani, and Zahorjan [22] use simple information about a job's current degree of parallelism to reallocate processors in response to changes in the parallelism of the job; in a sense attempting to utilize processors more effectively. This dynamic allocation policy reduces mean response time when compared with repartitioning processors strictly upon job arrivals and departures [33, 13]. The advantage of this dynamic scheduling policy is that it may adjust to a job's changing demands for processors over time.
Recent studies examine scheduling algorithms that consider another important characteristic, the memory requirements of jobs [37, 4, 29, 23, 30, 1, 27, 28]. These studies identify memory (as well as processors) as being a critical resource for the effective execution of parallel programs and devise and investigate scheduling policies that ensure minimum processor allocations for jobs in order to secure sufficient memory resources. Our work does not explicitly model a job's memory requirements but rather relies on the execution signature of a job to implicitly indicate its memory requirements.