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
Abstract
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
Funding
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).