© 1987 by British Computer Society
Combinator Reduction in a Shared-memory Multiprocessor
CERN, CH-1211 Geneva 23, Switzerland
A parallel combinator reduction machine for a shared-memory multiprocessor is described. The system, called Prism, uses a graphical internal representation and features a de-centralised scheduling algorithm which is independent of the number of processors available. The system was built to support lazy evaluation, with emphasis on the extraction of parallelism at the lowest expression level, here termed microparallelism. Results are presented which show that typical programs do not exhibit sufficient microparallelism to make this approach generally worthwhile. The system was therefore modified to incorporate simultaneous evaluation of list elements, and performance was then significantly improved with typical programs being able to employ usefully up to four processors. Direct shared memory is presented as being an ideal architecture for the exploitation of parallelism on this scale.
The major conclusions of this work are that the Prism approach is effective for the implementation of applicative languages on conventional D.S.M. multiprocessor architectures, but lazy evaluation and data structuring based on the list largely nullify any potential for parallelism. As a consequence, it is suggested that higher-level data structures such as sets, in conjunction with eager evaluation strategies, would be more appropriate for the parallel implementation of applicative languages.
Received November 1984. revised April 1986.
* UMIST, P.O. Box 88, Manchester M60 1QD, U.K.
Present address: Cern, CH-1211 Geneva 23, Switzerland.