Tim Lewis
Producing programs that runs efficiently on parallel computers is a difficult task and research into the problem falls into two basic areas.
My work is primarly involved with the second approach, but with a few nods to the first, in that the programmer is expected to augment the code with descriptions of the data structures that it uses.
Imperative languages, such as C, allow programmers to manipulate pointer-based structures. Thus a structure can contain a pointer to another structure of the same type, as one of its components. Such data structures are often called recursive , since the definition depends on itself, and the structure is not limited in size. Automatic parallelisers can often not deal with such structures effectively since there is little restriction on where the pointers point to. Thus linkages between different data nodes are not known, and hence dependencies between different parts of a program are difficult to predict.
Our approach is to force the programmer to describe the linkages in the structure more closely by declaring where each pointer may point. If we want to describe a general graph structure (such as a network of roads) there may not be enough regularity in it to allow for a very full description. We may just have to say that any node can be linked to any other by any edge. At the other extreme we could have a binary tree where each node is joined by two pointers left and right to two separate sub-trees. Somewhere between these two extremes are structures with sufficient regularity that they can be described and useful parallelising information about programs that use them can be extracted.