paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Lazy Determinism for Faster Deterministic Multithreading

面向更快确定性多线程的惰性确定性
ASPLOS Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems2019匹配度 2/10 · 论文关注确定性多线程与并发运行时性能优化,属于系统/并发方向,而非用户核心关注的静态分析、LLM/Agent 与程序分析交叉。仅与 PL/程序分析所在的广义领域有较弱关联,不涉及浮点或贝叶斯程序分析。引用 8 inbox
Timothy Merrifield, Sepideh Roghanchi, Joseph Devietti, Jakob Eriksson
crossref: 2026-09-12

AI 速览

一句话:提出惰性确定性 DMT,通过推测执行同步操作并验证顺序,避免全局全序瓶颈,大幅提升确定性执行性能。

确定性多线程(DMT)要求对同步操作施加确定性顺序,但现有系统往往将所有同步操作全局全序化,导致使用细粒度同步的高并发程序性能严重下降。本文提出惰性确定性:先推测执行同步操作,再验证其结果顺序;一旦检测到顺序违规,就重启部分计算。由于只强制保证确定性所需的部分顺序,该方法在确定性执行中释放更多并行性。作者实现 LazyDet 软件运行时,并借助定制 Linux 内核支持加速。在 Synchrobench 哈希表基准上,基于锁的数据结构相比最先进的 eager determinism 约提升一个数量级;在 PARSEC-2、SPLASH-2 和 Phoenix 上,最具挑战的程序最多提升 2 倍。

问题
现有确定性多线程系统常将所有同步操作全局全序化,导致使用细粒度同步的高并发应用性能严重退化。
方法
提出惰性确定性,推测执行同步操作并事后验证其顺序,检测到违规时重启部分计算;实现为 LazyDet 软件运行时,并利用定制 Linux 内核支持加速。
评估
在 Synchrobench 哈希表基准、PARSEC-2、SPLASH-2 和 Phoenix 上与最先进的 eager determinism 系统对比,验证性能提升。
原文摘要(Abstract)

Deterministic multithreading (DMT) fundamentally requires total, deterministic ordering of synchronization operations on each synchronization variable, i.e. a partial ordering over all synchronization operations. In practice, prior DMT systems totally order all synchronization operations, regardless of synchronization variable; the result is severe performance degradation for highly concurrent applications using fine-grained synchronization. Motivated by this class of programs, we propose lazy determinism as a way to go beyond this total order bottleneck. Lazy determinism executes synchronization operations speculatively, and enforces determinism by subsequently validating the resulting order of operations. If an ordering violation is detected, part of the computation is restarted. By enforcing only the partial ordering required to guarantee determinism, lazy determinism increases the available parallelism during deterministic execution. We implement LazyDet via a pure-software runtime system accelerated by custom Linux kernel support. Our experiments with hash table benchmarks from Synchrobench show roughly an order of magnitude improvement in the performance of lock-based data structures compared to the state of the art in eager determinism. For benchmarks from PARSEC-2, SPLASH-2, and Phoenix, we demonstrate runtime improvements of up to 2× on the programs that challenge deterministic execution environments the most.

链接与引用

DOI 原文 · PDF(开放获取) ·

BibTeX
@inproceedings{paperbot4923,
  title = {Lazy Determinism for Faster Deterministic Multithreading},
  author = {Timothy Merrifield and Sepideh Roghanchi and Joseph Devietti and Jakob Eriksson},
  booktitle = {ASPLOS},
  year = {2019},
  doi = {10.1145/3297858.3304047}
}