PROCESSING TRANSACTIONS ON GRIP,
A PARALLEL GRAPH REDUCER

G. AKERHOLT, K. HAMMOND, S. PEYTON JONES AND P. TRINDER

To appear in Proc. PARLE '93, Munich, June 1993.

Abstract. The GRIP architecture allows efficient execution of functional programs on a multi-processor built from standard hardware components. State-ofthe-art compilation techniques are combined with sophisticated runtime resourcecontrol to give good parallel performance. This paper reports the results of running GRIP on an application which is apparently unsuited to the basic functional model: a database transaction manager incorporating updates as well as lookup transactions. The results obtained show good relative speedups for GRIP, with real performance advantages over the same application executing on sequential machines.

1. Introduction

GRIP is a parallel processor designed for fast, efficient execution of pure functional programs. Good sequential compiler technology is combined with parallel runtime support to give good real-time performance. Pure functional languages form an attractive basis for parallel implementation, if a safe evaluation strategy such as parallel graph reduction is used:

ffl The principle of referential transparency ensures that all cached copies of a given object will have the same value when evaluated, whether or not they are shared, and no matter how many times they are evaluated. Thus, there can be no cachecoherency problems in a parallel functional implementation.
ffl The semantics of a functional program remains the same whether it is executed sequentially or in parallel. Thus, a parallel functional program may be debugged on a sequential machine without affecting its result. There can be no unexpected non-determinism in a parallel functional program.
ffl There is no possibility of deadlock. Parallel functional programs have exactly the same termination properties as their sequential counterparts.
ffl Because there is no explicitly sequential evaluation order, it is easy to automatically partition a functional program for parallel execution.
ffl Automatic resource-control is much more straightforward, since there are no hidden dependencies between tasks.

A number of pragmatic issues remain, however, for example whether good partitions into tasks can be made without human intervention, or whether dynamic control decisions

This work is supported by the ESPRIT FIDE Project (BRA 3070), the SERC Bulk Data Type Constructors Project, the SERC GRASP Project and the Royal Society of Edinburgh. Authors' address: Computing Science Dept, Glasgow University, Glasgow, Scotland. Email: fakerholg, kh, simonpj,trinderg@dcs.glasgow.ac.uk