Parallel Functional Programming: An Introduction

Kevin Hammond?

Department of Computing Science, University of Glasgow, Glasgow G12 8QQ, U.K.

[email protected]

1 Introduction

Parallel functional programming has a relatively long history. Burge was one of the first to suggest the basic technique of evaluating function arguments in parallel, with the possibility of functions absorbing unevaluated arguments and perhaps also exploiting speculative evaluation [22]. Berkling also considered the application of functional languages to parallel processing [17].

Due to the absence of side-effects in a purely functional program, it is relatively easy to partition programs so that sub-programs can be executed in parallel: any computation which is needed to produce the result of the program may be run as a separate task. There may, however, be implicit control- and data- dependencies between parallel tasks, which will limit parallelism to a greater or lesser extent.

Higher-order functions (functions which act on functions) can also introduce program-specific control structures, which may be exploited by suitable parallel implementations, such as those for algorithmic skeletons (Section 3.2).

Here is a classic divide-and-conquer program, a variant on the naive Fibonacci program. Since the two recursive calls to nfib are independent, they can each be executed in parallel. If this is done naively, then the number of tasks created is the same as the result of the program. This is an exponentially large number (O(2n)).

nfib n = if n <= 1 then 1
else 1 + nfib(n-1) + nfib(n-2)

?Supported by a SOED Research Fellowship from the Royal Society of Edinburgh and the UK EPSRC Parade project.

1.1 Determinism

The semantics of a purely functional program define the result of that program for a fixed set of inputs. It follows that functional programs are deterministic in the following useful sense: any program which runs sequentially will deliver the same result when run in parallel with an identical input. Apart from possible resource starvation the parallel program will also terminate under exactly the same conditions. This level of determinacy is useful in several respects:

ffl Programs can be debugged to remove algorithmic bugs without needing a parallel machine. Since programming environments are generally better on sequential machines, and there are usually fewer time limitations on their use, this can be an important pragmatic concern. Performance problems must still be detected by actual (or perhaps simulated) parallel execution.

ffl The result of the program is independent of dynamic task scheduling, except in terms of memory exhaustion. Thus tasks can be executed in any desired order, with locking provided by the normal execution model.

ffl Deadlock is impossible, except in conditions where the sequential program would also fail to terminate due to cyclic dependencies [107].

There are some programs (e.g. branch-and-bound searches) where nondeterministic results are required. It is beyond the scope of this paper to consider nondeterminism in detail, but Section 5.1 contains some pointers to the literature.