Introduction
In the late 1980s, the transition from uniprocessor to multiprocessor systems introduced significant challenges for symbolic processing. Parallelizing Lisp was particularly difficult because it relies heavily on complex, interconnected data structures and is prone to "probabilistic bugs"—errors caused by improper synchronization and side effects. This paper details the evolution of Butterfly Lisp, a shared-memory parallel programming environment designed for the BBN Butterfly multiprocessor, which successfully scaled symbolic AI applications across up to 256 processor nodes.
System Architecture and Implementation
The system is built on the BBN Butterfly, a hardware architecture featuring up to 256 Motorola 68020 nodes. These nodes are connected by a high-performance logarithmic switching network that provides a unified view of memory across the entire system.
To maintain the "ease-of-programming" characteristic of Lisp while achieving high performance, the authors layered Common Lisp semantics over MIT CScheme. A key technical challenge was handling Common Lisp’s separate namespaces for functions and variables (Lisp-2) within Scheme’s single namespace (Lisp-1). This was resolved using a "syntaxer" that automatically mutates symbols during translation to S-code. Unlike message-passing systems, all 256 nodes share a single Lisp heap, allowing data to be communicated via pointers rather than expensive structure copying.
The "Future" Mechanism
Parallelism in Butterfly Lisp is primarily managed through the (future <expression>) construct, borrowed from MIT’s Multilisp. This mechanism allows a program to spawn a task and immediately return a placeholder known as an "undetermined future." The calling program only stalls if it attempts to access the value before the task has completed. This approach encourages an applicative (functional) programming style, significantly reducing the need for manual locks and semaphores that often lead to deadlocks.
Execution Imaging (BLUI)
One of the most significant contributions of this work is the Butterfly Lisp User Interface (BLUI), a tool designed to address the lack of observability in parallel systems. BLUI processes "metering packets" from the Butterfly to reconstruct a visual history of every task’s lifetime on a Symbolics Lisp Machine.
By plotting task histories as horizontal bars, the tool allows researchers to visually identify "clusters" of activity. For example, in the Boyer-Moore theorem prover benchmark, BLUI revealed that while the initial transformations were forced to be serial, subsequent stages branched into parallel sub-tasks. This level of detail was crucial for identifying performance bottlenecks like "task starvation," where processors sit idle because tasks are not being spawned quickly enough.
Performance and Results
The authors evaluated the system using classic symbolic benchmarks, including the Boyer-Moore Theorem Prover and Recursive Fibonacci. Key results include:
- Scalability: The Butterfly switch allows bandwidth to grow almost linearly with the number of nodes. A 256-node system achieved approximately 250 million instructions per second (MIPS).
- Memory Capacity: The system supported up to 1 gigabyte of shared memory, providing a massive workspace for 1987-era AI applications.
- Efficiency: Remote memory references took only ~4 microseconds regardless of system size, proving that Lisp’s pointer-heavy nature is highly compatible with parallel systems if the hardware switch is sufficiently fast.
Limitations and Future Work
Despite its successes, the system had limitations. At the time of publication, the LIAR compiler was still being ported, meaning most results were based on interpreted code. Furthermore, while "futures" simplify parallel programming, the developer still has to manually decide where to insert them. Future research directions included the automatic detection of circular dependencies and the optimization of task subtrees. Additionally, the software's performance was tightly coupled to the unique low-latency Butterfly switch, making it difficult to port to contemporary message-passing architectures.
Summary updated