Distributed implementation of programmed graph reduction

Lecture notes in computer sciencePublished 1 January 1989

Rita Loogen, Herbert Kuchen, Klaus Indermark, Werner Damm

DOI10.1007/3540512845_37

Source URL

Citations38

SJR quartileQ2

SJR score0.35

SNIP0.55

TL;DR

The realization of programmed graph reduction in PAM — a parallel abstract machine with distributed memory is described and results of the implementation of PAM on an Occam-Transputersystem are given.

Abstract

Programmed graph reduction has been shown to be an efficient implementation technique for lazy functional languages on sequential machines. Considering programmed graph reduction as a generalization of conventional environment-based implementations where the activation records are allocated in a graph instead of on a stack it becomes very easy to use this technique for the execution of functional programs in a parallel machine with distributed memory. We describe in this paper the realization of programmed graph reduction in PAM — a parallel abstract machine with distributed memory. Results of our implementation of PAM on an Occam-Transputersystem are given.

Keywords

Computer Science

Lecture notes in computer scienceDistributed garbage collection using reference counting

139 Citations1987David Bevan

An elegant algorithm for the real-time garbage collection of distributed memory that makes use of reference counting and is simpler than distributed mark-scan algorithms and is also truly real- time unlike distributed mark -scan algorithms.

Efficient applicative data types

64 Citations1984Eugene W. Myers

This work treats the applicative manipulation of queues and stacks with the requirement that operations be free of side-effects, which makes it difficult to achieve efficient implementations.

ACM SIGPLAN NoticesEfficient compilation of lazy evaluation

53 Citations1984Thomas Johnsson

View PDF

IEEE Transactions on ComputersDistributed execution of functional programs using serial combinators

40 Citations1985Paul Hudak, Benjamin Goldberg

The authors describe a program transformation technique based on serial combinators that offers in some sense just the right granularity for this style of computing, and that can be fine-tuned for particular multiprocessor architectures.

Lecture notes in computer scienceEvaluation transformers — A model for the parallel evaluation of functional languages (extended abstract)

28 Citations1987Geoffrey Burn

A semantic criterion is given which ensures that a parallel machine may become swamped with the computation of the expressions whose values are not needed in order to produce the result from a program.

View PDF

Proceedings of the International Conference on Parallel ProcessingEFFICIENT DISTRIBUTED EVALUATION OF FUNCTIONAL PROGRAMS USING SERIAL COMBINATORS.

9 Citations1985Paul Hudak, Benjamin Goldberg

Informatik-FachberichteCompiled Graph Reduction on a Processor Network

8 Citations1988Martin N. Raber, T. Remmel +5 more

A parallel abstract machine for the implementation of functional languages on a processor network based on Th.

Lecture notes in computer scienceA simple abstract machine to execute supercombinators

1 Citations1987Jon Fairbairn

This paper gives a brief description of an abstract machine into which supercombinators may be compiled.