Experiments with a transputer‐based parallel graph reduction machine
Fethi Rabhi, Gordon A. Manson · Concurrency Practice and Experience · 1991
Abstract This paper is concerned with the implementation of functional languages on a parallel architecture, using graph reduction as a model of computation. Parallelism in such systems is automatically derived by the compiler but a major problem is the fine granularity, illustrated in Divide‐and‐Conquer problems at the leaves of the computational tree. The paper addresses this issue and proposes a method based on static analysis combined with run‐time tests to remove the excess in parallelism. We report experiments on a prototype machine, simulated on several connected INMOS transputers. Performance figures show the benefits in adopting the method and the difficulty of automatically deriving the optimum partitioning due to differences among the problems.