Transactional memory and the birthday paradox

ABSTRACT

Many word-based Software TransactionalMemory systems (STMs) have been proposed using tagless ownership tables, where read and write permissions are granted at the granularity of all addresses that map to a given ownership table entry. This optimization to reduce overhead potentially results in false conflicts. Using address traces from a multithreaded program, we demonstrate that the frequency of these false conflicts grows superlinearly with both the TM data footprint and concurrency and that increasing the size of the ownership table results in only a sub-linear reduction in conflict rate. These somewhat surprising relationships have a theoretical foundation that is also responsible for the (naively) unintuitive statistical result generally referred to as the "Birthday Paradox." We present an analytical model based on random population of an ownership table by concurrently executing transactions that correctly predicts the trends in measured data. These results call into question the viability of such an optimization that can undermine the scalability and concurrency claims of software transactional memory.

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: Peter Damron , Alexandra Fedorova , Yossi Lev , Victor Luchangco , Mark Moir , Daniel Nussbaum, Hybrid transactional memory, Proceedings of the 12th international conference on Architectural support for programming languages and operating systems, October 21-25, 2006, San Jose, California, USA
• 3: 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
• 4: J. R. Larus and R. Rajwar. Transactional Memory. Morgan and Claypool, Dec. 2006.
• 5: N. Shavit, D. Dice, and O. Shalev. Transactional Locking II. In TRANSACT, 2006.
• 6: C. Zilles and R. Rajwar. Transactional Memory and the Birthday Paradox. Technical Report UIUCDCS-R-2007-2835, University of Illinois at Urbana-Champaign, 2007.

INDEX TERMS

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

Additional Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY

General Terms:
Algorithms, Performance, Theory

Keywords:
birthdays, concurrency, transactional memory