Synthesising Parallel Functional Programs to Improve Dynamic Scheduling

This work investigates novel methods for improving the efficiency of evaluating lazy functional programs in parallel. We are specifically concerned with distributed memory architectures in which it is expensive for processors to communicate with each other via message passing. Traditionally, improvements in parallel evaluation are found by experimental processes supported by intuition and simple mathematical models and much existing research has been based on improving the execution time of a number of small benchmark programs. A key contribution of this thesis is the development of a language for synthe-sising the low-level run-time characteristics of functional programs. Using the language, it is possible to construct large synthetic workloads in a much shorter time-scale than the equivalent functional programs. From an experimenter's viewpoint the behaviour of the synthetic workloads is more predictable than that of functional programs because it is not distorted by compile-time transformations; it is therefore simpler to obtain specific experimental behaviour. The language enables the granularity of workloads to be altered in a straightforward manner and can model, under controlled conditions, instabilities due to run-time input. It is noted that functional language compilers ought to be able to estimate the expected time-costs of the individual functions of a program and that the time-cost information can then be used to guide dynamic scheduling strategies. Some research has taken place in this area but no existing research adequately deals with the problems of laziness (or, indeed, instabilities caused by run-time input). We investigate the effect on dynamic schedulers when laziness is not taken into account. The time-cost analysis is then improved to take account of lazy evaluation and we are able to show that the superior time-cost information can improve efficiency. However, large deviations from mean time-costs due to lazy evaluation and run-time input can precipitate inaccuracies even in the more complex compile-time estimates. We develop a number of heuristic run-time techniques to cope with these inaccuracies and gauge their success by introducing controlled instabilities