Scalable and reliable communication for hardware transactional memory

ABSTRACT

In a hardware transactional memory system with lazy versioning and lazy conflict detection, the process of transaction commit can emerge as a bottleneck. This is especially true for a large-scale distributed memory system where multiple transactions may attempt to commit simultaneously and coordination is required before allowing commits to proceed in parallel. In this paper, we propose novel algorithms to implement commit that are more scalable in terms of delay and are free of deadlocks/livelocks. We show that these algorithms have similarities with the token cache coherence concept and leverage these similarities to extend the algorithms to handle message loss and starvation scenarios. The proposed algorithms improve upon the state-of-the-art by yielding up to a 7X reduction in commit delay and up to a 48X reduction in network messages for commit. These translate into overall performance improvements of up to 66% (for synthetic workloads with average transaction length of 200 cycles), 35% (for average transaction length of 1000 cycles), and 8% (for average transaction length of 4000 cycles). For a small group of multi-threaded programs with frequent transaction commits, improvements of up to 8% were observed for a 32-node simulation.

REFERENCES

• 1: K. Agarwal, D. Sylvester, and D. Blaauw. Modeling and Analysis of Crosstalk Noise in Coupled RLC Interconnects. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 25(5), May 2006.
• 2: 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]
• 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, Proceedings of the 34th annual international symposium on Computer architecture, June 09-13, 2007, San Diego, California, USA
• 4: Jeffery A. Brown , Rakesh Kumar , Dean Tullsen, Proximity-aware directory-based coherence for multi-core processor architectures, Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures, June 09-11, 2007, San Diego, California, USA [doi>10.1145/1248377.1248398]
• 5: S. Burckhardt, R. Alur, and M. Martin. Verifying Safety of a Token Coherence Implementation by Parametric Compositional Refinement. In Proceedings of VMCAI, January 2005.
• 6: J. Cantin, M. Lipasti, and J. Smith. Dynamic Verification of Cache Coherence Protocols. In Proceedings of WMPI, June 2001.
• 7: 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
• 8: Luis Ceze , James Tuck , Pablo Montesinos , Josep Torrellas, BulkSC: bulk enforcement of sequential consistency, Proceedings of the 34th annual international symposium on Computer architecture, June 09-13, 2007, San Diego, California, USA
• 9: Hassan Chafi , Jared Casper , Brian D. Carlstrom , Austen McDonald , Chi Cao Minh , Woongki Baek , Christos Kozyrakis , Kunle Olukotun, A Scalable, Non-blocking Approach to Transactional Memory, Proceedings of the 2007 IEEE 13th International Symposium on High Performance Computer Architecture, p.97-108, February 10-14, 2007 [doi>10.1109/HPCA.2007.346189]
• 10: J. Chung, H. Chafi, A. McDonald, C. Minh, B. Carlstrom, C. Kozyrakis, and K. Olukotun. The Common Case Transactional Behavior of Multithreaded Programs. In Proceedings of HPCA-12, February 2006.
• 11: Marcelo Cintra , José F. Martínez , Josep Torrellas, Architectural support for scalable speculative parallelization in shared-memory multiprocessors, Proceedings of the 27th annual international symposium on Computer architecture, p.13-24, June 2000, Vancouver, British Columbia, Canada
• 12: Blas Cuesta , Antonio Robles , Jose Duato, An Effective Starvation Avoidance Mechanism to Enhance the Token Coherence Protocol, Proceedings of the 15th Euromicro International Conference on Parallel, Distributed and Network-Based Processing, p.47-54, February 07-09, 2007 [doi>10.1109/PDP.2007.22]
• 13: W. Dally. Workshop on On- and Off-Chip Interconnection Networks for Multicore Systems (OCIN), 2006. Workshop program and report at http://www.ece.ucdavis.edu/~ocin06/.
• 14: A. Deutsch. The Importance of Inductance and Inductive Coupling for On-chip Wiring. In Proceedings of IEEE 6th Topical Meeting on Electrical Performance of Electronic Packaging, October 1997.
• 15: Tudor Dumitraş , Sam Kerner , Radu Mărculescu, Towards on-chip fault-tolerant communication, Proceedings of the 2003 conference on Asia South Pacific design automation, January 21-24, 2003, Kitakyushu, Japan [doi>10.1145/1119772.1119817]
• 16: Ricardo Fernandez-Pascual , Jose M. Garcia , Manuel E. Acacio , Jose Duato, A Low Overhead Fault Tolerant Coherence Protocol for CMP Architectures, Proceedings of the 2007 IEEE 13th International Symposium on High Performance Computer Architecture, p.157-168, February 10-14, 2007 [doi>10.1109/HPCA.2007.346194]
• 17: R. Ho. On-Chip Wires: Scaling and Efficiency. PhD thesis, Stanford University, August 2003.
• 18: Y. Ismail and E. Friedman. On-Chip Inductance in High Speed Integrated Circuits. Kluwer Publishers, 2001.
• 19: Jongman Kim , Dongkook Park , Chrysostomos Nicopoulos , N. Vijaykrishnan , Chita R. Das, Design and analysis of an NoC architecture from performance, reliability and energy perspective, Proceedings of the 2005 ACM symposium on Architecture for networking and communications systems, October 26-28, 2005, Princeton, NJ, USA [doi>10.1145/1095890.1095915]
• 20: P. Kundu. On-Die Interconnects for Next Generation CMPs. In Workshop on On- and Off-Chip Interconnection Networks for Multicore Systems (OCIN), December 2006.
• 21: H. T. Kung , John T. Robinson, On optimistic methods for concurrency control, ACM Transactions on Database Systems (TODS), v.6 n.2, p.213-226, June 1981 [doi>10.1145/319566.319567]
• 22: Leslie Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, v.21 n.7, p.558-565, July 1978 [doi>10.1145/359545.359563]
• 23: J. R. Larus and R. Rajwar. Transactional Memory. Morgan & Claypool, 2006.
• 24: Milo M. K. Martin , Mark D. Hill , David A. Wood, Token coherence: decoupling performance and correctness, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 25: Michael R. Marty , Jesse D. Bingham , Mark D. Hill , Alan J. Hu , Milo M. K. Martin , David A. Wood, Improving Multiple-CMP Systems Using Token Coherence, Proceedings of the 11th International Symposium on High-Performance Computer Architecture, p.328-339, February 12-16, 2005 [doi>10.1109/HPCA.2005.17]
• 26: Michael R. Marty , Mark D. Hill, Coherence Ordering for Ring-based Chip Multiprocessors, Proceedings of the 39th Annual IEEE/ACM International Symposium on Microarchitecture, p.309-320, December 09-13, 2006 [doi>10.1109/MICRO.2006.14]
• 27: Albert Meixner , Daniel J. Sorin, Error Detection via Online Checking of Cache Coherence with Token Coherence Signatures, Proceedings of the 2007 IEEE 13th International Symposium on High Performance Computer Architecture, p.145-156, February 10-14, 2007 [doi>10.1109/HPCA.2007.346193]
• 28: Chi Cao Minh , Martin Trautmann , JaeWoong Chung , Austen McDonald , Nathan Bronson , Jared Casper , Christos Kozyrakis , Kunle Olukotun, An effective hybrid transactional memory system with strong isolation guarantees, Proceedings of the 34th annual international symposium on Computer architecture, June 09-13, 2007, San Diego, California, USA
• 29: K. Moore, J. Bobba, M. Moravan, M. Hill, and D. Wood. LogTM: Log-Based Transactional Memory. In Proceedings of HPCA-12, February 2006.
• 30: Shubhendu S. Mukherjee , Joel Emer , Steven K. Reinhardt, The Soft Error Problem: An Architectural Perspective, Proceedings of the 11th International Symposium on High-Performance Computer Architecture, p.243-247, February 12-16, 2005 [doi>10.1109/HPCA.2005.37]
• 31: Naveen Muralimanohar , Rajeev Balasubramonian , Norm Jouppi, Optimizing NUCA Organizations and Wiring Alternatives for Large Caches with CACTI 6.0, Proceedings of the 40th Annual IEEE/ACM International Symposium on Microarchitecture, p.3-14, December 01-05, 2007 [doi>10.1109/MICRO.2007.30]
• 32: Dongkook Park , Chrysostomos Nicopoulos , Jongman Kim , N. Vijaykrishnan , Chita R. Das, Exploring Fault-Tolerant Network-on-Chip Architectures, Proceedings of the International Conference on Dependable Systems and Networks, p.93-104, June 25-28, 2006 [doi>10.1109/DSN.2006.35]
• 33: Milos Prvulovic , María Jesús Garzarán , Lawrence Rauchwerger , Josep Torrellas, Removing architectural bottlenecks to the scalability of speculative parallelization, Proceedings of the 28th annual international symposium on Computer architecture, p.204-215, June 30-July 04, 2001, Göteborg, Sweden
• 34: 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
• 35: 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
• 36: Jose Renau , Karin Strauss , Luis Ceze , Wei Liu , Smruti Sarangi , James Tuck , Josep Torrellas, Thread-Level Speculation on a CMP can be energy efficient, Proceedings of the 19th annual international conference on Supercomputing, June 20-22, 2005, Cambridge, Massachusetts [doi>10.1145/1088149.1088178]
• 37: 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]
• 38: Semiconductor Industry Association. International Technology Roadmap for Semiconductors 2005.
• 39: Premkishore Shivakumar , Michael Kistler , Stephen W. Keckler , Doug Burger , Lorenzo Alvisi, Modeling the Effect of Technology Trends on the Soft Error Rate of Combinational Logic, Proceedings of the 2002 International Conference on Dependable Systems and Networks, p.389-398, June 23-26, 2002
• 40: D. Sorin, M. Hill, and D. Wood. Dynamic Verification of End-to-End Multiprocessor Invariants. In Proceedings of DSN, June 2003.
• 41: J. Greggory Steffan , Christopher B. Colohan , Antonia Zhai , Todd C. Mowry, A scalable approach to thread-level speculation, Proceedings of the 27th annual international symposium on Computer architecture, p.1-12, June 2000, Vancouver, British Columbia, Canada
• 42: Sarma B. K. Vrudhula , David Blaauw , Supamas Sirichotiyakul, Estimation of the likelihood of capacitive coupling noise, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA [doi>10.1145/513918.514085]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.4 Parallel Architectures
          Subjects: Distributed architectures

Additional Classification:
  B. Hardware
  B.8 Performance and Reliability
      B.8.0 General

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance, Reliability

Keywords:
algorithms for transaction commit, handling message loss, hardware transactional memory, on-chip network messages, reliability, token coherence