Downloads & Free Reading Options - Results

This dissertation considers several issues in the execution of Lisp programs on shared-memory multiprocessors. An overview of constructs for explicit parallelism in Lisp is first presented. An overview of constructs for explicit parallelism in Lisp is first presented. The problem of partitioning a program into process and scheduling these processes are then described, and a number of methods for performing these are proposed. These include cutting off process creation based on properties of the computation tree of the program, and basing partitioning decisions on the state of the system at runtime instead of the program. An experimental study of these methods has been performed using a simulator for parallel Lisp. This is followed by a description of the experiments that were performed and an analysis of the results. Two programs are used as illustrations-a Fast Fourier Transform, which has an abundance of parallelism, and the Cocke-Younger-Kasami parsing algorithm, for which good speedup is not as easy to obtain. The difficulty of using cutoff-based partitioning methods, and the differences between various scheduling methods, are shown. A combination of partitioning and scheduling methods which we call dynamic partitioning is analyzed in more detail. This method is based on examining the machine's runtime state; it requires that the programmer only identify parallelism in the program, without deciding which potential parallelism is actually useful. We conclude that for programs whose computation trees have small height relative to their total size, dynamic partitioning can achieve asymptotically minimal overhead in the cost of process creation. (AW)

"This report is the text of a paper to be presented in May, 1987, at the Second International Conference on Supercomputing."

CSIM is a simulator for parallel Lisp, based on a continuation passing interpreter. It models a shared-memory multiprocessor executing programs written in Common Lisp, extended with several primitives for creating and controlling processes. This paper describes the structure of the simulator, measures its performance, and gives an example of its use with a parallel Lisp program. Keywords: MIMD (Multiple Instruction Multiple Data).

In spite of the great interest in speeding up programs by using parallelism, few convenient parallel machines are available, and those may not have the types of parallelism that might be of most benefit. This paper describes a simulator, written in Common Lisp, that provides a method for experimenting with varying amounts of explicit (programmer-specified) parallelism, and gathering information about the efficiency of such programs if they were to be run on a parallel processor. The system chosen for simulation is Multilisp (7,8). Its parallel constructs are quite simple, and rely heavily on the programmer to decide on their efficient and correct use. Multilisp is explained in a later section of this paper; however, a working knowledge of some dialect of LISP is assumed.