The ButterflyTM Lisp System

Seth A. Steinberg, Donald C. Allen, Laura Bagnall, Curtis ScottAAAI 1986

TL;DR

This paper introduces Butterfly Lisp, a parallel Common Lisp system designed for BBN's Butterfly multiprocessor. It tackles the challenge of efficiently executing symbolic computations on parallel hardware by introducing a novel "future" construct for managing concurrency and a parallel garbage collector, enabling significant speedups for symbolic algorithms.

What Problem Does This Paper Address?

For decades, computational power has been primarily driven by advancements in numeric algorithms. However, the growing demand for symbolic computing, fueled by industries and research, has outpaced the capabilities of traditional, sequential Lisp machines. While multiprocessors offer a path to increased computational power, effectively harnessing them for symbolic tasks, which are often characterized by irregular data structures and dependencies, presents a significant challenge. Existing parallel systems, like the Uniform System, are optimized for numeric computations with regular structures. Butterfly Lisp aims to bridge this gap by providing a robust and efficient parallel programming environment for symbolic computations on the Butterfly multiprocessor.

Methods

The core of Butterfly Lisp's approach lies in its innovative use of the future construct. This mechanism allows a computation to be spawned in parallel without immediately blocking the caller. Instead, it returns a "future" object, a placeholder for the eventual result. If the result is needed before it's ready, the operation automatically suspends until the future is determined. This elegantly handles synchronization between parallel tasks.

The system also features a parallel garbage collector. Unlike serial garbage collectors, this one is designed to operate concurrently across multiple processors. When a processor runs out of heap space, it triggers a local garbage collection interrupt, which then initiates a global interrupt to synchronize all processors. The garbage collection process itself involves breaking down the heap into partitions, with processors concurrently scanning and copying objects from old to new space.

For memory management, Butterfly Lisp employs a striated heap, a composite of memory from all processors. This diffusion of data structures across nodes, combined with a garbage collector designed to maintain this diffusion, aims to minimize memory access contention, a critical issue in multiprocessor systems.

Datasets

Not discussed in the paper. The paper focuses on the system's design and implementation rather than specific benchmark datasets.

Key Insights and Ideas

  • The "future" construct is a game-changer for symbolic parallelism: It provides an elegant abstraction for synchronization, making parallel Lisp programs look remarkably similar to their sequential counterparts, thus lowering the barrier to entry for parallel programming.
  • Parallel garbage collection is essential for performance: For a system to effectively utilize a large number of processors, its memory management, particularly garbage collection, must also be parallelized to avoid becoming a bottleneck.
  • Minimizing memory contention is paramount: The Butterfly's architecture, with its shared memory and switch network, necessitates careful memory management to prevent processors from constantly retrying access to the same memory locations. Butterfly Lisp's striated heap and parallel GC are designed to address this.
  • Task granularity matters: The paper highlights that fundamental task units for parallelism should be on the order of 100-1000 instructions to ensure sufficient parallelism without excessive tasking overhead.

Key Results

The paper doesn't present extensive quantitative results but focuses on the system's design and capabilities. It demonstrates how a simple mapcar function can be parallelized with the addition of a single future form, illustrating the ease of introducing parallelism. The parallel garbage collector is described as being triggered when any processor runs out of heap space, with experiments indicating a relatively small difference (rarely more than 10%) in heap utilization among processors, suggesting good load balancing.

Limitations and Future Work

The authors acknowledge that Butterfly Lisp is currently interpreted, which, while adequate for development and experimentation, limits its performance potential. They are actively working on integrating a compiler to explore the performance benefits of compiled code in their parallel environment. Future work also includes further development of the user interface, with an emphasis on graphical debugging tools, and ensuring full compatibility with the Common Lisp standard. The system is envisioned as a testbed for exploring new data structures and procedural abstractions tailored for parallel symbolic computing.

Summary updated

BibTeX
@inproceedings{steinberg1986butterflytm,
  author = {Seth A. Steinberg and Donald C. Allen and Laura Bagnall and Curtis Scott},
  title = {{The ButterflyTM Lisp System}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1986},
}
Figure