Optimizing memory transactions

ABSTRACT

Atomic blocks allow programmers to delimit sections of code as 'atomic', leaving the language's implementation to enforce atomicity. Existing work has shown how to implement atomic blocks over word-based transactional memory that provides scalable multi-processor performance without requiring changes to the basic structure of objects in the heap. However, these implementations perform poorly because they interpose on all accesses to shared memory in the atomic block, redirecting updates to a thread-private log which must be searched by reads in the block and later reconciled with the heap when leaving the block.This paper takes a four-pronged approach to improving performance: (1) we introduce a new 'direct access' implementation that avoids searching thread-private logs, (2) we develop compiler optimizations to reduce the amount of logging (e.g. when a thread accesses the same data repeatedly in an atomic block), (3) we use runtime filtering to detect duplicate log entries that are missed statically, and (4) we present a series of GC-time techniques to compact the logs generated by long-running atomic blocks.Our implementation supports short-running scalable concurrent benchmarks with less than 50\% overhead over a non-thread-safe baseline. We support long atomic blocks containing millions of shared memory accesses with a 2.5-4.5x slowdown.

REFERENCES

• 1: Ole Agesen , David Detlefs , Alex Garthwaite , Ross Knippel , Y. S. Ramakrishna , Derek White, An efficient meta-lock for implementing ubiquitous synchronization, ACM SIGPLAN Notices, v.34 n.10, p.207-222, Oct. 1999
• 2: Allan, E., Chase, D., Luchangco, V., Maessen, J.-W., Ryu, S., Steele Jr, G. L., and Tobin-Hochstadt, S. The Fortress language specification v0.618, Apr. 2005.
• 3: Ananian, C. S., and Rinard, M. Efficient software transactions for object-oriented languages. In OOPSLA 2005 Workshop on Synchronization and Concurrency in Object-Oriented Lanaguages (SCOOL) (Oct. 2005). Also available in the University of Rochester digital archive.
• 4: David F. Bacon , Ravi Konuru , Chet Murthy , Mauricio Serrano, Thin locks: featherweight synchronization for Java, ACM SIGPLAN Notices, v.33 n.5, p.258-268, May 1998
• 5: Carlstrom, B. D., Chung, J., Chafi, H., McDonald, A., Minh, C. C., Hammond, L., Kozyrakis, C., and Olukotun, K. Transactional execution of Java programs. In OOPSLA 2005 Workshop on Synchronization and Concurrency in Object-Oriented Lanaguages (SCOOL) (Oct. 2005). Also available in the University of Rochester digital archive
• 6: Philippe Charles , Christian Grothoff , Vijay Saraswat , Christopher Donawa , Allan Kielstra , Kemal Ebcioglu , Christoph von Praun , Vivek Sarkar, X10: an object-oriented approach to non-uniform cluster computing, Proceedings of the 20th annual ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, October 16-20, 2005, San Diego, CA, USA
• 7: Cray Inc. The Chapel language specification v0.4, Feb. 2005.
• 8: Dice, D. Implementing fast Java monitors with relaxed-locks. In Proceedings of USENIX JVM 2001 (2001), pp. 79--90.
• 9: Pedro C. Diniz , Martin C. Rinard, Lock coarsening: eliminating lock overhead in automatically parallelized object-based programs, Journal of Parallel and Distributed Computing, v.49 n.2, p.218-244, March 15, 1998 [doi>10.1006/jpdc.1998.1441]
• 10: Fraser, K. Practical lock freedom. PhD thesis, University of Cambridge Computer Laboratory, 2003.
• 11: Harris, T. Exceptions and side-effects in atomic blocks. In PODC 2004 Workshop on Concurrency and Synchronization in Java programs (CSJP) (Jul. 2004), pp. 46--53. Proceedings published as Memorial University of Newfoundland CS Technical Report 2004-01.
• 12: 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
• 13: Tim Harris , Simon Marlow , Simon Peyton-Jones , Maurice Herlihy, Composable memory transactions, Proceedings of the tenth ACM SIGPLAN symposium on Principles and practice of parallel programming, June 15-17, 2005, Chicago, IL, USA [doi>10.1145/1065944.1065952]
• 14: Sabine Hanke , Thomas Ottmann , Eljas Soisalon-Soininen, Relaxed Balanced Red-Black Trees, Proceedings of the Third Italian Conference on Algorithms and Complexity, p.193-204, March 12-14, 1997
• 15: Herlihy, M. SXM1.1: Software transactional memory package for c#. Tech. rep., Brown University & Microsoft Research, May 2005.
• 16: 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]
• 17: 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
• 18: Maurice P. Herlihy , Jeannette M. Wing, Linearizability: a correctness condition for concurrent objects, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.3, p.463-492, July 1990 [doi>10.1145/78969.78972]
• 19: Hunt, G.C. et al. An overview of the Singularity project. Tech. Rep. MSR-TR-2005-135, Microsoft Research, Oct. 2005.
• 20: International Business Machines Corp. System/370 Principles of Operation, 1983.
• 21: John Kaunitz , Louis van Ekert, Audit trail compaction for database recovery, Communications of the ACM, v.27 n.7, p.678-683, July 1984 [doi>10.1145/358105.358194]
• 22: Barbara Liskov, Distributed programming in Argus, Communications of the ACM, v.31 n.3, p.300-312, March 1988 [doi>10.1145/42392.42399]
• 23: Virendra J. Marathe , William N. Scherer , Michael L. Scott, Design tradeoffs in modern software transactional memory systems, Proceedings of the 7th workshop on Workshop on languages, compilers, and run-time support for scalable systems, p.1-7, October 22-23, 2004, Houston, Texas [doi>10.1145/1066650.1066660]
• 24: Ravi Rajwar , James R. Goodman, Speculative lock elision: enabling highly concurrent multithreaded execution, Proceedings of the 34th annual ACM/IEEE international symposium on Microarchitecture, December 01-05, 2001, Austin, Texas
• 25: Ravi Rajwar , James R. Goodman, Transactional lock-free execution of lock-based programs, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
• 26: Ravi Rajwar , Maurice Herlihy , Konrad Lai, Virtualizing Transactional Memory, Proceedings of the 32nd Annual International Symposium on Computer Architecture, p.494-505, June 04-08, 2005
• 27: Michael F. Ringenburg , Dan Grossman, AtomCaml: first-class atomicity via rollback, Proceedings of the tenth ACM SIGPLAN international conference on Functional programming, September 26-28, 2005, Tallinn, Estonia
• 28: William N. Scherer, III , Michael L. Scott, Advanced contention management for dynamic software transactional memory, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA [doi>10.1145/1073814.1073861]
• 29: Shinnar, A., Tarditi, D., Plesko, M., and Steensgaard, B. Integrating support for undo with exception handling. Tech. Rep. MSR-TR-2004-140, Microsoft Research, Dec. 2004.
• 30: Welc, A., Jagannathan, S., and Hosking, A. Transactional monitors for concurrent objects. In European Conference on Object-Oriented Programming (ECOOP) (Jun. 2004), pp.519--542.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Concurrent programming structures

General Terms:
Algorithms, Languages, Performance

Keywords:
atomicity, critical regions, transactional memory