Entanglement Detection with Near-Zero Cost
summary
Presents a runtime entanglement detector implemented in the Maple (MPL) compiler that builds a computation graph and uses SP-order maintenance to check only mutable reads (no checks on immutable data). Proves soundness and completeness, reuses a provably efficient algorithm from POPL 2021, and adds a fast-path of entanglement candidates. Evaluated on benchmarks up to 72 cores: average time/space overhead ~1–5% (max ~10%), reports ~3x speedup and ~4x less space versus Java on the same tests.
AI-written summary · about
chapters (7)
- 0:00The challenge of parallel GC
- 1:25Defining disentanglement
- 2:45The Maple compiler performance
- 4:48Why static enforcement fails
- 8:06Dynamic detection approach
- 10:26Computation graph implementation
- 13:33Efficiency and future work
related talks
19mCompiling Probabilistic Programs for Variable Elimination with Information Flow
15mA Modular Cost Analysis for Probabilistic Programs
22mOptimizing Optimizations: Case Study on Detecting Specific Types of Mathematical(…)
25mAutomatic Inference of Enclave Placement in LLVM Compiler
13mProgram Analysis via Efficient Symbolic Abstraction
01h 13mParallelism in modern sparse solvers
55mJava PathFinder: going to Mars without bugs and deadlocks
21mTowards Compiler-Guided Static Analysis