Parallel Lisp with speculation and subtuplespace on distributed systems

Abstract

The advent of high speed VLSI CMOS chips has now 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 on our effort in building a compiler and a run-time system for BaLinda Lisp, a parallel Lisp dialect with speculation and global or speculative subtuplespace, on distributed-memory multiprocessors. BaLinda Lisp supports constructs to initiate parallel execution threads, speculative computation to spawn parallel tasks for results that may be required, and Linda tuplespace operations to enforce the proper communication and synchronization. Our implementation compiles BaLinda Lisp into instructions of an abstract machine. The abstract machine adopts a group managing execution model, suitable for machines with a scalable distributed architecture, allowing processors to form groups of different sizes in order to distribute the execution control mechanism, i.e. load balancing, tuplespace distribution and speculative task management. Experiments are carried out on a network of up to 18 transputers in various configurations. The experiment results show that with the compiler and run-time system, parallel BaLinda Lisp programs achieve reasonably good speedup and efficiency. © 1999 CRL Publishing Ltd.