CAR-STM: scheduling-based collision avoidance and resolution for software transactional memory

ABSTRACT

Transactional memory (TM) is a key concurrent programming abstraction. Several software-based transactional memory (STM) implementations have been developed in recent years. All STM implementations must guarantee transaction atomicity but different STM implementations may provide different progress guarantees. In order to ensure progress, an STM implementation must resolve transaction conflicts. This is done either by the implementation itself or by delegating conflict resolution to a separate contention manager module that tries to resolve transaction collisions once they are detected.

We present CAR-STM, a scheduling-based mechanism for STM Collision Avoidance and Resolution, that can be incorporated into existing STM implementations. CAR-STM maintains per-core transaction queues and schedules a thread while it is performing a transaction. CAR-STM employs the following two novel collision reduction techniques: (1) seriailizing contention managers resolve conflicts by aborting one transaction and moving it to the transactions queue of the other, effectively serializing the execution of these transactions and ensuring they will not collide again. (2) Proactive collision reduction allows applications to provide information about transactions' collision-probability. CAR-STM uses this information to pre-assign transactions that are more likely to collide to the same core.

We have incorporated CAR-STM into the University of Rochester's STM (RSTM) and compared the performance of the new implementation with that of the original RSTM by using STMBench7. Our results show that the new implementation provides orders-of-magnitude reduction of execution times and improved throughput for almost all concurrency levels. Additionally, since CAR-STM greatly reduces the unpredictable influence of operating-system scheduling on STM performance, the new implementation provides a much more stable performance. In contrast, the performance of the original RSTM implementation on STMBench7 workloads exhibits extremely high variance. Though our paper focuses on software transactional memory, we believe the ideas introduced by CAR-STM may prove useful also for hybrid implementations of transactional memory.

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: Hagit Attiya , Leah Epstein , Hadas Shachnai , Tami Tamir, Transactional contention management as a non-clairvoyant scheduling problem, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA [doi>10.1145/1146381.1146428]
• 3: T. Bai, X. Shen, C. Zhang, W. N. Scherer III, C. Ding, and M. L. Scott. A key-based adaptive transactional memory executor. In IPDPS, pages 1--8, 2007.
• 4: 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
• 5: K. Fraser. Practical lock-freedom. Ph. D. dissertation, UCAM-CL-TR-579, Computer Laboratory, University of Cambridge, 2004.
• 6: R. Guerraoui, M. Herlihy, and B. Pochon. Polymorphic contention management. In DISC, pages 303--323, 2005.
• 7: Rachid Guerraoui , Maurice Herlihy , Bastian Pochon, Towards a theory of transactional contention managers, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA [doi>10.1145/1146381.1146429]
• 8: Rachid Guerraoui , Michal Kapalka , Jan Vitek, STMBench7: a benchmark for software transactional memory, ACM SIGOPS Operating Systems Review, v.41 n.3, June 2007
• 9: Lance Hammond , Vicky Wong , Mike Chen , Brian D. Carlstrom , John D. Davis , Ben Hertzberg , Manohar K. Prabhu , Honggo Wijaya , Christos Kozyrakis , Kunle Olukotun, Transactional Memory Coherence and Consistency, Proceedings of the 31st annual international symposium on Computer architecture, p.102, June 19-23, 2004, München, Germany
• 10: 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
• 11: M. Herlihy. SXM software transactional memory package for C\#. http://www.cs.brown.edu/ mph.
• 12: 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]
• 13: 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
• 14: Sanjeev Kumar , Michael Chu , Christopher J. Hughes , Partha Kundu , Anthony Nguyen, Hybrid transactional memory, 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.1123003]
• 15: V. J. Marathe, W. N. S. III, and M. L. Scott. Adaptive software transactional memory. In DISC, pages 354--368, 2005.
• 16: V. J. Marathe, M. F. Spear, C. Heriot, A. Acharya, D. Eisenstat, I. W. N. Scherer, and M. L. Scott. Lowering the overhead of nonblocking software transactional memory. In Workshop on Languages, Compilers, and Hardware Support for Transactional Computing (TRANSACT06),, 2006.
• 17: K. E. Moore, J. Bobba, M. J. Moravan, M. D. Hill, and D. A. Wood. Logtm: Log-based transactional memory. In Proceedings of the 12th International Conference on High Performance Computer Architecture, pages 254--265, 2006.
• 18: 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
• 19: 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
• 20: Christopher J. Rossbach , Owen S. Hofmann , Donald E. Porter , Hany E. Ramadan , Bhandari Aditya , Emmett Witchel, TxLinux: using and managing hardware transactional memory in an operating system, Proceedings of twenty-first ACM SIGOPS symposium on Operating systems principles, October 14-17, 2007, Stevenson, Washington, USA
• 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: 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]
• 23: N. Shavit and D. Touitou. Software transactional memory. Distributed Computing, 10(2):99--116, 1997.
• 24: Gerhard Weikum , Gottfried Vossen, Transactional information systems: theory, algorithms, and the practice of concurrency control and recovery, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2001
• 25: R. M. Yoo and H. S. Lee. Adaptive transaction scheduling for transactional memory systems. Georgia Institute of Technology Technical Report GIT-CERCS-07-04, 2007.

INDEX TERMS

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

General Terms:
Algorithms, Experimentation, Performance

Keywords:
collision avoidance and reduction, contention management, scheduling, synchronization, transactional memory