While it is hard to write good sequential programs, it can be considerably harder to write good parallel ones. At Glasgow we have worked on several fairly large parallel programming projects and have slowly, and sometimes painfully, developed a methodology for parallelising sequential programs.
The essence of the problem facing the parallel programmer is that, in addition to specifying what value the program should compute, explicitly parallel programs must also specify how the machine should organise the computation. There are many aspects to the parallel execution of a program: threads are created, execute on a processor, transfer data to and from remote processors, and synchronise with other threads. Managing all of these aspects on top of constructing a correct and efficient algorithm is what makes parallel programming so hard. One extreme is to rely on the compiler and runtime system to manage the parallel execution without any programmer input. Unfortunately, this purely implicit approach is not yet fruitful for the large-scale functional programs we are interested in.
A promising approach that has been adopted by several researchers is to delegate most management tasks to the runtime system, but to allow the programmer the opportunity to give advice on a few critical aspects. This is the approach we have adopted for Glasgow Parallel Haskell (GpH), a simple extension of the standard non-strict functional language Haskell [Peterson et al., 1996] to support parallel execution.
In GpH, the runtime system manages most of the parallel execution, only requiring the programmer to indicate those values that might usefully be evaluated by parallel threads and, since our basic execution model is a lazy one, perhaps also the extent to which those values should be evaluated. We term these programmer-specified aspects the program's dynamic behaviour. Even with such a simple parallel programming model we find that more and more of such code is inserted in order to obtain better parallel performance. In realistic programs the algorithm can become entirely obscured by the dynamic-behaviour code.