Name
Abstract | ||
|---|---|---|
While parallel programmers find it easier to reason about large atomic regions, the conventional mutual exclusion-based primitives for synchronization force them to interleave many small operations to achieve performance. Transactional memory promises that pro- grammers can use large atomic regions while achieving similar per- formance. However, these large transactions can conflict when op- erating on shared data structures, even for logically independent op- erations. Transactional collection classes address this problem by allowing long-running transactions to operate on shared data while eliminating unnecessary conflicts. Transactional collection classes wrap existing data structures, without the need for custom imple- mentations or knowledge of data structure internals. Without transactional collection classes, access to shared data from within long-running transactions can suffer from data depen- dency conflicts that are logically unnecessary, but are artifacts of the data structure implementation such as hash table collisions or tree-balancing rotations. Our transactional collection classes use the concept of semantic concurrency control to eliminate these un- necessary data dependencies, replacing them with conflict detec- tion based on the operations of the abstract data type. The designand behavior ofthese transactional collectionclasses is discussed with reference to the related work from the database community such as multi-level transactions and semantic concur- rency control, as well as other concurrent data structures such as java.util.concurrent. The required transactional semantics needed for implementing transactional collection are enumerated, including open-nested transactions and commit and abort handlers. We also discuss how isolation can be reduced for greater concur- rency. Finally, we provide guidelines on the construction of classes that preserve isolation and serializability. The performance of these classes is evaluated with a number of benchmarks including targeted micro-benchmarks and a version of SPECjbb2000 with increased contention. The results show that easier-to-use long transactions can still allow programs to deliver scalable performance by simply wrapping existing data structures with transactional collection classes. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1145/1229428.1229441 | Principles and Practice of Parallel Programming |
Keywords | Field | DocType |
collection classes,existing data structure,data structure implementation,data dependency conflict,data structure internal,transactional collection class,shared data,transactional memory,unnecessary data dependency,concurrent data structure,abstract data type,shared data structure,java,mul- tiprocessor architecture,concurrency control,data structure,mutual exclusion,nested transaction,hash table,concurrent data structures | Data structure,Commitment ordering,Software transactional memory,Serializability,Concurrency control,Computer science,Parallel computing,Multiversion concurrency control,Transactional memory,Database,Optimistic concurrency control,Distributed computing | Conference |
Citations | PageRank | References |
16 | 1.22 | 14 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Brian D. Carlstrom | 1 | 364 | 30.29 |
| Austen Mcdonald | 2 | 499 | 36.78 |
| Michael Carbin | 3 | 16 | 1.22 |
| Christos Kozyrakis | 4 | 5817 | 355.99 |
| Kunle Olukotun | 5 | 4532 | 373.50 |