Exploiting the Commutativity Lattice ∗
Exploiting the Commutativity Lattice ∗
复制标题
利用交换性格*
DOI：
10.1145/1993498.1993562
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
K. Pingali
中科院分区：
文献类型：
--
作者：
Milind Kulkarni;Donald Nguyen;Dimitrios Prountzos;Xin Sui;K. Pingali
投机性执行是在许多程序中利用并行性的一种有前途的方法，但是它需要有效的方案来检测同时执行线程之间的冲突。先前的工作认为，检查方法调用的语义通勤性是检测复杂数据结构（例如KD-Trees）冲突的正确方法。在文献中提出了几种临时检查交换性的方法，但是没有系统地生产实施方法。在本文中，我们描述了有关通勤条件的推理的新框架：通勤晶格。我们展示了如何在三种不同方案之一中系统地实现该晶格的通勤性规范：抽象锁定，前向守门和一般守门。我们还讨论了一种纪律处分的方法，以利用晶格，以找到在冲突检测中以换取精确性的不同实现。最后，我们表明我们的新颖的冲突检测方案是实用的，可以在三个现实世界应用上提供加速。
Speculative execution is a promising approach for exploiting parallelism in many programs, but it requires efficient schemes for detecting conflicts between concurrently executing threads. Prior work has argued that checking semantic commutativity of method invocations is the right way to detect conflicts for complex data structures such as kd-trees. Several ad hoc ways of checking commutativity have been proposed in the literature, but there is no systematic approach for producing implementations. In this paper, we describe a novel framework for reasoning about commutativity conditions: the commutativity lattice. We show how commutativity specifications from this lattice can be systematically implemented in one of three different schemes: abstract locking, forward gatekeeping and general gatekeeping. We also discuss a disciplined approach to exploiting the lattice to find different implementations that trade off precision in conflict detection for performance. Finally, we show that our novel conflict detection schemes are practical and can deliver speedup on three real-world applications.