Optimistic concurrency for clusters via speculative locking

ABSTRACT

Transactional memory and speculative locking are optimistic concurrency control mechanisms, whose goal is to enable highly concurrent execution while reducing the programming effort. The same basic idea lies in the heart of both methods: optimistically execute a critical code segment, determine whether there have been data conflicts and roll back in case validation fails. Transactional memory is widely considered to have advantages over lock-based synchronization on shared memory multiprocessors. Several recent works suggest employment of transactional memory in a distributed environment. However, being derived from traditional shared-memory design space, these schemes seem to be not "optimistic" enough for this setting. Each thread must validate the current transaction before proceeding to the next. Hence, blocking remote requests whose purpose is to detect/avoid data conflicts are placed on the critical path and thus delay execution.

In this paper, we investigate whether in light of the above shortcomings speculative locking can be a suitable alternative for transactional memory in a distributed environment. We present a novel distributed speculative locking scheme and compare its properties to the existing distributed transactional memory protocols. Despite the conceptual similarity to transactional memory, the distributed implementation of speculative locking manages to overlap communication with computation. It allows a thread to speculatively acquire multiple locks simultaneously, which is analogous to executing one transaction before validating the previous.

REFERENCES

• 1: Robert L. Bocchino , Vikram S. Adve , Bradford L. Chamberlain, Software transactional memory for large scale clusters, Proceedings of the 13th ACM SIGPLAN Symposium on Principles and practice of parallel programming, February 20-23, 2008, Salt Lake City, UT, USA [doi>10.1145/1345206.1345242]
• 2: B. Carlstrom, J. Chung, H. Chafi, A. McDonald, C. Minh, L. Hammond, C. Kozyrakis, and K. Olukotun. Transactional Execution of Java Programs. SCOOL' 05.
• 3: M. Factor, A. Schuster, and K. Shagin. JavaSplit: A runtime for execution of monolithic java programs on heterogeneous collections of commodity workstations. In IEEE Fifth Int'l Conference on Cluster Computing, December 2003.
• 4: M. Factor, A. Schuster, and K. Shagin. Handbook of Parallel Computing: Models, Algorithms and Applications. Chapman and Hall, December 2007.
• 5: Chris Gniady , Babak Falsafi, Speculative Sequential Consistency with Little Custom Storage, Proceedings of the 2002 International Conference on Parallel Architectures and Compilation Techniques, p.179-188, September 22-25, 2002
• 6: Chris Gniady , Babak Falsafi , T. N. Vijaykumar, Is SC + ILP = RC?, ACM SIGARCH Computer Architecture News, v.27 n.2, p.162-171, May 1999
• 7: S. Gopal , T. Vijaykumar , J. Smith , G. Sohi, Speculative Versioning Cache, Proceedings of the 4th International Symposium on High-Performance Computer Architecture, p.195, January 31-February 04, 1998
• 8: 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]
• 9: Tim Harris , Keir Fraser, Language support for lightweight transactions, ACM SIGPLAN Notices, v.38 n.11, November 2003
• 10: Tim Harris , Simon Marlow , Simon Peyton Jones , Maurice Herlihy, Composable memory transactions, Communications of the ACM, v.51 n.8, August 2008 [doi>10.1145/1378704.1378725]
• 11: Maurice Herlihy , Victor Luchangco , Mark Moir, A flexible framework for implementing software transactional memory, ACM SIGPLAN Notices, v.41 n.10, October 2006
• 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, ACM SIGARCH Computer Architecture News, v.21 n.2, p.289-300, May 1993
• 14: M. Herlihy and Y. Sun. Distributed transactional memory for metric-space networks. Distributed Computing, 20(3):195--208, October 2007.
• 15: Christos Kotselidis , Mohammad Ansari , Kim Jarvis , Mikel Luján , Chris Kirkham , Ian Watson, DiSTM: A Software Transactional Memory Framework for Clusters, Proceedings of the 2008 37th International Conference on Parallel Processing, p.51-58, September 09-11, 2008 [doi>10.1109/ICPP.2008.59]
• 16: Venkata Krishnan , Josep Torrellas, A Chip-Multiprocessor Architecture with Speculative Multithreading, IEEE Transactions on Computers, v.48 n.9, p.866-880, September 1999 [doi>10.1109/12.795218]
• 17: Kaloian Manassiev , Madalin Mihailescu , Cristiana Amza, Exploiting distributed version concurrency in a transactional memory cluster, 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.1123002]
• 18: Milo Martin , Colin Blundell , E. Lewis, Subtleties of Transactional Memory Atomicity Semantics, IEEE Computer Architecture Letters, v.5 n.2, p.17, July 2006 [doi>10.1109/L-CA.2006.18]
• 19: José F. Martínez , Josep Torrellas, Speculative synchronization: applying thread-level speculation to explicitly parallel applications, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
• 20: Ravi Rajwar , James R. Goodman, Speculative lock elision: enabling highly concurrent multithreaded execution, Proceedings of the 34th annual ACM/IEEE international symposium on Microarchitecture, December 01-05, 2001, Austin, Texas
• 21: Peter Rundberg , Per Stenström, Speculative Lock Reordering: Optimistic Out-of-Order Execution of Critical Sections, Proceedings of the 17th International Symposium on Parallel and Distributed Processing, p.11.1, April 22-26, 2003
• 22: R. Samanta , A. Bilas , L. Iftode , J. Singh, Home-Based SVM Protocols for SMP Clusters: Design and Performance, Proceedings of the 4th International Symposium on High-Performance Computer Architecture, p.113, January 31-February 04, 1998
• 23: Nir Shavit , Dan Touitou, Software transactional memory, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.204-213, August 20-23, 1995, Ottowa, Ontario, Canada [doi>10.1145/224964.224987]
• 24: L. A. Smith and J. M. Bull. A multithreaded Java Grande benchmark suite. In Proc. of the Third Workshop on Java for High Performance Computing, 2001.
• 25: Janice M. Stone , Harold S. Stone , Philip Heidelberger , John Turek, Multiple Reservations and the Oklahoma Update, IEEE Parallel & Distributed Technology: Systems & Technology, v.1 n.4, p.58-71, November 1993 [doi>10.1109/88.260295]
• 26: Willy Zwaenepoel , John K. Bennett , John B. Carter , Pete Keleher, Munin: distributed shared memory using multi-protocol release consistency, IEEE Computer Society Technical Committee Newsletter on Operating Systems and Application Environments, v.5 n.4, p.11, Winter 1991

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS

Keywords:
distributed computing, optimistic concurrency control