Transactional Memory

Preface......Page 15
Acknowledgments......Page 17
Difficulty of Parallel Programming......Page 19
Parallel Programming Abstractions......Page 21
Database Systems and Transactions......Page 22
What Is a Transaction?......Page 23
Transactional Memory......Page 24
Basic Transactional Memory......Page 25
Building on Basic Transactions......Page 26
Software Transactional Memory......Page 27
What is Transactional Memory Good For?......Page 29
Differences Between Database Transactions and TM......Page 30
Current Transactional Memory Systems and Simulators......Page 31
Basic Transactions......Page 35
TM Design Choices......Page 37
Concurrency Control......Page 38
Version Management......Page 39
Conflict Detection......Page 40
Semantics of Transactions......Page 41
Correctness Criteria for Database Transactions......Page 42
Consistency During Transactions......Page 46
Problems with Mixed-Mode Accesses......Page 48
Handling Mixed-Mode Accesses: Lock-Based Models......Page 53
Handling Mixed-Mode Accesses: TSC......Page 56
Nesting......Page 59
Performance, Progress and Pathologies......Page 62
Progress Guarantees......Page 63
Conflict Detection and Performance......Page 66
Contention Management and Scheduling......Page 69
Reducing Conflicts Between Transactions......Page 72
Higher-Level Conflict Detection......Page 75
Summary......Page 77
Basic Atomic Blocks......Page 79
Semantics of Basic Atomic Blocks.......Page 82
Building Basic Atomic Blocks Over TM......Page 86
Providing Strong Guarantees Over Weak TM Systems......Page 87
Condition Synchronization......Page 90
Exceptions and Failure Atomicity......Page 96
Integrating Non-TM Resources......Page 98
Binary Libraries......Page 99
Storage Allocation and GC......Page 100
Existing Synchronization Primitives......Page 102
System Calls, IO, and External Transactions......Page 105
Debugging and Profiling......Page 107
TM Workloads......Page 108
User Studies......Page 111
Transactions Everywhere......Page 112
Lock-Based Models over TM......Page 114
Speculation over TM......Page 116
Summary......Page 117
Software Transactional Memory......Page 119
Maintaining Metadata......Page 121
Undo-Logs and Redo-Logs......Page 124
Lock-Based STM Systems with Local Version Numbers......Page 126
Two-Phase Locking with Versioned Locks......Page 127
Optimizing STM Usage......Page 131
Providing Opacity......Page 132
Lock-Based STM Systems with a Global Clock......Page 134
Providing Opacity Using a Global Clock......Page 135
Clock Contention vs False Conflict Tradeoffs......Page 139
Lock-Based STM Systems with Global Metadata......Page 141
Bloom Filter Conflict Detection......Page 142
Value-Based Validation......Page 144
Per-object Indirection......Page 146
Nonblocking Object-Based STM Design Space......Page 149
Nonblocking STM Systems Without Indirection......Page 150
Supporting Privatization Safety and Publication Safety......Page 154
Condition Synchronization......Page 158
Irrevocability......Page 159
STM for Clusters......Page 160
STM-Based Middleware......Page 161
STM Testing and Correctness......Page 162
Summary......Page 163
Hardware-Supported Transactional Memory......Page 165
Identifying Transactional Locations......Page 166
Tracking Read-Sets and Managing Write-Sets......Page 167
Detecting Data Conflicts......Page 169
Managing Architectural Register State......Page 170
Committing and Aborting HTM Transactions......Page 171
Explicitly Transactional HTMs......Page 172
Implicitly Transactional HTM Systems......Page 177
Hybrid TMs: Integrating HTMs and STMs......Page 182
Software and Design Considerations......Page 186
Software-Resident Logs for Version Management......Page 188
Signatures for Access Tracking......Page 192
Conflict Detection via Update Broadcasts......Page 197
Deferring Conflict Detection......Page 200
Unbounded HTMs......Page 202
Combining Signatures and Software-Resident Logs......Page 203
Using Persistent Meta-Data......Page 205
Using Page Table Extensions......Page 212
Accelerating Short Transactions and Filtering Redundant Reads......Page 215
Software Controlled Cache Coherence......Page 216
Exposed Signatures to STMs......Page 217
Exposing Metadata to STMs......Page 218
Extending HTM: Nesting, IO, and Synchronization......Page 219
Summary......Page 221
Conclusions......Page 223
Bibliography......Page 227
Authors\' Biographies......Page 264