Transactional collection classes

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 programmer scan use large atomic regions while achieving similar performance. However, these large transactions can conflict when operating on shared data structures, even for logically independent operations. 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 implementations or knowledge of data structure internals.

Without transactional collection classes, access to shared datafrom within long-running transactions can suffer from data dependency 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 unnecessary data dependencies, replacing them with conflict detection based on the operations of the abstract data type.

The design and behavior of these transactional collection classes is discussed with reference to the related work from the database community such as multi-level transactions and semantic concurrency 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 concurrency. 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.

REFERENCES

• 1: Ali-Reza Adl-Tabatabai , Brian T. Lewis , Vijay Menon , Brian R. Murphy , Bratin Saha , Tatiana Shpeisman, Compiler and runtime support for efficient software transactional memory, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada
• 2: Brian D. Carlstrom , Austen McDonald , Hassan Chafi , JaeWoong Chung , Chi Cao Minh , Christos Kozyrakis , Kunle Olukotun, The Atomos transactional programming language, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada
• 3: Hassan Chafi , Chi Cao Minh , Austen McDonald , Brian D. Carlstrom , JaeWoong Chung , Lance Hammond , Christos Kozyrakis , Kunle Olukotun, TAPE: a transactional application profiling environment, Proceedings of the 19th annual international conference on Supercomputing, June 20-22, 2005, Cambridge, Massachusetts [doi>10.1145/1088149.1088176]
• 4: J. Chung, H. Chafi, C. Cao Minh, A. McDonald, B. D. Carlstrom, C. Kozyrakis, and K. Olukotun. The Common Case Transactional Behavior of Multithreaded Programs. In Proceedings of the 12th International Conference on High-Performance Computer Architecture, February 2006.
• 5: D. Dice and N. Shavit. What really makes transactions faster? In TRANSACT: First ACM SIGPLAN Workshop on Languages, Compilers, and Hardware Support for Transactional Computing, 2006.
• 6: R. Ennals. Efficient software transactional memory. Technical Report IRC-TR-05-051,, Intel Research Cambridge, 2005.
• 7: Free Software Foundation, GNU Classpath 0.18. http://www.gnu.org/software/classpath/, 2005.
• 8: Hector Garcia-Molina , Kenneth Salem, Sagas, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.249-259, May 27-29, 1987, San Francisco, California, United States
• 9: J. Gray. The transaction concept: Virtues and limitations. In Proceedings of the 7th International Conference on Very Large Data Bases, pages 144--154. IEEE Computer Society, 1981.
• 10: Jim Gray , Andreas Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1992
• 11: R. Guerraoui, M. Herlihy, M. Kapalka, and B. Pochon. Robust Contention Management in Software Transactional Memory. In OOPSLA 2005 Workshop on Synchronization and Concurrency in Object-Oriented Languages (SCOOL). October 2005.
• 12: T. Harris. Exceptions and side-effects in atomic blocks. In 2004 PODC Workshop on Concurrency and Synchronization in Java Programs, July 2004.
• 13: Tim Harris , Keir Fraser, Language support for lightweight transactions, Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications, October 26-30, 2003, Anaheim, California, USA
• 14: Maurice Herlihy , Victor Luchangco , Mark Moir , William N. Scherer, III, Software transactional memory for dynamic-sized data structures, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.92-101, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872048]
• 15: Maurice Herlihy , J. Eliot B. Moss, Transactional memory: architectural support for lock-free data structures, Proceedings of the 20th annual international symposium on Computer architecture, p.289-300, May 16-19, 1993, San Diego, California, United States
• 16: Java Specification Request (JSR) 166: Concurrency Utilities, September 2004.
• 17: R. Kalla, B. Sinharoy, and J. Tendler. Simultaneous multi-threading implementation in POWER5. In Conference Record of Hot Chips 15 Symposium, Stanford, CA, August 2003.
• 18: Poonacha Kongetira , Kathirgamar Aingaran , Kunle Olukotun, Niagara: A 32-Way Multithreaded Sparc Processor, IEEE Micro, v.25 n.2, p.21-29, March 2005 [doi>10.1109/MM.2005.35]
• 19: M. Kulkarni, L. P. Chew, and K. Pingali. Using Transactions in Delaunay Mesh Generation. In Workshop on Transactional Memory Workloads, June 2006.
• 20: D. Lea. package util.concurrent. http://gee.cs.oswego.edu/dl, May 2004.
• 21: Austen McDonald , JaeWoong Chung , Brian D. Carlstrom , Chi Cao Minh , Hassan Chafi , Christos Kozyrakis , Kunle Olukotun, Architectural Semantics for Practical Transactional Memory, Proceedings of the 33rd annual international symposium on Computer Architecture, p.53-65, June 17-21, 2006
• 22: Austen McDonald , JaeWoong Chung , Hassan Chafi , Chi Cao Minh , Brian D. Carlstrom , Lance Hammond , Christos Kozyrakis , Kunle Olukotun, Characterization of TCC on Chip-Multiprocessors, Proceedings of the 14th International Conference on Parallel Architectures and Compilation Techniques, p.63-74, September 17-21, 2005 [doi>10.1109/PACT.2005.11]
• 23: Maged M. Michael , Michael L. Scott, Simple, fast, and practical non-blocking and blocking concurrent queue algorithms, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.267-275, May 23-26, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/248052.248106]
• 24: J. E. B. Moss. Nested Transactions: An Approach to Reliable Distributed Computing. PhD thesis, Massachusetts Institute of Technology, Cambridge, MA, USA, April 1981.
• 25: J. E. B. Moss. Open Nested Transactions: Semantics and Support. In Poster at the 4th Workshop on Memory Performance Issues (WMPI-2006). February 2006.
• 26: J. Eliot B Moss , Nancy D. Griffeth , Marc H. Graham, Abstraction in recovery management, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.72-83, May 28-30, 1986, Washington, D.C., United States
• 27: Peter M. Schwarz , Alfred Z. Spector, Synchronizing shared abstract types, ACM Transactions on Computer Systems (TOCS), v.2 n.3, p.223-250, Aug. 1984 [doi>10.1145/989.1188]
• 28: Nir Shavit , Dan Touitou, Software transactional memory, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.204-213, August 20-23, 1995, Ottowa, Ontario, Canada [doi>10.1145/224964.224987]
• 29: Standard Performance Evaluation Corporation, SPECjbb2000 Benchmark. http://www.spec.org/jbb2000/, 2000.
• 30: I. L. Trager. Trends in systems aspects of database management. In Proceedings of the 2nd International Conference on Databases. Wiley & Sons, 1983.
• 31: William Weihl , Barbara Liskov, Specification and implementation of resilient, atomic data types, Proceedings of the 1983 ACM SIGPLAN symposium on Programming language issues in software systems, p.53-64, June 27-29, 1983, San Francisco, California, United States
• 32: Gerhard Weikum , Hans-Jörg Schek, Architectural Issues of Transaction Management in Multi-Layered Systems, Proceedings of the 10th International Conference on Very Large Data Bases, p.454-465, August 27-31, 1984
• 33: C. Zilles and L. Baugh. Extending hardware transactional memory to support non-busy waiting and non-transactional actions. In TRANSACT: First ACM SIGPLAN Workshop on Languages, Compilers, and Hardware Support for Transactional Computing, 2006.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.5 COMPUTER SYSTEM IMPLEMENTATION
      C.5.0 General

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Concurrent programming structures

General Terms:
Design, Languages, Performance

Keywords:
Java, collection classes, multiprocessor architecture, transactional memory