Transactional Locking II

Transactional Locking II

2006 | Dave Dice, Ori Shalev, and Nir Shavit
Transactional locking II (TL2) is a software transactional memory (STM) algorithm that combines commit-time locking with a novel global version-clock based validation technique. TL2 improves upon state-of-the-art STMs in several ways. First, it seamlessly integrates with any system's memory life-cycle, including those using malloc/free. Second, it efficiently avoids unsafe execution periods by ensuring user code operates only on consistent memory states through its version-clock validation. Third, in high-performance benchmarks, TL2 delivers performance comparable to (and often better than) previous STM algorithms, both lock-based and non-blocking. Moreover, it performs competitively with the best hand-crafted fine-grained concurrent structures, being ten-fold faster than a single lock. These characteristics make TL2 a viable candidate for deploying transactional memory today, before hardware transactional support is available. The goal of current multiprocessor software design is to introduce parallelism by allowing non-conflicting memory accesses to proceed concurrently. Locks have been the key tool in designing concurrent data structures, but coarse-grained locking provides poor performance due to limited parallelism. Fine-grained lock-based structures perform well but are difficult to design. Alternative approaches that simplify code design and verification are needed for concurrent programming to become ubiquitous. This paper focuses on mechanical methods for transforming sequential or coarse-grained lock-based code into concurrent code without requiring program-specific information. The paper also emphasizes techniques that deliver reasonable performance across a wide range of systems and can easily combine with specialized hardware support. Transactional memory programming, as introduced by Herlihy and Moss, is gaining momentum as a replacement for locks. It promises to reduce programming and verification complexity by making code appear sequential without fine-grained locks. Transactions can run in parallel if they do not conflict, and conflicting ones are aborted and retried without programmer intervention. There are proposals for hardware implementations (HTM), software-based ones (STM), and hybrid schemes (HyTM). The dominant trend is to provide large-scale, unbounded, and dynamic transactions. Providing large-scale transactions in hardware is complex, while efficient software implementations are challenging and require careful design.Transactional locking II (TL2) is a software transactional memory (STM) algorithm that combines commit-time locking with a novel global version-clock based validation technique. TL2 improves upon state-of-the-art STMs in several ways. First, it seamlessly integrates with any system's memory life-cycle, including those using malloc/free. Second, it efficiently avoids unsafe execution periods by ensuring user code operates only on consistent memory states through its version-clock validation. Third, in high-performance benchmarks, TL2 delivers performance comparable to (and often better than) previous STM algorithms, both lock-based and non-blocking. Moreover, it performs competitively with the best hand-crafted fine-grained concurrent structures, being ten-fold faster than a single lock. These characteristics make TL2 a viable candidate for deploying transactional memory today, before hardware transactional support is available. The goal of current multiprocessor software design is to introduce parallelism by allowing non-conflicting memory accesses to proceed concurrently. Locks have been the key tool in designing concurrent data structures, but coarse-grained locking provides poor performance due to limited parallelism. Fine-grained lock-based structures perform well but are difficult to design. Alternative approaches that simplify code design and verification are needed for concurrent programming to become ubiquitous. This paper focuses on mechanical methods for transforming sequential or coarse-grained lock-based code into concurrent code without requiring program-specific information. The paper also emphasizes techniques that deliver reasonable performance across a wide range of systems and can easily combine with specialized hardware support. Transactional memory programming, as introduced by Herlihy and Moss, is gaining momentum as a replacement for locks. It promises to reduce programming and verification complexity by making code appear sequential without fine-grained locks. Transactions can run in parallel if they do not conflict, and conflicting ones are aborted and retried without programmer intervention. There are proposals for hardware implementations (HTM), software-based ones (STM), and hybrid schemes (HyTM). The dominant trend is to provide large-scale, unbounded, and dynamic transactions. Providing large-scale transactions in hardware is complex, while efficient software implementations are challenging and require careful design.
Reach us at info@study.space
[slides] Transactional Locking II | StudySpace