Hassan, Ahmed Mohamed Elsayed.
Designing, Modeling, and Optimizing Transactional Data Structures.
Degree: PhD, Electrical and Computer Engineering, 2015, Virginia Tech
Transactional memory (TM) has emerged as a promising synchronization abstraction for multi-core architectures. Unlike traditional lock-based approaches, TM shifts the burden of implementing threads synchronization from the programmer to an underlying framework using hardware (HTM) and/or software (STM) components.
Although TM can be leveraged to implement transactional data structures (i.e., those where multiple operations are allowed to execute atomically, all-or-nothing, according to the transaction paradigm), its intensive speculation may result in significantly lower performance than the optimized concurrent data structures. This poor performance motivates the need to find other, more effective, alternatives for designing transactional data structures without losing the simple programming abstraction proposed by TM.
To do so, we identified three major challenges that need to be addressed to design efficient transactional data structures. The first challenge is composability, namely allowing an atomic execution of two or more data structure operations in the same way as TM provides, but without its high overheads. The second challenge is integration, which enables the execution of data structure operations within generic transactions that may contain other memory- based operations. The last challenge is modeling, which encompasses the necessity of defining a unified formal methodology to reason about the correctness of transactional data structures.
In this dissertation, we propose different approaches to address the above challenges. First, we address the composability challenge by introducing an optimistic methodology to effi- ciently convert concurrent data structures into transactional ones. Second, we address the integration challenge by injecting the semantic operations of those transactional data struc- ture into TM frameworks, and by presenting two novel STM algorithms in order to enhance the overall performance of those frameworks. Finally, we address the modeling challenge by presenting two models for concurrent and transactional data structures designs.
- Our first main contribution in this dissertation is Optimistic transactional boosting (OTB), a methodology to design transactional versions of the highly concurrent optimistic (i.e., lazy) data structures. An earlier (pessimistic) boosting proposal added a layer of abstract locks on top of existing concurrent data structures. Instead, we propose an optimistic boosting methodology, which allows greater data structure-specific optimizations, easier integration with TM frameworks, and lower restrictions on the operations than the original (more pessimistic) boosting methodology.
Based on the proposed OTB methodology, we implement the transactional version of two list-based data structures (i.e., set and priority queue). Then, we present TxCF-Tree, a balanced tree whose design is optimized to support transactional accesses. The core optimizations of TxCF-Tree's operations are: providing a traversal phase that does not use any lock and/or speculation…
Advisors/Committee Members: Ravindran, Binoy (committeechair), Wang, Chao (committee member), Tilevich, Eli (committee member), Broadwater, Robert P. (committee member), White, Christopher Jules (committee member).
Subjects/Keywords: Transactional Memory; STM; HTM; Transactional Boosting; Concurrent Data Structures; Optimistic Semantic Synchronization; Lazy List; Balanced Trees; Hybrid Transactions; Semantic Validation; Remote Transaction Commit; Modeling; Linearizability
to Zotero / EndNote / Reference
APA (6th Edition):
Hassan, A. M. E. (2015). Designing, Modeling, and Optimizing Transactional Data Structures. (Doctoral Dissertation). Virginia Tech. Retrieved from http://hdl.handle.net/10919/56656
Chicago Manual of Style (16th Edition):
Hassan, Ahmed Mohamed Elsayed. “Designing, Modeling, and Optimizing Transactional Data Structures.” 2015. Doctoral Dissertation, Virginia Tech. Accessed January 23, 2020.
MLA Handbook (7th Edition):
Hassan, Ahmed Mohamed Elsayed. “Designing, Modeling, and Optimizing Transactional Data Structures.” 2015. Web. 23 Jan 2020.
Hassan AME. Designing, Modeling, and Optimizing Transactional Data Structures. [Internet] [Doctoral dissertation]. Virginia Tech; 2015. [cited 2020 Jan 23].
Available from: http://hdl.handle.net/10919/56656.
Council of Science Editors:
Hassan AME. Designing, Modeling, and Optimizing Transactional Data Structures. [Doctoral Dissertation]. Virginia Tech; 2015. Available from: http://hdl.handle.net/10919/56656