Parallel Workloads Archive: Sevcik '94

The Sevcik 1994 Model

This is a model of application speedup, which is useful for modeling jobs that are scheduled on varying partition sizes (that is, moldable or malleable jobs). It has been shown that actual speedup functions can indeed be represented in this form.

Speedup Function

The speedup function is modeled using two inputs and three parameters.

The inputs are
Wthe total work done by the job
nthe number of processors allocated

The parameters are
phi the load imbalance of threads
alphathe amount of sequential and per-processor work
beta communication and congestion delays

The formula for the runtime of the job is then

T(n) = phi W/n + alpha + beta n

Suggested values for these parameters are
W phi alphabeta
workload110001.020.05 0
workload210001.3 25 25
Where the values for W are mean values, and the distribution is selected so as to achieve the desired variance. In the first workload, all jobs have nearly ideal speedup. In the second, small jobs experience poor speedup while large jobs experience reasonable speedup.


Parallel Workloads Archive - Models