Parallel Lisp with speculation and subtuplespace on distributed systems

The advent of high speed VLSI CMOS chips has now made low cost parallel pro cessing feasible. To use parallel computers efficiently for symbolic comput ing, both an expressively powerful parallel symbolic language, e.g. paralle l Lisp or Prolog, and its efficient implementation are required. This paper reports on our effort in building a compiler and a runtime system for BaLi nda Lisp, a parallel Lisp dialect with speculation and global or speculativ e subtuplespace, on distributed-memory multiprocessors. BaLinda Lisp suppor ts constructs to initiate parallel execution threads, speculative computati on to spawn parallel tasks for results that may be required, and Linda tupl espace operations to enforce the proper communication and synchronization. Our implementation compiles BaLinda Lisp into instructions of an abstract m achine. The abstract machine adopts a group managing execution model, suita ble for machines with a scalable distributed architecture, allowing process ors to form groups of different sizes in order to distribute the execution control mechanism, i.e. load balancing, tuplespace distribution and specula tive task management. Experiments are carried out on a network of up to 18 transputers in various configurations. The experiment results show that wit h the compiler and run-time system, parallel BaLinda Lisp programs achieve reasonably good speedup and efficiency.