A Virtual Memory Foundation for Scalable Deterministic Parallelism

Yu Zhang and Bryan Ford
Yale University

2nd ACM SIGOPS Asia-Pacific Workshop on Systems (APSys 2011),
July 11-12, 2011, Shanghai, China


Recent deterministic execution environments promise efficient program replay and bug reproduction, but their scalability is currently limited by strictly hierarchical synchronization models or serialized thread scheduling mechanisms. To address these issues, we introduce a single-producer multiple-consumer (SPMC) virtual memory foundation for deterministic parallelism, which supports non-hierarchical synchronization without serialized thread scheduling. An extension to the Determinator microkernel, supporting SPMC memory regions, offers threads and processes scalable “peer-to-peer” communication while preserving the kernel's existing guarantee of system-enforced determinism. DetMP, a deterministic user-level message passing API modeled on MPI, illustrates one way to build convenient application-level parallel programming abstractions atop the SPMC foundation. Preliminary results suggest that DetMP atop SPMC may be realistic and useful, achieving near-ideal speedup for parallel matrix multiplication, and good scaling for IS, in all cases ensuring strict determinism.

Paper: PDF

This research was supported by China's Fundamental Research Funds for the Central Universities, and by the U.S. National Science Foundation under grant CNS-1017206.