Testing patterns for software transactional memory engines

ABSTRACT

The emergence of multi-core processors is promoting the use of concurrency and multithreading. To raise the abstraction level of synchronization constructs is fundamental to ease the development of concurrent software, and Software Transactional Memory (STM) is a good approach towards such goal. However, execution environment issues such as the processor instruction set, caching policy, and memory model, may have strong influence upon the reliability of STM engines. This paper addresses the testing of STM engines aiming at improving their reliability and independence from execution environment. From our experience with porting and extending a specific STM engine, we report on some of the bugs found and synthesize some testing patterns that proved to be useful at testing STM engines.

REFERENCES

• 1: D. Dice, O. Shalev, and N. Shavit. Transactional locking ii. In Proc. of the 20th International Symposium on Distributed Computing (DISC 2006), pages 194--208, 2006.
• 2: David Dice and Nir Shavit. What really makes transactions faster? In Proceedings of the First ACM SIGPLAN Workshop on Languages, Compilers, and Hardware Support for Transactional Computing. Jun 2006.
• 3: Robert Ennals. Software transactional memory should not be obstruction-free. Technical Report IRC-TR-06-052, Intel Research Cambridge Tech Report, Jan 2006.
• 4: 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
• 5: 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]
• 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: Chaiyasit Manovit , Sudheendra Hangal , Hassan Chafi , Austen McDonald , Christos Kozyrakis , Kunle Olukotun, Testing implementations of transactional memory, Proceedings of the 15th international conference on Parallel architectures and compilation techniques, September 16-20, 2006, Seattle, Washington, USA [doi>10.1145/1152154.1152177]
• 9: 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]
• 10: R. M. Tomasulo. An efficient algorithm for exploiting multiple arithmetic units. IBM Journal of Research and Development, 11(1):25, 1967.

INDEX TERMS

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

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Diagnostics
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Synchronization

General Terms:
Algorithms, Experimentation, Performance, Reliability

Keywords:
concurrency, debugging, software transactional memory, testing, testing patterns