Lazy Determinism for Faster Deterministic Multithreading
Lazy Determinism for Faster Deterministic Multithreading
复制标题
用于更快确定性多线程的惰性确定性
DOI：
10.1145/3297858.3304047
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Eriksson, Jakob
中科院分区：
文献类型：
--
作者：
Merrifield, Timothy;Roghanchi, Sepideh;Devietti, Joseph;Eriksson, Jakob
确定性多线程（DMT）从根本上要求对每个同步变量的同步操作进行完全的、确定性的排序，即对所有同步操作进行部分排序。在实践中，现有的DMT系统完全排序所有的同步操作，而不管同步变量;结果是严重的性能退化的高并发应用程序使用细粒度同步。受这类程序的启发，我们提出了懒惰决定论作为一种超越这种总顺序瓶颈的方法。延迟确定性推测性地执行同步操作，并通过随后验证操作的结果顺序来强制执行确定性。如果检测到违反排序，则重新开始部分计算。通过只强制执行保证确定性所需的偏序，惰性确定性增加了确定性执行期间可用的并行性。我们实现LazyDet通过一个纯软件的运行时系统加速自定义Linux内核支持。我们的实验与哈希表基准从Synchrobench显示大约一个数量级的改进，基于锁的数据结构的性能相比，最先进的急切确定性。对于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.
登录
查看更多内容
具有总商店订单一致性的高性能确定性
DOI：
--
发表时间：
2015
期刊：
European Conference on Computer Systems
影响因子：
--
作者：
Timothy Merrifield;Joseph Devietti;Jakob Eriksson
通讯作者：
Jakob Eriksson
使用具有效果的任务进行规范的并发编程
DOI：
--
发表时间：
2012
期刊：
USENIX Conference on Hot Topics in Parallelism
影响因子：
--
作者：
Stephen Heumann;Vikram S. Adve
通讯作者：
Vikram S. Adve
使用面向对象并行框架进行安全编程的类型、区域和效果
DOI：
--
发表时间：
2011
期刊：
European Conference on Object-Oriented Programming
影响因子：
--
作者：
R. Bocchino;Vikram S. Adve
通讯作者：
Vikram S. Adve
DOI：
--
发表时间：
2012
期刊：
IEEE International Symposium on High-Performance Comp Architecture
影响因子：
--
作者：
Cedomir Segulja;T. Abdelrahman
通讯作者：
T. Abdelrahman
将执行和语言级确定性与 MELD 合并的案例
DOI：
--
发表时间：
2012
期刊：
影响因子：
--
作者：
Joseph Devietti;D. Grossman;L. Ceze
通讯作者：
L. Ceze