Source-linked AI summary
Efficient System-Enforced Deterministic Parallelism
Amittai Aviram, Shu-Chun Weng, Sen Hu, Bryan Ford
TL;DR
Parallel programs are difficult and costly to make deterministically repeatable, especially against buggy or malicious software. Determinator addresses this with a shared-nothing kernel and deterministic synchronization, plus an untrusted runtime that emulates familiar abstractions. Experiments suggest comparable performance and scalability for coarse-grained applications on multicore machines and clusters, while fine-grained parallelism and prototype limitations remain boundaries.
Problem
Parallel execution is difficult and costly to make precisely repeatable, while nondeterminism limits debugging, fault tolerance, accountability, and security uses.
Method
Determinator uses single-threaded shared-nothing address spaces, deterministic synchronization, and an untrusted user-level runtime to emulate familiar parallel and operating-system abstractions.
Results
Experiments suggest deterministic coarse-grained parallel applications can achieve comparable performance and scalability on multicore machines and across clusters.
Takeaways & Limitations
System-enforced deterministic execution is feasible for normal-case coarse-grained parallel applications with suitable kernel and runtime designs.
Takeaways & Limitations
The prototype has limited file-system capacity and legacy synchronization abstractions that remain semantically nondeterministic.
Abstract
from arXiv · showhide
Deterministic execution offers many benefits for debugging, fault tolerance, and security. Running parallel programs deterministically is usually difficult and costly, however - especially if we desire system-enforced determinism, ensuring precise repeatability of arbitrarily buggy or malicious software. Determinator is a novel operating system that enforces determinism on both multithreaded and multi-process computations. Determinator's kernel provides only single-threaded, "shared-nothing" address spaces interacting via deterministic synchronization. An untrusted user-level runtime uses distributed computing techniques to emulate familiar abstractions such as Unix processes, file systems, and shared memory multithreading. The system runs parallel applications deterministically both on multicore PCs and across nodes in a cluster. Coarse-grained parallel benchmarks perform and scale comparably to - sometimes better than - conventional systems, though determinism is costly for fine-grained parallel applications.
UNPUBLISHED DRAFT
The paper lists four authors.
- Amittai Aviram is listed as an author.
- Shu-Chun Weng is listed as an author.
- Sen Hu and Bryan Ford are also listed as authors.
1 Introduction
The paper motivates system-enforced determinism for reproducibility, debugging, fault tolerance, accountability, and security, then presents Determinator as a clean-slate operating system for enforcing it. Its design supports deterministic coarse-grained parallel execution with comparable performance and scalability, while fine-grained applications and prototype limitations remain important boundaries.
- Motivation: Deterministic execution makes bugs reproducible and supports record-and-replay debugging, fault tolerance, accountability, intrusion analysis, and timing-channel control.
- Motivation: Parallel nondeterminism complicates development and debugging, while logging internal events can cost orders of magnitude more than logging external inputs.
- Determinator: Determinator reruns multi-process computations with identical inputs to produce identical outputs without internal event logging, treating timing as privileged information.
- Design approach: The system addresses timing dependencies by isolating concurrent activities, using local names, one-to-one synchronization, controlled time access, and application-level scheduling.
- Design approach: The clean-slate kernel exposes minimal abstractions and limited API compatibility, while an untrusted user-level runtime builds familiar operating-system abstractions above it.
- Results and scope: Experiments suggest comparable performance and scalability for coarse-grained parallel applications, but high fine-grained costs and prototype limitations constrain broader use.
- Contributions: The paper contributes five OS design principles, user-space constructions of familiar abstractions, and a system enforcing deterministic multi-process execution for some coarse-grained applications.
2 The Determinator Kernel
The kernel design explores principles and a low-level API for deterministic execution rather than claiming a definitive kernel design. The principles address known timing dependencies and are sufficient for Determinator’s guarantee, though the list is explicitly incomplete.
- Determinator’s kernel design principles and low-level API are intended to support higher-level user-runtime abstractions, not direct use by normal applications.
- The paper presents the API as an exploration of design challenges and strategies, without claiming it is the right determinism-enforcing kernel design.
- The five principles address known timing-dependency sources and suffice for Determinator’s deterministic-execution guarantee, but are not claimed to be complete or conclusive.
1. Isolate the working state of concurrent activities
Determinator isolates concurrent activities in private spaces and replaces shared, timing-dependent interactions with explicit deterministic synchronization. Its minimal kernel API supports controlled communication, execution, and distribution while preserving determinism.
- Isolation: Concurrent activities run in private sandboxes and interact only at deterministically defined synchronization points.The kernel provides no shared state abstractions such as writable shared memory or global file systems.
- Naming: The API uses application-chosen local names, avoiding timing-dependent allocation from shared namespaces.User-level code chooses memory locations and child process identifiers rather than receiving system-allocated names.
- Synchronization and scheduling: User code selects synchronization participants and execution points, excluding nondeterministic operations such as waiting for any first available target.Explicit time sources are treated as controlled I/O, and applications must separate scheduling from result computation.
- Spaces: Each space contains one control flow’s register state and private virtual memory, forming a hierarchy in which spaces interact only with immediate parents and children.Spaces resemble single-threaded Unix processes but cannot outlive their parents.
- Kernel API: Put, Get, and Ret provide deterministic mechanisms to create, execute, synchronize, stop, and transfer state among spaces.Put and Get can copy registers or memory, while Ret returns control to the parent; rendezvous semantics block parents until children stop.
- Determinism and distribution: A Kahn-process-network interpretation formally supports determinism, while space hierarchies can span multiple CPUs and cluster nodes.Distribution is semantically transparent to applications, although applications may need distribution-aware design for acceptable performance.
3 Emulating High-Level Abstractions
Determinator’s user-level runtime recreates familiar Unix processes, file systems, and shared-memory threads over a deterministic, shared-nothing kernel. These abstractions remain feasible, but compatibility and some synchronization behaviors impose concrete semantic, performance, and storage limitations.
- Processes and fork/exec/wait: The runtime emulates fork/exec/wait sufficiently for common shells, build tools, and batch-processing applications rather than reproducing Unix semantics exactly.Process identifiers are local to each process, so applications that pass PIDs between processes are unsupported.
- Processes and fork/exec/wait: Deterministic wait selects the earliest-forked child with uncollected status instead of whichever child terminates first.This preserves applications that wait for all children but can hurt dynamic scheduling and load balancing.
- A Shared File System: The file-system design limits total storage to less than one address space and makes wild-pointer corruption easier than in Unix.The prototype’s 32-bit address-space limit is especially serious; write protection or separate child spaces are proposed alternatives.
- A Shared File System: A user-level file-system replica per process is reconciled at synchronization points, allowing concurrent append-only outputs to accumulate across replicas.Unsynchronized writes that conflict cause one copy to be discarded, set a conflict flag, and make later open() calls fail.
- Shared Memory Multithreading: Deterministic consistency propagates memory changes predictably only at program-defined synchronization points, making some concurrent data races race-free and repeatable.The model can simplify lock-step array computations and avoids speculative execution needed to emulate deterministic sequential consistency.
- Legacy Synchronization APIs: Legacy synchronization abstractions remain difficult because mutexes, condition variables, semaphores, and message queues permit competing operations to resolve in arbitrary order.Deterministic scheduling can preserve repeatability while leaving the programming model unpredictable and vulnerable to schedule-dependent heisenbugs.
4 Prototype Implementation
The Determinator prototype implements its kernel and runtime on 32-bit x86, with limited I/O and cluster migration support. Precise instruction limits use a hybrid performance-counter and debug-tracing technique.
- The prototype is implemented in C with small assembly fragments for 32-bit x86, and its source code is available on request.
- I/O is limited to text console access and a Unix-style shell; there is no demand paging, persistent storage, or interactive job control.The logically shared file system operates only in physical memory.
- Space migration supports application-transparent movement among up to 32 cluster machines using synchronous Ethernet messaging with minimal optimization.The protocol provides only two request/response types and lacks features such as page prefetching.
- On x86, instruction limits combine an imprecise hardware performance counter with debug tracing to recover precise control after a target instruction count.The counter interrupts before the desired count, then tracing runs the remaining instructions.
5 Evaluation
Evaluation finds reproducible debugging and conflict detection benefits, with coarse-grained parallel performance comparable to Linux and usable cluster scaling. Fine-grained interaction and simplistic migration impose substantial costs.
- 5.1 Experience Using the System: Deterministic execution makes user-space bugs reproducible, while observed nondeterminism points to a kernel or hardware bug.
- 5.1 Experience Using the System: Buffered file-system output appears atomically per process and in a consistent order across runs, despite parallel execution.
- 5.1 Experience Using the System: Determinator detects shared-memory and file-system races during normal execution at synchronization events, without requiring a separate race-detection tool.
- 5.1 Experience Using the System: All twelve students successfully reimplemented Determinator’s core features in the PIOS operating-systems course.They also extended the system with graphics, pipes, and a remote shell.
- 5.2 Single-node Multicore Performance: Coarse-grained benchmarks perform comparably to Linux, while MD5 reaches 2.25× Linux performance on 12 cores.The authors suspect Linux thread-system scaling bottlenecks but did not identify the precise cause.
- 5.2 Single-node Multicore Performance: A deterministic scheduler adds about 35% overhead for blackscholes with a 10 million-instruction quantum.Increasing the quantum could reduce the overhead; using the native parallel API could eliminate it.
- 5.2 Single-node Multicore Performance: Fine-grained LU benchmarks incur higher costs, showing that virtual-memory isolation is poorly suited to fine-grained parallel applications.
- 5.2 Single-node Multicore Performance: Large matmult and quicksort inputs become competitive with, and sometimes faster than, Linux, whereas small inputs requiring frequent interaction are costly.
6 Related Work
Prior approaches enforce or replay determinism at the language, application, or logging layers, but face compatibility, security, ordering, or normal-case cost limitations. Determinator instead enforces repeatability in the kernel across multithreaded and multi-process computations.
- Deterministic languages cannot run legacy or multi-process parallel code, while race detectors may miss higher-level order dependencies.
- Application-level deterministic schedulers can be corrupted by bugs or malicious code running in the same process as the scheduler.
- Determinators kernel-enforced model provides repeatability for arbitrary multithreaded and multi-process code, including deterministic shared-file-system abstractions.
- DMP and Grace detect dependencies and re-execute tasks, whereas Determinator combines isolation and deterministic synchronization rather than emulating arbitrary write propagation.
- Logging and replaying parallel nondeterministic events is usually too costly in performance and storage for normal-case execution.
- Transactional memory guarantees atomicity but does not determine the ordering between transactions.
7 Conclusion
Determinator is an initial step toward broadly usable deterministic parallel execution. Experiments suggest that suitable kernel and runtime designs can provide it efficiently for coarse-grained applications on multicore machines and clusters.
- Experiments suggest system-enforced deterministic execution can be efficient for coarse-grained parallel applications on a single multicore machine and across a cluster.