Architectural Semantics for Practical Transactional Memory

ABSTRACT

Transactional Memory (TM) simplifies parallel programming by allowing for parallel execution of atomic tasks. Thus far, TM systems have focused on implementing transactional state buffering and conflict resolution. Missing is a robust hardware/software interface, not limited to simplistic instructions defining transaction boundaries. Without rich semantics, current TM systems cannot support basic features of modern programming languages and operating systems such as transparent library calls, conditional synchronization, system calls, I/O, and runtime exceptions. This paper presents a comprehensive instruction set architecture (ISA) for TM systems. Our proposal introduces three key mechanisms: two-phase commit; support for software handlers on commit, violation, and abort; and full support for open- and closed-nested transactions with independent rollback. These mechanisms provide a flexible interface to implement programming language and operating system functionality. We also show that these mechanisms are practical to implement at the ISA and microarchitecture level for various TM systems. Using an execution-driven simulation, we demonstrate both the functionality (e.g., I/O and conditional scheduling within transactions) and performance potential (2.2× improvement for SPECjbb2000) of the proposed mechanisms. Overall, this paper establishes a rich and efficient interface to foster both hardware and software research on transactional memory.

References

1. {1} A.-R. Adl-Tabatabai et al. Compiler and Runtime Support for Efficient Software Transactional Memory. In Proceedings of the Conference on Programming Language Design and Implementation, June 2006.
2. {2} E. Allen et al. The Fortress Language Specification. Sun Microsystems, 2005.
3. {3} B. Alpern et al. The Jalapeño Virtual Machine. IBM Systems Journal, 39(1):211-238, 2000.
4. {4} S. Ananian et al. Unbounded Transactional Memory. In Proceedings of the 11th Intl. Symposium on High Performance Computer Architecture, Feb. 2005.
5. {5} C. Blundell, E. C. Lewis, and M. Martin. Deconstructing Transactional Semantics: The Subtleties of Atomicity. In ISCA Workshop on Duplicating, Deconstructing, and Debunking , June 2005.
6. {6} B. D. Carlstrom et al. The Atomos Transactional Programming Language. In Proceedings of the Conference on Programming Language Design and Implementation, June 2006.
7. {7} Chapel Specification. Cray, February 2005.
8. {8} P. Charles et al. X10: An Object-oriented Approach to Non-uniform Cluster Computing. In Proceedings of the 20th Conference on Object-oriented Programing, Systems, Languages, and Applications. ACM Press, Oct. 2005.
9. {9} J. Chung et al. The Common Case Transactional Behavior of Multithreaded Programs. In Proceedings of the 12th Intl. Conference on High Performance Computer Architecture , Feb. 2006.
10. {10} J. Gray and A. Reuter. Transaction Processing: Concepts and Techniques. Morgan Kaufmann, 1993.
11. {11} R. Guerraoui et al. Robust Contention Management in Software Transactional Memory. In OOPSLA Workshop on Synchronization and Concurrency in Object-Oriented Languages , Oct. 2005.
12. {12} L. Hammond et al. Transactional memory coherence and consistency. In Proceedings of the 31st Intl. Symposium on Computer Architecture, June 2004.
13. {13} T. Harris. Exceptions and Side-effects in Atomic Blocks. In PODC Workshop on Concurrency and Synchronization in Java Programs, July 2004.
14. {14} T. Harris et al. Composable Memory Transactions. In Proceedings of the Symposium Principles and Practice of Parallel Programming, July 2005.
15. {15} T. Harris and K. Fraser. Language Support for Lightweight Transactions. In Proceedings of the 18th Conference on Object-oriented programing, Systems, Languages, and Applications , pages 388-402. ACM Press, Oct. 2003.
16. {16} M. Herlihy et al. Software Transactional Memory for Dynamic-sized Data Structures. In Proceedings of the 22nd Symposium on Principles of Distributed Computing, July 2003.
17. {17} M. Herlihy and J. E. B. Moss. Transactional Memory: Architectural Support for Lock-Free Data Structures. In Proceedings of the 20th Intl. Symposium on Computer Architecture, May 1993.
18. {18} Java Grande Forum, Java Grande Benchmark Suite. http: //www.epcc.ed.ac.uk/javagrande/, 2000.
19. {19} J. Larus. It's the Software Stupid. Talk at the Workshop on Transactional Systems, Apr. 2005.
20. {20} V. Luchangco and V. Marathe. Transaction Synchronizers. In OOPSLA Workshop on Synchronization and Concurrency in Object-Oriented Languages, Oct. 2005.
21. {21} V. Marathe, W. Scherer, and M. Scott. Adaptive Software Transactional Memory. In Proceedings of the 19th Intl. Symposium on Distributed Computing, Sept. 2005.
22. {22} A. McDonald et al. Characterization of TCC on Chip-Multiprocessors. In Proceedings of the 14th Intl. Conference on Parallel Architectures and Compilation Techniques, Sept. 2005.
23. {23} K. Moore et al. LogTM: Log-Based Transactional Memory. In Proceedings of the 12th Intl. Conference on High Performance Computer Architecture, Feb. 2006.
24. {24} E. Moss and T. Hosking. Nested Transactional Memory: Model and Preliminary Architecture Sketches. In OOPSLA Workshop on Synchronization and Concurrency in Object-Oriented Languages, Oct. 2005.
25. {25} J. Nakano et al. ReViveI/O: Efficient Handling of I/O in Highly-Available Rollback-Recovery Servers. In Proceedings of the 12th Intl. Conference on High Performance Computer Architecture, Feb. 2006.
26. {26} J. Oplinger and M. S. Lam. Enhancing Software Reliability with Speculative Threads. In Proceedings of the 10th Intl. Conference on Architectural Support for Programming Languages and Operating Systems, Oct. 2002.
27. {27} R. Rajwar and J. Goodman. Transactional Lock-Free Execution of Lock-Based Programs. In Proceedings of the 10th Intl. Conference on Architectural Support for Programming Languages and Operating Systems, Oct. 2002.
28. {28} R. Rajwar, M. Herlihy, and K. Lai. Virtualizing Transactional Memory. In Proceedings of the 32nd Intl. Symposium on Computer Architecture, June 2005.
29. {29} M. F. Ringenburg and D. Grossman. AtomCaml: First-class Atomicity via Rollback. In Proceedings of the 10th Intl. Conference on Functional Programming, Sept. 2005.
30. {30} B. Saha et al. A High Performance Software Transactional Memory System for a Multi-core Runtime. In Proceedings of the Symposium Principles and Practice of Parallel Programming , Mar. 2005.
31. {31} N. Shavit and S. Touitou. Software Transactional Memory. In Proceedings of the 14th Symposium on Principles of Distributed Computing, Aug. 1995.
32. {32} J. P. Singh, W. Weber, and A. Gupta. SPLASH: Stanford Parallel Applications for Shared-Memory. Computer Architecture News, 1992.
33. {33} Standard Performance Evaluation Corporation, SPEC CPU Benchmarks. http://www.specbench.org/, 2000.
34. {34} Standard Performance Evaluation Corporation, SPECjbb2000 Benchmark. http://www.spec. org/jbb2000/, 2000.
35. {35} G. Steffan, C. Colohan, Z. Zhai, and T. Mowry. A Scalable Approach to Thread-level Speculation. In the Proceedings of the 27th Intl. Symposium on Computer Architecture, June 2000.
36. {36} S. Woo, M. Ohara, E. Torrie, J. P. Singh, and A. Gupta. The SPLASH2 Programs: Characterization and Methodological Considerations. In Proceedings of the 22nd Intl. Symposium on Computer Architecture, June 1995.
37. {37} A. Welc, S. Jagannathan, and A. L. Hosking. Transactional Monitors for Concurrent Objects. In Proceedings of the European Conference on Object-Oriented Programming, June 2004.

Index Terms

• Computing methodologies

  • Parallel computing methodologies

    • Parallel programming languages

• Hardware

  • Electronic design automation

    • High-level and register-transfer level synthesis

  • Integrated circuits

    • Semiconductor memory

• Software and its engineering

  • Software notations and tools

    • General programming languages

      • Language types

        • Parallel programming languages