Declarative fence insertion
Declarative fence insertion
复制标题
声明性栅栏插入
DOI：
10.1145/2814270.2814318
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
J. Palsberg
中科院分区：
文献类型：
--
作者：
John Bender;M. Lesani;J. Palsberg
先前的工作已经显示了如何插入实施顺序一致性的围栏。但是，对于许多并发算法，顺序一致性不必要地很强，并且可能导致高执行开销。原因是，通常，正确性取决于几对指令的执行顺序。算法设计人员可以声明这些执行订单，从而启用有关正确性的内存模型的推理，并在多个平台上简化算法的实现。文献中有这样的推理的例子，而迄今为止一直缺乏执行订单的工具支持。在本文中，我们提出了一种声明性的方法来指定和执行执行令。我们的围栏插入算法首先确定给定内存模型会自动执行的执行顺序，然后插入强制执行其余的栅栏。我们的基准包括以C/C ++编写的三种现成的交易内存算法，我们为其指定合适的执行订单。对于这些基准测试，我们对X86和ARMV7内存模型的实验表明，我们的工具插入了与原始作者插入的栅栏竞争的围栏。我们的工具是第一个将围栏插入交易记忆算法的工具，它解决了如何将这种算法轻松移植到新型内存模型的长期存在的问题。
Previous work has shown how to insert fences that enforce sequential consistency. However, for many concurrent algorithms, sequential consistency is unnecessarily strong and can lead to high execution overhead. The reason is that, often, correctness relies on the execution order of a few specific pairs of instructions. Algorithm designers can declare those execution orders and thereby enable memory-model-independent reasoning about correctness and also ease implementation of algorithms on multiple platforms. The literature has examples of such reasoning, while tool support for enforcing the orders has been lacking until now. In this paper we present a declarative approach to specify and enforce execution orders. Our fence insertion algorithm first identifies the execution orders that a given memory model enforces automatically, and then inserts fences that enforce the rest. Our benchmarks include three off-the-shelf transactional memory algorithms written in C/C++ for which we specify suitable execution orders. For those benchmarks, our experiments with the x86 and ARMv7 memory models show that our tool inserts fences that are competitive with those inserted by the original authors. Our tool is the first to insert fences into transactional memory algorithms and it solves the long-standing problem of how to easily port such algorithms to a novel memory model.