Modeling software transactional memory with AnyLogic

ABSTRACT

A flexible simulation model is presented to study different variants of software transactional memory (STM), like pessimistic STM or optimistic STM either with inplace memory updates or write buffering.

The dynamic behavior of transactions is encoded in timed statecharts as provided by the simulation tool AnyLogic in its implementation of real-time UML. Their graphical representation helps to convey the key design issues of the simulation model within this publication. Statistically significant numeric results for varying parameters, like number of threads, number of transactional operations, number of transactional data objects, are obtained efficiently as part of a Parameter Variation Experiment.

REFERENCES

• 1: C. Scott Ananian , Krste Asanovic , Bradley C. Kuszmaul , Charles E. Leiserson , Sean Lie, Unbounded Transactional Memory, Proceedings of the 11th International Symposium on High-Performance Computer Architecture, p.316-327, February 12-16, 2005 [doi>10.1109/HPCA.2005.41]
• 2: Jayaram Bobba , Neelam Goyal , Mark D. Hill , Michael M. Swift , David A. Wood, TokenTM: Efficient Execution of Large Transactions with Hardware Transactional Memory, Proceedings of the 35th International Symposium on Computer Architecture, p.127-138, June 21-25, 2008
• 3: Jayaram Bobba , Kevin E. Moore , Haris Volos , Luke Yen , Mark D. Hill , Michael M. Swift , David A. Wood, Performance pathologies in hardware transactional memory, Proceedings of the 34th annual international symposium on Computer architecture, June 09-13, 2007, San Diego, California, USA
• 4: Luis Ceze , James Tuck , Josep Torrellas , Calin Cascaval, Bulk Disambiguation of Speculative Threads in Multiprocessors, Proceedings of the 33rd annual international symposium on Computer Architecture, p.227-238, June 17-21, 2006
• 5: Weihaw Chuang , Satish Narayanasamy , Ganesh Venkatesh , Jack Sampson , Michael Van Biesbrouck , Gilles Pokam , Brad Calder , Osvaldo Colavin, Unbounded page-based 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
• 6: XJ Technologies Company. Anylogic 6.2.2. Multi-method simulation software, Petersburg, Russian Federation, http://www.xjtek.com/, 2009.
• 7: 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
• 8: David Dice, Ori Shalev, and Nir Shavit. Transactional locking II. In Proc. 20th Int. Symposium on Distributed Computing (DISC'06), pages 194--208, Stockholm, Sweden, February 2006.
• 9: Pascal Felber , Christof Fetzer , Torvald Riegel, Dynamic performance tuning of word-based software transactional memory, Proceedings of the 13th ACM SIGPLAN Symposium on Principles and practice of parallel programming, February 20-23, 2008, Salt Lake City, UT, USA [doi>10.1145/1345206.1345241]
• 10: Jim Gray , Andreas Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1992
• 11: Lance Hammond , Brian D. Carlstrom , Vicky Wong , Ben Hertzberg , Mike Chen , Christos Kozyrakis , Kunle Olukotun, Programming with transactional coherence and consistency (TCC), Proceedings of the 11th international conference on Architectural support for programming languages and operating systems, October 07-13, 2004, Boston, MA, USA
• 12: Armin Heindl and Gilles Pokam. An analytical performance model of software transactional memory. In Proc. IEEE Int. Symposium on Performance Analysis of Systems and Software (ISPASS'09), Boston, MA, USA, April 2009.
• 13: 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]
• 14: 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
• 15: James Larus and Ravi Rajwar. Transactional Memory. Morgan & Claypool Publishers, 2007.
• 16: Virendra J. Marathe, Michael F. Spear, Christopher Heriot, Athul Acharya, David Eisenstat, William N. Scherer III, and Michael L. Scott. Lowering the overhead of nonblocking software transactional memory. In Proc. 1st ACM SIGPLAN Workshop on Languages, Compilers, and Hardware Support for Transactional Computing (TRANSACT'06), Ottawa, Canada, June 2006.
• 17: Chi Cao Minh, Jae Woong Chung, Christos Kozyrakis, and Kunle Olukotun. STAMP: Stanford Transactional Applications for Multi-Processing. In Proc. IEEE Int. Symposium on Workload Characterization (IISWC'08), pages 35--46, Seattle, WA, USA, September 2008.
• 18: Kevin E. Moore, Jayaram Bobba, Michelle J. Moravan, Mark D. Hill, and David A. Wood. LogTM: Log-based transactional memory. In Proc. 12th Int. Symposium on High-Performance Computer Architecture (HPCA'06), pages 254--265, Washington, DC, USA, 2006. IEEE Computer Society.
• 19: Yang Ni , Adam Welc , Ali-Reza Adl-Tabatabai , Moshe Bach , Sion Berkowits , James Cownie , Robert Geva , Sergey Kozhukow , Ravi Narayanaswamy , Jeffrey Olivier , Serguei Preis , Bratin Saha , Ady Tal , Xinmin Tian, Design and implementation of transactional constructs for C/C++, Proceedings of the 23rd ACM SIGPLAN conference on Object-oriented programming systems languages and applications, October 19-23, 2008, Nashville, TN, USA
• 20: Ravi Rajwar , Maurice Herlihy , Konrad Lai, Virtualizing Transactional Memory, ACM SIGARCH Computer Architecture News, v.33 n.2, p.494-505, May 2005
• 21: 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]
• 22: 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]
• 23: Alexander Thomasian, Concurrency control: methods, performance, and analysis, ACM Computing Surveys (CSUR), v.30 n.1, p.70-119, March 1998 [doi>10.1145/274440.274443]
• 24: Christoph von Praun , Rajesh Bordawekar , Calin Cascaval, Modeling optimistic concurrency using quantitative dependence analysis, Proceedings of the 13th ACM SIGPLAN Symposium on Principles and practice of parallel programming, February 20-23, 2008, Salt Lake City, UT, USA [doi>10.1145/1345206.1345234]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS