Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Parallel programming is receiving renewed attention with the advent of multi-core CPU architectures. The Transactional Memory (TM) paradigm has the potential to provide good speedup and make parallel programming easier to adopt. Under low contention, it has been shown that TM programs can outperform standard lock-based programs. However, under high contention, performance of TM programs can degrade. Previous work has shown that we can use either data forwarding or value prediction to improve performance under high contention. Both these techniques demand significant changes to the architecture and coherence protocol above and beyond those required by TM.

In this work, we analyze and compare these approaches. Our objective is to find a solution that improves performance without needing significant hardware additions or changes to the coherence protocol. We observe that for most transactions conflicts are limited to only a few threads at a time. We design a system that uses this knowledge to reduce the hardware for a TM system that tries to avoid conflicts using early value communication. Our results show that we can get comparable performance of the proposed techniques with minimal extra hardware.

REFERENCES

• 1: 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]
• 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, ACM SIGARCH Computer Architecture News, v.35 n.2, May 2007
• 3: 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]
• 4: 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
• 5: Maurice Herlihy, Victor Luchango, Mark Moir, and III William N. Scherer. Software transactional memory for dynamic-sized data structures. pages 92--101, Jul 2003.
• 6: 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
• 7: 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]
• 8: 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]
• 9: 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]
• 10: 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]
• 11: Chi Cao Minh, JaeWoong Chung, Christos Kozyrakis, and Kunle Olukotun. Stamp: Stanford transactional applications for multi-processing. In Proceedings of The IEEE International Symposium on Workload Characterization Sep 2008.
• 12: K. E. Moore, J. Bobba, M. J. Moravan, M. D. Hill, and D. A. Wood. Logtm:log-based transactional memory. High-Performance Computer Architecture, 2006. The Twelfth International Symposium on pages 254--265, 11-15 Feb. 2006.
• 13: Salil Mohan Pant , Gregory T. Byrd, Extending concurrency of transactional memory programs by using value prediction, Proceedings of the 6th ACM conference on Computing frontiers, May 18-20, 2009, Ischia, Italy [doi>10.1145/1531743.1531748]
• 14: R. Rajwar, M. Herlihy, and K. Lai. Virtualizing transactional memory. pages 494--505, 2005.
• 15: Ravi Rajwar and James R. Goodman. Transactional lock-free execution of lock-based programs. SIGPLAN Not. 37(10):5--17, 2002.
• 16: 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]
• 17: Sun Microsystems. UltraSPARC III Cu User's manual 2004. Version 2. 2. 1.

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:
parallel programming, transactional memory, value prediction