Refereeing conflicts in hardware transactional memory

ABSTRACT

In the search for high performance, most transactional memory (TM) systems execute atomic blocks concurrently and must thus be prepared for data conflicts. The TM system also needs to choose a policy to decide when and how to manage the resulting contention. In this paper, we analyze the interplay between conflict resolution time and contention management policy in the context of hardware-supported TM systems, highlighting both the implementation tradeoffs and the performance implications of the various points in the design space. We show that both policy decisions have a significant impact on the ability to exploit available parallelism and thereby affect overall performance. Our analysis corroborates previous research findings that stalling (especially prior to retrying an access rather than the entire transaction) helps side-step conflicts and avoid wasted work. We also demonstrate that conflict resolution time has the dominant effect on performance: lazy (which delays resolution to commit time) uncovers more parallelism than eager (which resolves conflicts at access time). Furthermore, Lazy's delayed conflict management decreases the likelihood of livelock while Eager needs sophisticated priority mechanisms. Finally, we evaluate a mixed conflict detection mode that detects write-write conflicts eagerly while detecting read-write conflicts lazily, and show that it provides a good compromise between flexibility and implementation complexity.

REFERENCES

• 1: Lee Baugh , Naveen Neelakantam , Craig Zilles, Using Hardware Memory Protection to Build a High-Performance, Strongly-Atomic Hybrid Transactional Memory, Proceedings of the 35th International Symposium on Computer Architecture, p.115-126, June 21-25, 2008
• 2: 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
• 3: 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
• 4: Shlomi Dolev , Danny Hendler , Adi Suissa, CAR-STM: scheduling-based collision avoidance and resolution for software transactional memory, Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, August 18-21, 2008, Toronto, Canada [doi>10.1145/1400751.1400769]
• 5: R. Guerraoui, M. Herlihy, and B. Pochon. Polymorphic Contention Management in SXM. In Proc. of the 19th Intl. Symp. on Distributed Computing, Cracow, Poland, Sept. 2005.
• 6: Rachid Guerraoui , Maurice Herlihy , Bastian Pochon, Toward a theory of transactional contention managers, 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.1073863]
• 7: Rachid Guerraoui , Michal Kapalka , Jan Vitek, STMBench7: a benchmark for software transactional memory, Proceedings of the 2nd ACM SIGOPS/EuroSys European Conference on Computer Systems 2007, March 21-23, 2007, Lisbon, Portugal
• 8: 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
• 9: 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]
• 10: M. Kulkarni, L. P. Chew, and K. Pingali. Using Transactions in Delaunay Mesh Generation. In Workshop on Transactional Memory Workloads, Ottawa, ON, Canada, June 2006.
• 11: Virendra J. Marathe , William N. Scherer , Michael L. Scott, Design tradeoffs in modern software transactional memory systems, Proceedings of the 7th workshop on Workshop on languages, compilers, and run-time support for scalable systems, p.1-7, October 22-23, 2004, Houston, Texas [doi>10.1145/1066650.1066660]
• 12: V. J. Marathe, M. F. Spear, C. Heriot, A. Acharya, D. Eisenstat, W. N. Scherer III, and M. L. Scott. Lowering the Overhead of Software Transactional Memory. In Proc. of the 1st ACM SIGPLAN Workshop on Transactional Computing, Ottawa, ON, Canada, June 2006. Expanded version available as TR 893, Dept. of Computer Science, Univ. of Rochester, Mar. 2006.
• 13: M. M. K. Martin, D. J. Sorin, B. M. Beckmann, M. R. Marty, M. Xu, A. R. Alameldeen, K. E. Moore, M. D. Hill, and D. A. Wood. Multifacet's General Execution-driven Multiprocessor Simulator (GEMS) Toolset. In ACM SIGARCH Computer Architecture News, Sept. 2005.
• 14: C. C. Minh, J. Chung, C. Kozyrakis, and K. Olukotun. STAMP: Stanford Transactional Applications for Multi-Processing. In Proc. of the 2008 IEEE Intl. Symp. on Workload Characterization, Seattle, WA, Sept. 2008.
• 15: K. E. Moore, J. Bobba, M. J. Moravan, M. D. Hill, and D. A. Wood. LogTM: Log-based Transactional Memory. In Proc. of the 12th Intl. Symp. on High Performance Computer Architecture, Austin, TX, Feb. 2006.
• 16: Hany E. Ramadan , Christopher J. Rossbach , Donald E. Porter , Owen S. Hofmann , Aditya Bhandari , Emmett Witchel, MetaTM/TxLinux: transactional memory for an operating system, Proceedings of the 34th annual international symposium on Computer architecture, June 09-13, 2007, San Diego, California, USA
• 17: Hany E. Ramadan , Christopher J. Rossbach , Emmett Witchel, Dependence-aware transactional memory for increased concurrency, Proceedings of the 2008 41st IEEE/ACM International Symposium on Microarchitecture, p.246-257, November 08-12, 2008 [doi>10.1109/MICRO.2008.4771795]
• 18: Jim Ruppert, A Delaunay refinement algorithm for quality 2-dimensional mesh generation, Journal of Algorithms, v.18 n.3, p.548-585, May 1995
• 19: W. N. Scherer III and M. L. Scott. Randomization in STM Contention Management (poster paper). In Proc. of the 24th ACM Symp. on Principles of Distributed Computing, Las Vegas, NV, July 2005.
• 20: M. L. Scott. Sequential Specification of Transactional Memory Semantics. In Proc. of the 1st ACM SIGPLAN Workshop on Transactional Computing, Ottawa, ON, Canada, June 2006.
• 21: Michael L. Scott , Michael F. Spear , Luke Dalessandro , Virendra J. Marathe, Delaunay Triangulation with Transactions and Barriers, Proceedings of the 2007 IEEE 10th International Symposium on Workload Characterization, p.107-113, September 27-29, 2007 [doi>10.1109/IISWC.2007.4362186]
• 22: Arrvindh Shriraman , Michael F. Spear , Hemayet Hossain , Virendra J. Marathe , Sandhya Dwarkadas , Michael L. Scott, An integrated hardware-software approach to flexible transactional memory, Proceedings of the 34th annual international symposium on Computer architecture, June 09-13, 2007, San Diego, California, USA
• 23: Arrvindh Shriraman , Sandhya Dwarkadas , Michael L. Scott, Flexible Decoupled Transactional Memory Support, Proceedings of the 35th International Symposium on Computer Architecture, p.139-150, June 21-25, 2008
• 24: Michael F. Spear , Luke Dalessandro , Virendra J. Marathe , Michael L. Scott, A comprehensive strategy for contention management in software transactional memory, Proceedings of the 14th ACM SIGPLAN symposium on Principles and practice of parallel programming, February 14-18, 2009, Raleigh, NC, USA
• 25: M. Tremblay and S. Chaudhry. A Third-Generation 65nm 16-Core 32-Thread Plus 32-Scout-Thread CMT. In Proc. of the Intl. Solid State Circuits Conf., San Francisco, CA, Feb. 2008.
• 26: Richard M. Yoo , Hsien-Hsin S. Lee, Adaptive transaction scheduling for transactional memory systems, Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures, June 14-16, 2008, Munich, Germany [doi>10.1145/1378533.1378564]

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Parallel processors**
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Design studies; Performance attributes

General Terms:
Design, Experimentation, Performance

Keywords:
conflict detection, contention management, transactional memory