The Downey 1997 Model
This model is based on an analysis of the SDSC logs, and was
re-affirmed by the CTC log as well.
The goal was to produce a model that allows the remaining runtime of a
job to be estimated, given its current age.
In addition, this model is for moldable and malleable jobs, where the
number of processors allocated can be chosen by the scheduler when the
job is started.
As a result, the speedup function must be included in the model.
Degrees of Parallelism
This model explicitly disregards the dominance of powers of two sizes
in the logs, under the assumption that this is a result of the
interface to commonly used queueing systems such as NQS.
It is therefore proposed to "smooth" the distribution.
The suggested model is log-uniform:
the probability that a job use less than n processors is
proportional to log n.
This is interpreted as the average parallelism in the job, and is used
in the definition of the speedup function.
Cumulative Runtime
Rather than model runtime independently from the degree of
parallelism, the cummulative runtime (that is the sum over all
processors) is modeled.
This is taken to represent the total work done by the job, independent
of how many processors are used.
The actual runtime is then obtained by applying the speedup function,
given the number of processors chosen by the scheduler.
The proposed model is again log-uniform:
the probability that a job use less than t node-seconds is
proportional to log t.
Speedup Function
The speedup function is modeled using 3 parameters:
the average parallelism of the job, the variance in parallelism, and
the number of processors.
Given these parameters, a hypothetical parallelism profile is
constructed, and the speedup calculated.
The equations are given in the paper.
Distributions from which the parameters can be selected were later
proposed by Cirne and Berman.
Arrival Process
The arrival process used is Poisson, with a twist:
Each day of simulated time is divided into two parts of 12 hours each.
During the first part (the day) jobs arrive according to the Poisson
process, but may be queued if they cannot run immediately.
During the second part (the night) no more jobs arrive, and the system
serves jobs that were queued during the day.
Parallel Workloads Archive - Models