Transactional predication: high-performance concurrent sets and maps for STM
Transactional predication: high-performance concurrent sets and maps for STM
复制标题
事务预测：STM 的高性能并发集和映射
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
K. Olukotun
中科院分区：
文献类型：
--
作者：
N. Bronson;J. Casper;Hassan Chafi;K. Olukotun
并发集合类广泛应用于多线程编程中，但它们仅为一组固定的操作提供原子性。软件事务内存 (STM) 为组合原子操作提供了方便而强大的编程模型，但允许使用 STM 组合操作的并发收集算法比不可组合的替代方案慢得多。我们引入事务预测，这是一种在底层不可组合并发映射之上构建事务映射和集合的方法。我们将大多数集合操作的工作分为两部分：不需要原子性或隔离的部分，以及单个事务性内存访问。结果近似使用 STM 的结构冲突检测机制进行语义冲突检测。当集合在事务之外使用时，这种分离还允许额外的优化。我们进行的实验评估表明，在一系列工作负载中，预测比现有的事务收集算法具有更好的性能。
Concurrent collection classes are widely used in multi-threaded programming, but they provide atomicity only for a fixed set of operations. Software transactional memory (STM) provides a convenient and powerful programming model for composing atomic operations, but concurrent collection algorithms that allow their operations to be composed using STM are significantly slower than their non-composable alternatives. We introduce transactional predication, a method for building transactional maps and sets on top of an underlying non-composable concurrent map. We factor the work of most collection operations into two parts: a portion that does not need atomicity or isolation, and a single transactional memory access. The result approximates semantic conflict detection using the STM's structural conflict detection mechanism. The separation also allows extra optimizations when the collection is used outside a transaction. We perform an experimental evaluation that shows that predication has better performance than existing transactional collection algorithms across a range of workloads.