A Parallel Functional Database on GRIP

Gert Akerholt Kevin Hammond Simon Peyton Jones Phil Trinder?

April 23, 1992

Abstract

GRIP is a shared-memory multiprocessor designed for efficient parallel evaluation of functional languages, using compiled graph reduction. This paper investigates the feasibility of processing persistent data on GRIP, and presents results obtained from a pilot implementation. A database implemented in a pure functional language must be modified non-destructively, i.e. the original database must be preserved and a new copy constructed. The naive implementation provides evidence for the feasibility of data processing in the form of modest real-time speed-ups, and acceptable real-time performance. The functional database is also used to investigate the GRIP architecture, compared with an idealised machine. The particular features investigated are the thread-creation costs and caching of GRIP's distributed memory.

1 Introduction

Multiprocessor machines potentially provide considerable computing power cheaply. Because they typically have large memories, multiprocessors are a particularly attractive choice for implementing data- or transaction-processing applications. It is believed that pure functional languages are easily made concurrent and hence particularly suitable for programming multiprocessors. Indeed, there are now several declarative multiprocessors, i.e. machines specifically designed to evaluate functional languages in parallel [3, 7, 8, 19].

There are many research issues which remain to be resolved for multiprocessor machines, for example locality, granularity, throttling and load balancing. Data processing poses an additional challenge for declarative systems because data structures must be modified non-destructively, that is, the original structure must be preserved and a new copy constructed. Because of the high cost of non-destructive update the designers of the Flagship declarative multiprocessor provided sideeffecting transactions as operating-system primitives. The Flagship machine has achieved some impressive transaction-processing results [23]. However, the side-effecting transactions made the semantics of programs complex, reasoning about programs difficult and evaluation-order significant.

An alternative purely-functional approach based on creating versions of trees was proposed in [1]. Essentially only a path from the root to the site of the update needs to be duplicated | the unchanged parts can be shared by the original tree and the new tree. Encouraging results were obtained for the simulated parallel evaluation of a prototype database using this approach [25, 26].

?This work is supported by the SERC GRASP and Bulk Data Types Projects. Authors' address: Computing Science Dept, Glasgow University, Glasgow, Scotland. Email: fkh,simonpj,[email protected]