Parallel Graph Reduction for Shared-Memory Architectures

Parallel graph reduction is a conceptually simple model for the concurrent evaluation of lazy functional programs. A program is represented by a heap-based graph which forms the primary means of communication and synchronisation between processors. Execution-driven simulation is used to study the behaviour of a set of benchmark parallel functional programs compiled with a highly-optimising compiler executing on a variety of multicache shared-memory implementations. Three forms of shared-memory are simulated: an ideal shared-memory is used to assess the scalability of the benchmark programs and to study their data sharing behaviour. A multicache shared-memory based on an invalidating coherency protocol similar to those used in commercial snooping-bus systems is also simulated. The memory access characteristics of parallel functional programs are found to have distinctive properties of importance to the design and optimisation of coherency protocols. A third shared-memory design which ta..