# 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 |

### 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_{0} + ... + w_{B}

u_{i} = grain of phase i

u_{std} = 0, or another value to express imbalance

Parallel Workloads Archive - Models