Lazy Tree Mapping:
Generalizing and Scaling
Deterministic Parallelism

Yu Zhang
University of Science and Technology of China

Bryan Ford
Yale University

4th Asia-Pacific Workshop on Systems (APSYS 2013)
July 30, 2013


Many parallel programs are intended to yield deterministic results, but unpredictable thread or process interleavings can lead to subtle bugs and nondeterminism. We are exploring a producer-consumer memory model—SPMC—for efficient system-enforced deterministic parallelism. However, the previous eager page mapping wastes physical memory, and cannot support large-size and real applications. This paper presents a novel lazy tree mapping approach to the model, which introduces “shadow page table” for allocating pages “on demand”, and extends an SPMC region by a tree of lazily generated pages, representing an infinite stream on reusing a finite-size of virtual addresses. We build DLINUX to emulate the SPMC model entirely in Linux user space to make the SPMC more powerful. DLINUX uses virtual memory to emulate physical pages, and sets up page tables at user-level to emulate lazy tree mapping. Atop the SPMC, DetMP and DetMPI are explored and integrated into DLINUX, offering both thread- and process-level deterministic message passing programming. Experimental evaluations suggest lazy tree mapping improves mem- ory use and address reuse. DLINUX scales close to ideal with 2048*2048 matrices for matmult, and better than MPICH2 for some workloads with larger input datasets.

Paper: PDF


This work was supported in part by the National High Technology Research and Development Program of China (863 Program) grant (No.2012AA010901), and the National Natural Science Foundation of China grant (No.61229201).