Synthesis Lectures on Computer Architecture : Transactional Memory (2nd Edition)

Kurzbeschreibung The advent of multicore processors has renewed interest in the idea of incorporating transactions into the programming model used to write parallel programs. This approach, known as transactional memory, offers an alternative, and hopefully better, way to coordinate concurrent threads. The ACI (atomicity, consistency, isolation) properties of transactions provide a foundation to ensure that concurrent reads and writes of shared data do not produce inconsistent or incorrect results. At a higher level, a computation wrapped in a transaction executes atomically - either it completes successfully and commits its result in its entirety or it aborts. In addition, isolation ensures the transaction produces the same result as if no other transactions were executing concurrently. Although transactions are not a parallel programming panacea, they shift much of the burden of synchronizing and coordinating parallel computations from a programmer to a compiler, to a language runtime system, or to hardware. The challenge for the system implementers is to build an efficient transactional memory infrastructure. This book presents an overview of the state of the art in the design and implementation of transactional memory systems, as of early spring 2010. Table of Contents: Introduction / Basic Transactions / Building on Basic Transactions / Software Transactional Memory / Hardware-Supported Transactional Memory / Conclusions 1. Introduction Motivation Difficulty of Parallel Programming Parallel Programming Abstractions Database Systems and Transactions What Is a Transaction Transactional Memory Basic Transactional Memory Building on Basic Transactions Software Transactional Memory Hardware Transactional Memory What is Transactional Memory Good For Differences Between Database Transactions and TM Current Transactional Memory Systems and Simulators 2. Basic Transactions TM Design Choices Concurrency Control Version Management Conflict Detection Semantics of Transactions Correctness Criteria for Database Transactions Consistency During Transactions Problems with Mixed-Mode Accesses Handling Mixed-Mode Accesses: Lock-Based Models Handling Mixed-Mode Accesses: TSC Nesting Performance, Progress and Pathologies Progress Guarantees Conflict Detection and Performance Contention Management and Scheduling Reducing Conflicts Between Transactions Higher-Level Conflict Detection Summary 3. Building on Basic Transactions Basic Atomic Blocks Semantics of Basic Atomic Blocks Building Basic Atomic Blocks Over TM Providing Strong Guarantees Over Weak TM Systems Extending Basic Atomic Blocks Condition Synchronization Exceptions and Failure Atomicity Integrating Non-TM Resources Binary Libraries Storage Allocation and GC Existing Synchronization Primitives System Calls, IO, and External Transactions Programming with TM Debugging and Profiling TM Workloads User Studies Alternative Models Transactions Everywhere Lock-Based Models over TM Speculation over TM Summary 4. Software Transactional Memory Managing STM Logs and Metadata Maintaining Metadata Undo-Logs and Redo-Logs Read-Sets and Write-Sets Lock-Based STM Systems with Local Version Numbers Two-Phase Locking with Versioned Locks Optimizing STM Usage Providing Opacity Discussion Lock-Based STM Systems with a Global Clock Providing Opacity Using a Global Clock Timebase Extension Clock Contention vs False Conflict Tradeoffs Alternative Global Clock Algorithms Lock-Based STM Systems with Global Metadata Bloom Filter Conflict Detection Value-Based Validation Nonblocking STM Systems Per-object Indirection Nonblocking Object-Based STM Design Space Nonblocking STM Systems Without Indirection Additional Implementation Techniques Supporting Privatization Safety and Publication Safety Condition Synchronization Irrevocability Distributed STM Systems STM for Clusters STM-Based Middleware STM for PGAS Languages STM Testing and Correctness Summary 5. Hardware-Supported Transactional Memory Basic Mechanisms for Conventional HTMs Identifying Transactional Locations Tracking Read-Sets and Managing Write-Sets Detecting Data Conflicts Resolving Data Conflicts Managing Architectural Register State Committing and Aborting HTM Transactions Conventional HTM Proposals Explicitly Transactional HTMs Implicitly Transactional HTM Systems Hybrid TMs: Integrating HTMs and STMs Software and Design Considerations Alternative Mechanisms for HTMs Software-Resident Logs for Version Management Signatures for Access Tracking Conflict Detection via Update Broadcasts Deferring Conflict Detection Unbounded HTMs Combining Signatures and Software-Resident Logs Using Persistent Meta-Data Using Page Table Extensions Exposing Hardware Mechanisms to STMs Accelerating Short Transactions and Filtering Redundant Reads Software Controlled Cache Coherence Exposed Signatures to STMs Exposing Metadata to STMs Extending HTM: Nesting, IO, and Synchronization Summary 6. Conclusions Bibliography Authors' Biographies.