CCLISP™ on the iPSC™ Concurrent Computer

David Billstrom, Joseph Brandenburg, John TeeterAAAI 1987

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.

Performance of the Triangle benchmark across different iPSC node configurations compared to the Symbolics 3600.

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.

Performance of the Browse benchmark, highlighting the superlinear speedup achieved through distributed memory and reduced garbage collection overhead.

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:

  1. Single-Solution Search: Developing efficient parallel algorithms for finding a single result in a massive search tree remains a primary research issue.
  2. 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."
  3. 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

BibTeX
@inproceedings{billstrom1987cclisptm,
  author = {David Billstrom and Joseph Brandenburg and John Teeter},
  title = {{CCLISP™ on the iPSC™ Concurrent Computer}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1987},
}
Figure