DESIGN AND EMULATION OF A PARALLEL DATA-DRIVEN LISP MACHINE

Abstract

The exploitation of parallelism at all levels of the computer architecture has been a key method that complemented technological advances in electronics to achieve ever increasing performances of computers. Diverse architectural models and techniques have been proposed to realise high-speed supercomputing. Two such architectures arc the dataflow model and the reduction model of program execution. Specialised machines have also been developed to support list-processing languages, since these languages are unable to be effectively supported on traditional von Neuman computers due to semantic differences between them. BIDDLE is one such specialised machine designed to support fast parallel execution of Lisp, incorporating in it ideas from the dataflow and reduction model. In BIDDLE, Lisp programs are first preprocessed into an internal form to enable more efficient program execution. During execution, a program is reduced into simpler forms until expressions which are non-reducible instructions are encountered. The reduction process builds an execution tree with bidirectional links between instructions and the expressions generating their required results. Instructions arc executed in the data-driven manner. The execution tree changes dynamically as portions of the program are expanded and are added to the tree while some branches of the tree execute and are purged off. A priority mechanism controls the execution priorities of different branches of conditional statements to limit speculative evaluation when system workload is high, as well as to purge those branches whose evaluation arc found to be unnecessary and to increase the priorities of those branches that are determined to be required. Parallelism in programs is specified by the programmer using the FUTURE construct. The machine supports instructions that can have side-effects. Hence, we designed a mechanism to sequentialise the execution of branches that are not parallely executable with each other. A Lisp expression is executable only if it is given environment access rights. Environment access rights arc passed through the execution tree in post-order, with every branch preceded with the FUTURE construct having a separate access right. Environment information of every function invocation are each captured in separate argument objects. Static and dynamic links arc maintained between argument objects to reflect the static and dynamic environment of functions. Support for Lisp execution, namely tagged data types and garbage collection are also incorporated. To support concurrent program execution, BIDDLE has several clusters of processors, with each cluster having its own memory store and a number of processing elements. Large data structures created are stored into these memory store and may be distributed across several memory stores. An emulation of BIDDLE architecture has been implemented on an array of transputers, enabling us to test the performance of the system using actual parallel processors. Results obtained from the execution of test programs on the emulator has offered much insight into the execution characteristics of the system. Based on the insights obtained, proposals for modifications to improve the design are made and are reported in this thesis.