Parallel lisp compilation for distributed systems

Abstract

The advent of high speed VLSI CMOS chips has made low cost parallel processing feasible. To use parallel computers efficiently for symbolic computing, both an expressively powerful parallel symbolic language, e.g. parallel Lisp or Prolog, and its efficient implementation are required. This paper reports the effort of building a compiler for BaLinda Lisp, a parallel Lisp dialect, on distributed-memory multiprocessors. BaLinda Lisp supports the construct to initiate parallel execution threads, speculative computation to spawn parallel tasks for results that may be required, and Linda tuplespace operations to enforce proper communication and synchronization. The compiling of BaLinda Lisp consists of several passes and generates code for an intermediate abstract machine. We will show how the salient features of BaLinda Lisp could be fully described by lower-level abstract machine instructions and will explain the abstract machine and its instruction set. The execution model is based on group managing, allowing processors to form groups of different sizes in order to distribute the execution control mechanism. Experiments are carried out on a network of up to 18 transputers in various configurations. The results show that the compiler generates efficient code for sequential BaLinda Lisp programs and, following upon this, parallel BaLinda Lisp programs could run much faster such that reasonable speedup could be achieved in most situations.