An Efficient Garbage Collection Scheme for Parallel Computer Architectures

Watson, P; Watson, I

doi:10.1007/3-540-17945-3_25

An Efficient Garbage Collection Scheme for Parallel Computer Architectures

Lookup NU author(s): Professor Paul Watson ORCiD

Downloads

Full text for this publication is not currently held within this repository. Alternative links are provided below where available.

Abstract

A large amount of work has been undertaken in recent years on the design of garbage collection schemes for parallel computers. This has been largely driven by the need for an efficient scheme to reclaim the redundant parts of the computational graphs produced when programs written in Declarative Languages [DARL8] are evaluated by graph reduction [WATS86] [KELL84] [KIEB85]. Garbage Collection is especially important in implementations of declarative languages, as they tend to consume new storage locations at a much higher rate than do conventional programming languages. In conventional languages, computation is performed by repeatedly changing the 'state' of the computation, as represented by the contents of fixed storage locations (variables). In Declarative languages there is no concept of state, and any re-use of storage locations must be achieved by garbage collection, rather than by the program itself. Without an efficient scheme to allow the re-use of store locations holding redundant parts of the computational graph, the amount of storage required to run programs would be unacceptably high. Parallel computers add to the problem of Garbage Collection, usually by introducing the need for synchronisation in the Garbage Collection schemes. This can have a major effect on the efficiency of Garbage Collection. The paper examines the problems of garbage collection on parallel machines, and proposes a new scheme which has been implemented on the Flagship parallel machine architecture [WATS87]. It is efficient because it requires no synchronisation.