Extending concurrency of transactional memory programs by using value prediction

ABSTRACT

Transactional Memory (TM) is an optimistic speculative synchronization scheme that provides atomic execution for a region of code marked as a transaction by the programmer. TM avoids many of the problems associated with lock-based synchronization and can make writing parallel programs relatively easier. Programs with critical sections that are not heavily contended benefit from the optimistic nature of TM systems. However, for heavily contended critical sections, performance can degrade due to conflicts leading to stalls and expensive rollbacks. In this paper, we look into the nature of the shared data involved in conflicts for TM systems. We find that most transactions have conflicts around a few shared addresses, and shared-conflicting data is often updated in a predictable manner by different transactions. We propose using a memory-level value predictor to capture this predictability for such data structures and increase overall concurrency by satisfying loads from conflicting transactions with predicted values, instead of stalling. In this paper, we present one possible design and implementation of a TM system with a value predictor. Our benchmark results show that the value predictor can capture this predictable behavior for most benchmarks and can improve performance of TM programs by improving concurrency and minimizing stalls and rollbacks.

REFERENCES

• 1: SPECjbb2000. http://www.spec.org/jbb200.
• 2: C. Scott Ananian , Krste Asanovic , Bradley C. Kuszmaul , Charles E. Leiserson , Sean Lie, Unbounded Transactional Memory, IEEE Micro, v.26 n.1, p.59-69, January 2006 [doi>2006-02-17 02:00:03.800]
• 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, IEEE Micro, v.28 n.1, p.32-41, January 2008 [doi>10.1109/MM.2008.11]
• 4: Marcelo Cintra , Josep Torrellas, Eliminating Squashes Through Learning Cross-Thread Violations in Speculative Parallelization for Multiprocessors, Proceedings of the 8th International Symposium on High-Performance Computer Architecture, p.43, February 02-06, 2002
• 5: Lance Hammond , Brian D. Carlstrom , Vicky Wong , Michael Chen , Christos Kozyrakis , Kunle Olukotun, Transactional Coherence and Consistency: Simplifying Parallel Hardware and Software, IEEE Micro, v.24 n.6, p.92-103, November 2004 [doi>10.1109/MM.2004.91]
• 6: 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]
• 7: 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
• 8: Alain Kägi , Doug Burger , James R. Goodman, Efficient synchronization: let them eat QOLB, Proceedings of the 24th annual international symposium on Computer architecture, p.170-180, June 01-04, 1997, Denver, Colorado, United States
• 9: 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]
• 10: Peter S. Magnusson , Magnus Christensson , Jesper Eskilson , Daniel Forsgren , Gustav Hållberg , Johan Högberg , Fredrik Larsson , Andreas Moestedt , Bengt Werner, Simics: A Full System Simulation Platform, Computer, v.35 n.2, p.50-58, February 2002 [doi>10.1109/2.982916]
• 11: Milo M. K. Martin , Daniel J. Sorin , Bradford M. Beckmann , Michael R. Marty , Min Xu , Alaa R. Alameldeen , Kevin E. Moore , Mark D. Hill , David A. Wood, Multifacet's general execution-driven multiprocessor simulator (GEMS) toolset, ACM SIGARCH Computer Architecture News, v.33 n.4, November 2005 [doi>10.1145/1105734.1105747]
• 12: John M. Mellor-Crummey , Michael L. Scott, Algorithms for scalable synchronization on shared-memory multiprocessors, ACM Transactions on Computer Systems (TOCS), v.9 n.1, p.21-65, Feb. 1991 [doi>10.1145/103727.103729]
• 13: C. C. Minh et al. STAMP: Stanford transactional applications for multi-processing. In IEEE Intl. Symp. on Workload Characterization, pages 35--46, 2008.
• 14: K.E. Moore, J. Bobba, et al. LogTM: log-based transactional memory. In Intl. Symp. on High-Perf. Comput. Archit., pages 254--265, 2006.
• 15: R. Rajwar and J. R. Goodman. Transactional lock-free execution of lock-based programs. SIGPLAN Not., 37(10):5--17, 2002.
• 16: 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
• 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: J. Gregory Steffan , Christopher B. Colohan , Antonia Zhai , Todd C. Mowry, Improving Value Communication for Thread-Level Speculation, Proceedings of the 8th International Symposium on High-Performance Computer Architecture, p.65, February 02-06, 2002
• 19: Sun Microsystems. UltraSPARC III Cu User's manual, 2004. Version 2.2.1.
• 20: S. Woo et al. Methodological considerations and characterization of the SPLASH-2 parallel application suite. In Intl. Symp. on Comput. Archit., 1995

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.4 Parallel Architectures

General Terms:
Design, Performance

Keywords:
logtm, transactional memory, value prediction