A virtual memory foundation for scalable deterministic parallelism

Yu Zhang, Bryan FordAPSys 2011 · DOI

TL;DR

This paper introduces SPMC (Single-Producer Multiple-Consumer) virtual memory, a novel OS foundation that enables deterministic parallel programming without the scalability bottlenecks of traditional hierarchical synchronization. By building a user-level message passing API (DetMP) on top of SPMC, the authors demonstrate significant speedups in parallel benchmarks like matrix multiplication and integer sorting, while guaranteeing deterministic execution.

What Problem Does This Paper Address?

Developing parallel programs that are both efficient and deterministic (meaning they produce the same output every time for the same input) is a long-standing challenge. While deterministic execution is crucial for reliable debugging, fault tolerance, and security, existing approaches often suffer from poor scalability. This is primarily due to synchronization models that are strictly hierarchical (like fork/join) or rely on serialized thread scheduling, which inherently limit how many processors can be effectively utilized. These limitations prevent parallel programs from fully leveraging modern multi-core architectures.

Methods

The core innovation is the SPMC (Single-Producer Multiple-Consumer) virtual memory foundation. This extends the existing Determinator microkernel by introducing a new type of memory region. In an SPMC region, a single process acts as the "producer," writing data, while multiple other processes can act as "consumers," reading that data.

Key aspects of the SPMC approach:

  • Virtual Memory Integration: SPMC regions are managed at the virtual memory level, allowing for efficient page-based data sharing.
  • Non-Hierarchical Synchronization: Unlike previous models, SPMC allows "peer-to-peer" communication, bypassing the need for a common ancestor process to mediate all communication.
  • Deterministic Guarantees: The kernel enforces strict rules: consumers cannot read a page until the producer explicitly "fixes" it, ensuring that data is available and consistent before being accessed.
  • DetMP API: Built on top of SPMC, DetMP is a user-space library that provides an MPI-like message passing interface. It offers familiar collective communication operations (like barrier, broadcast, scatter, gather) but maps them onto SPMC channels, ensuring deterministic semantics.

Datasets

The paper evaluates its approach using two well-known benchmarks:

  • Matrix Multiplication (MM): A common benchmark for parallel computation.
  • Integer Sorting (IS): Specifically, the IS benchmark from the NAS Parallel Benchmarks (NPB3.3-MPI).

These benchmarks are used to compare the performance and scalability of DetMP (running on the SPMC foundation) against existing deterministic (DetSM) and non-deterministic (Linux MPI) implementations.

Key Insights and Ideas

  • Virtual Memory as a Synchronization Primitive: The paper demonstrates that virtual memory mechanisms, typically used for memory protection and management, can be powerfully repurposed to build efficient and deterministic inter-process communication primitives.
  • Breaking Hierarchical Bottlenecks: By enabling peer-to-peer communication via SPMC, the system effectively removes a major scalability bottleneck present in many prior deterministic parallel systems.
  • Bridging Shared Memory and Message Passing: DetMP, built on SPMC, offers the convenience of message passing while allowing for efficient sharing of read-only data, blurring the lines between traditional shared-memory and message-passing models.
  • Scalability with Determinism: The results show that it's possible to achieve good parallel speedup even when strict deterministic guarantees are enforced, challenging the notion that determinism inherently sacrifices performance.

Key Results

  • Matrix Multiplication (MM): DetMP atop SPMC achieved near-ideal speedup and scaled better than the original deterministic shared-memory model (DetSM) on the Determinator kernel.
  • Integer Sorting (IS): IS implemented with DetMP showed strong scalability, offering 110% of the speedup of IS running on Linux MPI with 2 CPUs, and 97% and 78% of Linux MPI's speedup on 4 and 8 CPUs, respectively. Crucially, IS-DetMP guarantees determinism, which Linux MPI does not.
  • Communication Overhead: For the IS benchmark, communication time as a percentage of total execution time was lower in DetMP compared to Linux MPI, especially as the number of threads increased.

Limitations and Future Work

  • Prototype Implementation: The authors acknowledge that the prototype is early and incomplete, suggesting that further optimization is possible.
  • QEMU Environment: Preliminary results were run within QEMU, which may introduce its own overheads and limitations (e.g., Ubuntu only utilizing up to 8 CPUs).
  • Future Directions: The authors envision SPMC as a foundation for supporting various parallel programming models (both shared memory and message passing) and high-performance deterministic I/O. They also plan to explore more efficient channel implementations and other parallel programming models atop SPMC.

Summary updated

BibTeX
@inproceedings{zhang2011virtual,
  author = {Yu Zhang and Bryan Ford},
  title = {{A virtual memory foundation for scalable deterministic parallelism}},
  booktitle = {APSys},
  year = {2011},
  doi = {10.1145/2103799.2103808},
}
Figure