A TRANSPUTER-BASED PARALLEL LISP IMPLEMENTATION

Transputers are commonly used in low cost computation-intensive applications, such as image processing and signal analysis. Symbolic processing and AI applications on transputers require a different programming environment. This paper reports the effort made to implement BaLinda Lisp, a parallel Lisp dialect, on transputer arrays. BaLinda Lisp supports the FUTURE construct to initiate parallel execution threads, speculative constructs to spawn parallel tasks for results that may be required, and tuple space operations to enforce the proper communication, synchronization, mutual exclusion and shared variable access for parallel tasks. A suite of application programs has been tested on the resulting interpreter and some performance results are presented. The results demonstrate that the interpreter achieves realistic parallelism and provides a high speed symbolic processing environment on transputers. The implementation strategies are described in this paper, focusing on how to support the novel features of BaLinda Lisp. The advantages and disadvantages inherent in the transputer architecture that affect the design of the interpreter are also discussed.