The Feitelson & Rudolph 1998 Model

This is actually more of a framework to create models of the internal structure of parallel application, in order to be able to investigate the connections between application behavior and scheduling. This framework has to be populated with specific parameter values in order to create an actual model. Currently, no specific parameter values are being suggested due to lack of real data.

The parameters of the model are:
parameterdescription
Wtotal number of work units in job
Pllower bound on number of processors
Puupper bound on number of processors
Bllower bound on number of barriers
Buupper bound on number of barriers
wimean number of work units per barrier
wstdstandard deiation of number of work units per barrier
uimean compute time of a work unit
ustdstandard deiation of compute time of work units

Examples

Here are some examples of how to describe different types of applications.

Rigid jobs:
This is P work units running on P processors for T time, with no additional structure. It is expressed by
Pl = Pu = P
W = wi = P
wstd = 0
Bl = Bu = 0
ui = T
ustd = 0, or another value to express imbalance

Workpile:
This is an unstructured collection of multiple work units. It is expressed by
Pl = some minimum number or 1
Pu = some maximum number or the system size
W = wi = the number of work units, which should be larger than Pu
wstd = 0
Bl = Bu = 0
ui = average granularity
ustd = 0, or another value to express imbalance

Fork-join:
In this class of applications the degree of parallelism varies during the execution, which is partitioned into a set of discrete steps. It is expressed by
Pl = some minimum number or 1, or fixed at P
Pu = some maximum number or the system size, or fixed at P
Bl = Bu = number of phases in the application
wi = degree of parallelism in phase i, subject to Pl <= wi <= Pu
wstd = variability in degrees of parallelism
W = w0 + ... + wB
ui = grain of phase i
ustd = 0, or another value to express imbalance


Parallel Workloads Archive - Models