Time-based transactional memory with scalable time bases

ABSTRACT

Time-based transactional memories use time to reason about the consistency of data accessed by transactions and about the order in which transactions commit. They avoid the large read overhead of transactional memories that always check consistency when a new object is accessed, while still guaranteeing consistency at all times--in contrast to transactional memories that only check consistency on transaction commit.

Current implementations of time-based transactional memories use a single global clock that is incremented by the commit operation for each update transaction that commits. In large systems with frequent commits, the contention on this global counter can thus become a major bottleneck.

We present a scalable replacement for this global counter and describe how the Lazy Snapshot Algorithm (LSA), which forms the basis for our LSA-STM time-based software transactional memory, has to be changed to support these new time bases. In particular, we show how the global counter can be replaced (1) by an external or physical clock that can be accessed efficiently, and (2) by multiple synchronized physical clocks.

REFERENCES

• 1: F. Cristian. A probabilistic approach to distributed clock synchronization. Distributed Computing, 3:146--158, 1989.
• 2: D. Dice, O. Shalev, and N. Shavit. Transactional Locking II. In 20th International Symposium on Distributed Computing (DISC), September 2006.
• 3: D. Dice and N. Shavit. What really makes transactions fast? In TRANSACT, Jun 2006.
• 4: Christof Fetzer , Flaviu Cristian, Integrating External and Internal Clock Synchronization, Real-Time Systems, v.12 n.2, p.123-171, March 1997 [doi>10.1023/A:1007905917490]
• 5: 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
• 6: Tim Harris , Mark Plesko , Avraham Shinnar , David Tarditi, Optimizing memory transactions, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada
• 7: 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]
• 8: Robin Holt, SGI. Personal Communication.
• 9: T. Riegel, P. Felber, and C. Fetzer. A Lazy Snapshot Algorithm with Eager Validation. In 20th International Symposium on Distributed Computing (DISC), September 2006.
• 10: T. Riegel, C. Fetzer, and P. Felber. Snapshot isolation for software transactional memory. In TRANSACT06, Jun 2006.
• 11: Bratin Saha , Ali-Reza Adl-Tabatabai , Richard L. Hudson , Chi Cao Minh , Benjamin Hertzberg, McRT-STM: a high performance software transactional memory system for a multi-core runtime, Proceedings of the eleventh ACM SIGPLAN symposium on Principles and practice of parallel programming, March 29-31, 2006, New York, New York, USA [doi>10.1145/1122971.1123001]
• 12: M. F. Spear, V. J. Marathe, W. N. S. III, and M. L. Scott. Conflict detection and validation strategies for software transactional memory. In 20th International Symposium on Distributed Computing (DISC), September 2006.
• 13: Cheng Wang , Wei-Yu Chen , Youfeng Wu , Bratin Saha , Ali-Reza Adl-Tabatabai, Code Generation and Optimization for Transactional Memory Constructs in an Unmanaged Language, Proceedings of the International Symposium on Code Generation and Optimization, p.34-48, March 11-14, 2007 [doi>10.1109/CGO.2007.4]

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming

General Terms:
Algorithms, Performance

Keywords:
transactional memory