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
Author(s): Tim Harris, James Larus, Ravi Rajwar
Series: Synthesis Lectures on Computer Architecture
Edition: 2
Publisher: Morgan and Claypool Publishers
Year: 2010
Language: English
Pages: 264
Preface......Page 13
Acknowledgments......Page 15
Difficulty of Parallel Programming......Page 17
Parallel Programming Abstractions......Page 19
Database Systems and Transactions......Page 20
What Is a Transaction?......Page 21
Transactional Memory......Page 22
Basic Transactional Memory......Page 23
Building on Basic Transactions......Page 24
Software Transactional Memory......Page 25
What is Transactional Memory Good For?......Page 27
Differences Between Database Transactions and TM......Page 28
Current Transactional Memory Systems and Simulators......Page 29
Basic Transactions......Page 33
TM Design Choices......Page 35
Concurrency Control......Page 36
Version Management......Page 37
Conflict Detection......Page 38
Semantics of Transactions......Page 39
Correctness Criteria for Database Transactions......Page 40
Consistency During Transactions......Page 44
Problems with Mixed-Mode Accesses......Page 46
Handling Mixed-Mode Accesses: Lock-Based Models......Page 51
Handling Mixed-Mode Accesses: TSC......Page 54
Nesting......Page 57
Performance, Progress and Pathologies......Page 60
Progress Guarantees......Page 61
Conflict Detection and Performance......Page 64
Contention Management and Scheduling......Page 67
Reducing Conflicts Between Transactions......Page 70
Higher-Level Conflict Detection......Page 73
Summary......Page 75
Basic Atomic Blocks......Page 77
Semantics of Basic Atomic Blocks.......Page 80
Building Basic Atomic Blocks Over TM......Page 84
Providing Strong Guarantees Over Weak TM Systems......Page 85
Condition Synchronization......Page 88
Exceptions and Failure Atomicity......Page 94
Integrating Non-TM Resources......Page 96
Binary Libraries......Page 97
Storage Allocation and GC......Page 98
Existing Synchronization Primitives......Page 100
System Calls, IO, and External Transactions......Page 103
Debugging and Profiling......Page 105
TM Workloads......Page 106
User Studies......Page 109
Transactions Everywhere......Page 110
Lock-Based Models over TM......Page 112
Speculation over TM......Page 114
Summary......Page 115
Software Transactional Memory......Page 117
Maintaining Metadata......Page 119
Undo-Logs and Redo-Logs......Page 122
Lock-Based STM Systems with Local Version Numbers......Page 124
Two-Phase Locking with Versioned Locks......Page 125
Optimizing STM Usage......Page 129
Providing Opacity......Page 130
Lock-Based STM Systems with a Global Clock......Page 132
Providing Opacity Using a Global Clock......Page 133
Clock Contention vs False Conflict Tradeoffs......Page 137
Lock-Based STM Systems with Global Metadata......Page 139
Bloom Filter Conflict Detection......Page 140
Value-Based Validation......Page 142
Per-object Indirection......Page 144
Nonblocking Object-Based STM Design Space......Page 147
Nonblocking STM Systems Without Indirection......Page 148
Supporting Privatization Safety and Publication Safety......Page 152
Condition Synchronization......Page 156
Irrevocability......Page 157
STM for Clusters......Page 158
STM-Based Middleware......Page 159
STM Testing and Correctness......Page 160
Summary......Page 161
Hardware-Supported Transactional Memory......Page 163
Identifying Transactional Locations......Page 164
Tracking Read-Sets and Managing Write-Sets......Page 165
Detecting Data Conflicts......Page 167
Managing Architectural Register State......Page 168
Committing and Aborting HTM Transactions......Page 169
Explicitly Transactional HTMs......Page 170
Implicitly Transactional HTM Systems......Page 175
Hybrid TMs: Integrating HTMs and STMs......Page 180
Software and Design Considerations......Page 184
Software-Resident Logs for Version Management......Page 186
Signatures for Access Tracking......Page 190
Conflict Detection via Update Broadcasts......Page 195
Deferring Conflict Detection......Page 198
Unbounded HTMs......Page 200
Combining Signatures and Software-Resident Logs......Page 201
Using Persistent Meta-Data......Page 203
Using Page Table Extensions......Page 210
Accelerating Short Transactions and Filtering Redundant Reads......Page 213
Software Controlled Cache Coherence......Page 214
Exposed Signatures to STMs......Page 215
Exposing Metadata to STMs......Page 216
Extending HTM: Nesting, IO, and Synchronization......Page 217
Summary......Page 219
Conclusions......Page 221
Bibliography......Page 225
Authors' Biographies......Page 262
