Parallelisations

This section covers the kind of automatic parallelisation that may be possible using the information gleaned from these programs.

Function Call Parallelism

Two or more function calls are distributed to separate processors. This requires the analyser to spot when the data read and written by each call does not clash. We can produce FSA descriptions of the data accessed by each function call. Note that this information may be inaccurate, since there may be conditional data accesses that depend on run-time information. However, it will be conservative, in the sense that the actual set of data will be a subset of that computed. This is the type of parallelism that is being extracted in [Fea98], using the EARTH-C language.

Fine Grained Parallelism

Individual statements are scattered across processors. This requires knowledge about the dataflow dependencies between different statements. We can produce this information for restricted programs with static control, any improvement will require the fuzzy approach given in [CC96].

The `function call' approach has been explored using a parallel language called `Cilk' [Lei]. Cilk is a multi-threaded language based on ANSI C. It adds the keywords spawn and sync, for spawning and synchronising parallel function calls (threads). The threads operate in shared memory, so spawned function calls must operate on discrete sets of data, or the outcome of the computation will be uncertain and probably undesirable.

Cilk comes with a tool called the `Nondeterminator' which, given a cilk program and the data on which it operates, tests for possible data conflicts in spawned threads. The answers received are approximate, for the given data set.

Our aim has been to decide where, if anywhere, we can insert spawn and sync commands, given a program in our reduced language. This is solved when we can produce descriptions of all the data nodes accessed by a particular function call. This is an amalgam of the def and use FSAs described previously. Initial results for the code analysed so far show that there is always some dependency between function calls from the same function. A more feasible future approach is to unroll the functions to a particular depth and look for independent calls from more than one function.