ZLISP--a portable parallel LISP environment

Candidate: Dimitrovsky,Isaac Aaron

Abstract

This thesis concerns ZLISP, a portable parallel LISP environment for shared memory MIMD supercomputers. ZLISP was created as a vehicle for experimenting with parallel symbolic computing on a variety of supercomputer designs. It is a small but reasonably powerful subset of COMMON LISP that includes arrays, strings, structures, most of COMMON LISP's control flow functions, and a native code compiler, among other features. A low-level, flexible set of parallel primitives is provided that can support a wide spectrum of parallel programming styles. ZLISP currently runs on the NYU Ultracomputer prototype. A version that simulates parallelism runs on VAX and SUN minicomputers. I begin this thesis by discussing ZLISP's design and implementation. I attempt to justify the more difficult design decisions made during the development of ZLISP. I also give some details on how the more unusual parts of ZLISP are implemented. The full ZLISP reference manual is included as an appendix. I then turn to some parallel algorithms of independent interest that were discovered during the development of ZLISP. Many of these algorithms use the faa (fetch-and-add) operation, a versatile low-level synchronization primitive that has been promoted by the NYU Ultracomputer group and incorporated in several other supercomputer designs. I first describe some of the parallel algorithms used to implement ZLISP. These include an algorithm for parallel garbage collection and an algorithm for efficiently using hash tables in a parallel garbage collected environment. Finally, I cover some parallel algorithms provided for use by ZLISP programmers. I define the group lock, a new synchronization primitive useful in writing asynchronous parallel algorithms, and give some examples of its use in such applications as parallel stacks, heaps, and databases. I also present an assortment of space efficient parallel data structures such as queues, multiqueues, and stacks.