Transactional memory (TM) is a modern concurrency control paradigm that reduces the difficulty of parallel programming. TM also reduces some unnecessary program serialization by allowing operations from different critical sections, called transactions, to execute concurrently. Although allowing transactions to execute concurrently can increase throughput, care is needed to avoid memory access conflicts between transactions that can lead to incorrect program states.
To prevent such incorrect program states, TM systems identify conflicts between transactions before such illegal states become part of the visible program state. To do this, when two or more transactions conflict, the TM stalls or rolls back some number of transactions to ensure the program state remains serializable, the main correctness criterion for TM systems. The process of identifying when transactions conflict is called conflict detection and is a significant source of overhead.
To improve the performance of TM, researchers have found optimizations that reduce the cost of conflict detection. However, many of these TMs perform one aspect of conflict detection in the same manner. That is, they perform commit-time validation, where a transaction is analyzed for conflicts with previously committed transactions during its commit phase. While commit-time validation has certain benefits, it also has drawbacks that make it a suboptimal conflict detection strategy for certain environments.
In this work we present a conflict detection strategy called full invalidation where the TM resolves all conflicts between a given transaction and all other active transactions before the given transaction commits. Full invalidation has a number of advantages over validation such as improved performance, enforceable execution guarantees, reduced conflict speculation, reduced conflict analysis space and time overhead, and simplified integration of optimistic and pessimistic concurrency control.
We analyze full invalidation in the following ways. First, we compare and contrast InvalSTM, a software transactional memory (STM) that implements full invalidation, against TL2, a state-of-the-art STM that uses commit-time validation. Next we present a new theoretical model for TM systems and use the model to prove that histories accepted by a full invalidation system are both conflict and view serializable. We then demonstrate that a full invalidation STM is notably more efficient (by upwards of 100x) than a commit-time validation STM for programs where transactional priority must be respected. Last, we show that a full invalidation STM can reduce the TM implementation complexity and the TM operational overhead when using optimistic (transactions) and pessimistic (locks) critical sections in the same program.
|Advisor:||Siek, Jeremy G.|
|Commitee:||Bradley, Aaron, Herlihy, Maurice, Somenzi, Fabio, Vachharajani, Manish|
|School:||University of Colorado at Boulder|
|School Location:||United States -- Colorado|
|Source:||DAI-B 72/07, Dissertation Abstracts International|
|Subjects:||Computer Engineering, Computer science|
|Keywords:||Invalidation, Parallel algorithms, Parallel computing, Transactional memory|
Copyright in each Dissertation and Thesis is retained by the author. All Rights Reserved
The supplemental file or files you are about to download were provided to ProQuest by the author as part of a
dissertation or thesis. The supplemental files are provided "AS IS" without warranty. ProQuest is not responsible for the
content, format or impact on the supplemental file(s) on our system. in some cases, the file type may be unknown or
may be a .exe file. We recommend caution as you open such files.
Copyright of the original materials contained in the supplemental file is retained by the author and your access to the
supplemental files is subject to the ProQuest Terms and Conditions of use.
Depending on the size of the file(s) you are downloading, the system may take some time to download them. Please be