Dynamic Behaviour

As the examples above show, a parallel function must describe not only the algorithm, but also some important aspects of how the parallel machine should organise the computation, i.e. the function's dynamic behaviour. In GpH, there are several aspects of dynamic behaviour:

• Parallelism control, which specifies what threads should be created, and in what order, using par and seq.
• Evaluation degree, which specifies how much evaluation each thread should perform. In the examples above, forcing functions were used to describe the evaluation degree.
• Thread granularity: it is important to spark only those expressions where the cost of evaluation greatly exceeds the thread creation overheads.
• Locality: part of the cost of evaluating a thread is the time required to communicate its result and the data it requires, and in consequence it may only be worth creating a thread if its data is local.

Evaluation degree is closely related to strictness. If the evaluation degree of a value in a function is less than the program's strictness in that value then the parallelism is conservative, i.e. no expression is reduced in the parallel program that is not reduced in its lazy counterpart. In several programs we have found it useful to evaluate some values speculatively, i.e. the evaluation-degree may usefully be more strict than the lazy function. Section * contains a case study program where a strategy is used to introduce speculative parallelism.