Integrating Transactionally Boosted Data Structures with STM Frameworks: A Case Study on Set
Integrating Transactionally Boosted Data Structures with STM Frameworks: A Case Study on Set
复制标题
将事务增强的数据结构与 STM 框架集成：Set 的案例研究
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
B. Ravindran
中科院分区：
文献类型：
--
作者：
Ahmed Hassan;R. Palmieri;B. Ravindran
提供具有与高并发数据结构相同性能的数据结构事务集合，可以实现具有性能竞争力的事务组合性。尽管软件事务存储器（STM）越来越成为设计和实现事务应用程序的一种有前途的技术，但并发数据结构仍然没有利用STM的优势。最近，乐观事务提升（OTB）已被提出作为一种方法来实现高度并发的数据结构的事务版本。OTB以类似于STM算法的方式工作，但是在数据结构语义的级别上。这种相似性是寻找一种将事务数据结构的操作与STM框架集成的方法的动机。在本文中，我们扩展了设计的DEUCE，Java STM框架，支持OTB集成。使用我们的扩展，程序员可以在同一个事务中包括OTB数据结构操作和传统的内存读/写，并且框架将保证两者都将作为原子块安全地执行。在保持与原始DEUCE框架相同的简单接口和与JVM相同的独立性的同时，我们允许开发人员轻松集成更多的OTB数据结构。作为案例研究，我们展示了OTB-Set的实现细节，这是一个基于事务提升的链表集，我们展示了不同的STM算法（如NOrec和TL 2）如何与之交互。我们的实验表明，与原始DEUCE框架相比，微基准测试的性能提高了10倍。
Providing transactional collections of data structures with the same performance of highly concurrent data structures enables performance-competitive transactional composability. Although Software Transactional Memory (STM) is increasingly becoming a promising technology for designing and implementing transactional applications, concurrent data structures still do not exploit STM’s advantages. Recently, Optimistic Transactional Boosting (OTB) has been proposed as a methodology to implement transactional versions of highly concurrent data structures. OTB works in a similar way to STM algorithms, but on the level of data structure semantics. This similarity is a motivation for finding a way to integrate operations of transactional data structures with STM frameworks. In this paper, we extend the design of DEUCE, a Java STM framework, to support OTB integration. Using our extension, programmers can include both OTB data structure operations and traditional memory reads/writes in the same transaction, and the framework will guarantee that both will execute safely as an atomic block. While keeping the same simple interface and the same independence from the JVM as the original DEUCE framework, we allow developers to easily integrate more OTB data structures. As a case study, we show the implementation details of OTB-Set, a transactionally boosted linked-list-based set, and we show how different STM algorithms like NOrec and TL2 can interact with it. Our experiments show up to 10x improvement in the performance of micro-benchmarks over the original DEUCE framework.