Parallel Workloads Archive: Feitelson/Rudolph '98

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:

parameter description

W total number of work units in job

P_l lower bound on number of processors

P_u upper bound on number of processors

B_l lower bound on number of barriers

B_u upper bound on number of barriers

w_i mean number of work units per barrier

w_std standard deiation of number of work units per barrier

u_i mean compute time of a work unit

u_std standard deiation of compute time of work units

parameter	description
W	total number of work units in job
P_l	lower bound on number of processors
P_u	upper bound on number of processors
B_l	lower bound on number of barriers
B_u	upper bound on number of barriers
w_i	mean number of work units per barrier
w_std	standard deiation of number of work units per barrier
u_i	mean compute time of a work unit
u_std	standard 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
P_l = P_u = P
W = w_i = P
w_std = 0
B_l = B_u = 0
u_i = T
u_std = 0, or another value to express imbalance

Workpile:
This is an unstructured collection of multiple work units. It is expressed by
P_l = some minimum number or 1
P_u = some maximum number or the system size
W = w_i = the number of work units, which should be larger than P_u
w_std = 0
B_l = B_u = 0
u_i = average granularity
u_std = 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
P_l = some minimum number or 1, or fixed at P
P_u = some maximum number or the system size, or fixed at P
B_l = B_u = number of phases in the application
w_i = degree of parallelism in phase i, subject to P_l <= w_i <= P_u
w_std = variability in degrees of parallelism
W = w₀ + ... + w_B
u_i = grain of phase i
u_std = 0, or another value to express imbalance

Parallel Workloads Archive - Models