Abstract
This paper introduces CCLISP (Concurrent Common LISP), a distributed software environment designed to bring the high-level productivity of Common LISP to the Intel iPSC hypercube supercomputer. By extending LISP with message-passing "streams" and remote evaluation capabilities, the authors demonstrate how symbolic AI applications can overcome the limitations of uniprocessor workstations. The evaluation shows that symbolic tasks can achieve significant performance gains—including superlinear speedups—across parallel processor nodes.
Introduction: The Symbolic AI Bottleneck
In the mid-1980s, symbolic AI researchers encountered a significant hardware barrier. The complexity of their problems began to exceed the capacity of standard uniprocessor workstations, such as the Symbolics 3600 or Xerox 1108. While concurrent computers like the Intel iPSC offered massive raw power through a hypercube architecture of interconnected 80286 processors, they were notoriously difficult to program, typically requiring low-level languages like C or FORTRAN.
The challenge addressed by this research was to create a software environment that maintained the "friendly" features of LISP—interpreters, editors, and dynamic typing—while providing a robust framework for managing communication and task distribution across hundreds of independent nodes.
The CCLISP Environment
The authors developed CCLISP, a distributed environment where each node on the iPSC runs its own complete Common LISP system. To facilitate coordination between these nodes, several key abstractions were introduced:
- Node Streams: These extend the traditional LISP I/O stream metaphor to network communication. Sending data to another processor is syntactically similar to writing to a file or terminal.
- FASL Streams: A specialized, high-speed variant of node streams designed specifically for moving compiled code and complex LISP objects between nodes.
- Remote Evaluation: This mechanism allows a programmer to send a LISP expression (a "form") to a remote node for execution. This can be performed synchronously (the sender waits for a result) or asynchronously (the sender continues working while the remote node processes the task).
- Hybrid Applications: CCLISP supports communication between LISP nodes and nodes running C or FORTRAN, enabling applications that combine symbolic logic with heavy numeric vector processing.
Performance Evaluation
The authors evaluated CCLISP using the Gabriel LISP Benchmarks, the industry standard for measuring LISP performance. They focused on three specific benchmarks to test parallelization: Triangle (a peg-solitaire search), Browse (database search and pattern matching), and Puzzle (combinatorial block-packing).
Triangle Benchmark Results
The Triangle benchmark, which involves finding all solutions to a search problem, proved highly amenable to parallelization. Because the problem requires an exhaustive search of every branch, the workload can be distributed effectively across nodes.
As shown in the data, the system achieved a 14.8x speedup on 16 nodes and a 27.6x speedup on 32 nodes. Notably, a single iPSC node performed roughly on par with a Xerox 1108 Dandelion workstation.
Key Insights: Superlinear Speedup and Search Strategies
One of the most significant findings occurred during the Browse benchmark. The authors observed "superlinear speedup," where 16 processors were more than 16 times faster than a single processor.
This phenomenon was not an error but a result of distributed memory architecture. By splitting the database across multiple nodes, each node maintained a much smaller memory footprint. This drastically reduced the time spent on Garbage Collection (GC), a notorious performance bottleneck in LISP systems. Once tuned to minimize non-computational overhead, the benchmark demonstrated a speedup of 26.6x on 16 nodes.
However, the research also highlighted that search strategy is critical. While "all-solution" problems like Triangle parallelize well, "first-solution" problems like Puzzle are much harder to optimize. In Puzzle, one node might find the answer early, rendering the work of other nodes redundant. Consequently, Puzzle only showed a 2x speedup on 16 nodes.
Limitations and Future Work
Despite the success of CCLISP, several hurdles remain for concurrent AI:
- Single-Solution Search: Developing efficient parallel algorithms for finding a single result in a massive search tree remains a primary research issue.
- Manual Decomposition: CCLISP provides the tools for concurrency, but the programmer must still manually decide how to partition the problem. Automatic parallelization by a compiler remains the "holy grail."
- Scaling: While the architecture theoretically supports thousands of nodes, this study only demonstrates results up to 32 nodes. The behavior of symbolic systems at a massive scale remains a question for future hardware generations.
Summary updated