This research was supported by the United States Air Force Command, Rome Air Development Center, under contract number F30602-83-K-0119.


Projects in the past few years have looked into the problem of automatic parallelization of the Lisp programming language. Since it appears to be feasible to adapt Lisp to run on a general parallel computer, an implementation will be developed. This implementation will be as general as possible in order to locate the tradeoffs between implementing Lisp on a general parallel computer versus having an efficient interpreter. This implementation can be used to study the execution characteristics of Lisp in a parallel environment. It can also be used to derive information about architectural features which affect the performance of Lisp on parallel machines. This implementation will use a multitasking system and interprocess communication to simulate an MIMD machine. The implementation will include the formation, queuing, distribution, and execution of dataflow frames. Realistic Lisp application programs will be used with the implementation to examine the feasibility and efficiency of parallel Lisp. Measurements derivable from the simulator include number of processor cycles, processor utilization, memory requirements, and speedup. These tests will provide two main results. First, they will indicate possibilities for further gains by illustrating the bottlenecks in such a scheme. Second, they will help determine if it is indeed feasible to run Lisp on a parallel machine or if instead the overhead is too high for the application to be profitable. Most likely, some parallelism will be profitable. The simulation will provide information on the extent to which parallelism can be utilized.

Date of this Version