As hardware manufacturers shift their primary focus to chip multi-processors (CMPs), a simplified and robust parallel programming model is critical for future software developments to harness the resources of these new architectures. Of the numerous solutions available, transactional memory (TM) shows great promise in reducing programming complexity while retaining high performance. Furthermore, transactional memory has composition characteristics which no other synchronization mechanism demonstrates. Reduction of parallel complexity and composition characteristics make transactional memory a potentially viable solution to the current parallel programming problem.
For over a decade, software transactional memory (STM), a software-only approach to TM, was believed to be only practically implementable using non-blocking atomic primitives, such as compare-and-swap (CAS) or load linked and store-conditional (LL/SC). Yet in the past two years, lock-based STM frameworks have emerged as an alternative design method for STM systems. While significant research exists on non-blocking STM solutions, little has has been done on lock-based STM. This thesis presents a thorough examination of lock-based software transactional memory from (1) a theoretical and (2) a practical viewpoint. First, a background of three important classical synchronization mechanisms is covered to highlight the important aspects and limitations of each. Each synchronization primitive is scrunitized from varying angles ranging from critical section growth causing vertical scaling concerns to practical use within software systems. Next, software transactional memory theory and a practical application framework (DracoSTM) is presented. The TM theory and practice section covers differences between highly visible TM aspects, such as: non-blocking and lock-based systems, direct and deferred updating, validation and invalidation consistency checking, early and late conflict detection and atomic operational overhead. Third, a step-by-step analysis of the current lock-based STM criticisms is presented as well as a detailed counter-argument (if necessary and possible) for each. Lock-based criticisms which also affect non-blocking systems are briefly examined here as well. Finally, a concrete performance analysis between DracoSTM, a lock-based C++ STM library and RSTM, University of Rochester's non-blocking C++ STM library, is presented.
|Commitee:||Siek, Jeremy, Vachharajani, Manish|
|School:||University of Colorado at Boulder|
|School Location:||United States -- Colorado|
|Source:||MAI 46/03M, Masters Abstracts International|
|Keywords:||Distributed computing, Nonblocking STM, 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