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