The theory, design, and fabrication of an alternating sequential/parallel Lisp machine (ASPLM) is described. The ASPLM provides an environment for symbolic computation, capable of solving artificial intelligence problems using parallel algorithms.; The ASPLM is an innovative hardware/software system, resulting from the integration of the following new ideas: an extensible hardware architecture which directly supports the alternating sequential/parallel (ASP) methodology, a coordinated garbage collection mechanism for multicomputers, an efficient Lisp identifier-passing scheme, a tokenized protocol for the transmission of symbolic Lisp expressions, and Lisp language extensions which support parallel programming.; This dissertation covers the following topics:; Background. The critical decisions in designing the ASPLM architecture were based on a survey of existing parallel computer architectures. A comparison between the ASPLM and other modern Lisp machine architectures demonstrates the relevance and importance of this research.; ASPLM architecture. The fundamental components of the ASPLM architecture are described. The host-slave communications scheme, which shows how symbolic expressions can be efficiently processed on this architecture, is presented.; Hardware design. Important aspects of the ASPLM hardware organization are discussed. A complete description of the host computer, the host interface, the bus repeater, and the slave processors is provided. Schematic diagrams and photographs of the ASPLM hardware are included.; Software design. An analysis of the software organization reveals the close interrelationships between the various component modules which constitute the ASPLM Lisp system. The ASPLM Lisp system software is written in the 'C' language and 68000 assembler. All source code is included.; Parallel language. Parallel function extensions to the Standard Lisp language were created to support the ASP methodology at the Lisp programming level.; Performance measurement. Two traditional example problems are solved using programs developed for the ASPLM. Execution data demonstrates the performance advantages of the ASPLM architecture. A new performance parameter, activity, characterizes the relative communications traffic. The speedup, efficiency, and activity all approach theoretical limits of parallel performance enhancement as problem size increases.; Future research. The hands-on experience gained by creating the ASPLM inspired several architectural ideas for designing future parallel Lisp machines.
展开▼
