Transactional memory: architectural support for lock-free data structures

Abstract

A shared data structure is lock-free if its operations do not require mutual exclusion. If one process is interrupted in the middle of an operation, other processes will not be prevented from operating on that object. In highly concurrent systems, lock-free data structures avoid common problems associated with conventional locking techniques, including priority inversion, convoying, and difficulty of avoiding deadlock. This paper introduces transactional memory, a new multiprocessor architecture intended to make lock-free synchronization as efficient (and easy to use) as conventional techniques based on mutual exclusion. Transactional memory allows programmers to define customized read-modify-write operations that apply to multiple, independently-chosen words of memory. It is implemented by straightforward extensions to any multiprocessor cache-coherence protocol. Simulation results show that transactional memory matches or outperforms the best known locking techniques for simple benchmarks, even in the absence of priority inversion, convoying, and deadlock.

References

1. 1 A. Agarwal et al. The MIT Alewife machine: A large-scale distributed-memory multiprocessor. Technical Report TM-454, MIT Lab for Computer Science, 545 Technology Square, Cambridge MA 02139, March 1991. Extended version submitted for publication.
2. 2 J. Allemany and E.W. Felton. Performance issues in non-blocking synchronization on shared-memory multiprocessors. In Proceedings of the 11th Annual ACM Symposium on Principles of Distributed Computing, pages 125-134. ACM, August 1992.
3. 3 T.E. Anderson. The performance of spin lock alternatives for shared-memory multiprocessors. IEEE Transactions on Parallel and Distributed Systems, 1(1):6-16, January 1990.
4. 4 B.N. Bershad. Practical considerations for lock-free concurrent objects. Technical Report CMU-CS-91-183, Carnegie Mellon University, Pittsburgh, PA, September 1991.
5. 5 E. A. Brewer, C. N. Dellarocas, A. Colbrook, and W. E. Weihl. PROTEUS: A high-performance parallel architecture simulator. Technical Report MIT/LCSfl'R-516, Massachusetts Institute of Technology, September 1991.
6. 6 D. Chaiken, J. Kubiatowicz, and A. Agm'wal. LimitLESS directories: a scalable cache coherence scheme. In Proceedings of the 4th International Conference on Architectural Support for Programming Langauges and Operating Systems, pages 224-234. ACM, April 1991.
7. 7 A. Chang and M.F. Mergen. 801 storage: Architecture and programming. ACM Transactions on Computer Systems, 6(1):28-50, February 1988.
8. 8 Michel Dubois and Christoph Scheurich. Memory access dependencies in shared-memory multiprocessors. IEEE Transactions on Software Engineering, 16(6):660-673, June 1990.
9. 9 Michel Dubois, Christoph Scheurich, and Fay6 Briggs. Memory access buffering in multiprocessors. In Proceedings of the 13th Annual International Symposium on Computer Architecture, pages 434-442, June 1986.
10. 10 M. Franklin and G. S. Sohi. The expansible split window paradigm for exploiting fine-grain parallelism, in Proceedings of the 19th Annual International Symposium on Computer Architecture, pages 58-67. IEEE, May 1992.
11. 11 K. Gharachorloo and P. Gibl~ons. Detectitng violations of sequential consistency. In Proceedings of the 2nd Annual Symposium on Parallel Algorithms and Architectures, pages 316-326, July 1991.
12. 12 Kourosh Gharachorloo, Anoop Gupta, and John Hennessy. Performance evaluation of memory consistency models for shared-memory multiprocessors. In Fourth International Conference on Architectural Support for Programming Languages and Operating Systems, pages 245-257, April 1991.
13. 13 Kourosh Gharachorloo, Dan Lenoski, James Laudon, Phillip Gibbons, Anoop Gupta, and John Hennessy. Memory consistency and event ordering in scalable shared-memory multiprocessors, in Proceedings of the 17th Annual International Symposium on Computer Architecture, pages 15-26, June 1990.
14. 14 James R. Goodman. Cache consistency and sequential consistency. Technical Report 61, SCI Committee, March 1989.
15. 15 J.R. Goodman. Using cache memory to reduce processor-memory traffic. In Proceedings of the 12th International Symposium on Computer Architecture, pages 124-13 I. IEEE, June 1983.
16. 16 J.R. Goodman, M.K. Vernon, and P.J. Woest. Efficient synchronization primitives for large-scale cache-coherent multiprocessors. In Proceedings of the 3rd International Conference on Architectural Support for Programming Languates and Operating Systems, pages 64-75, April 1989.
17. 17 G. Graunke and S. Thakkar. Synchronization algorithms for shared-memory multiprocessors. IEEE Computer, 23(6):60-70, June 1990.
18. 18 J.N. Gray. Notes on Database Operating Systems, pages 393-481. Springer-Verlag, Berlin, 1978.
19. 19 M.P. Herlihy. A methodology for implementing highly concurrent data structures. In Proceedings of the Second ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pages 197-206, March 1990.
20. 20 M.P. Herlihy and J.E.B. Moss. Transactional memory: Architectural support for lock-free data structures. Technical Report 92/07, Digital Cambridge Research Lab, One Kendall Square, Cambridge MA 02139, December 1992.
21. 21 E.H. Jensen, G.W. Hagensen, and J.M. Broughton. A new approach to exclusive data access in shared memory multiprocessors. Technical Report UCRL-97663, Lawrence Livermore National Laboratory, November 1987.
22. 22 N. Jouppi. Improving direct mapped cache performance by the addition of a small fully-associative cache and prefetch buffers. In 17th Annual lnternationall Symposium on Computer Architecture, page 364. ACM SIGARCH, June 1990.
23. 23 T. Knight. An achitecture for mostly functional languages. In Conference on Lisp and Functional Programming, pages 105-112, August 1986.
24. 24 Leslie Lamport. How to make a multiprocessor computer that correctly executes multiprocess programs. IEEE Transactions on Computers, C-28(9):241-248, September 1979.
25. 25 H. Massalin and C. Pu. A lock-free multiprocessor OS kernel. Technical Report CUCS-005-91, Columbia University Computer Science Dept., 1991.
26. 26 J.M. Mellor-Crummey. Practical fetch-and-phi algorithms. Technical Report Technical Report 229, Computer Science Dept., University of Rochester, November 1987.
27. 27 John M. Mellor-Crummey and Michael L. Scott. Algorithms for scalable synchronization on shared-memory multiprocessors. A CM Transactions on Computer Systems, 9(1):21-65, February 1991.
28. 28 R. Metcalfe and D. Boggs. Ethernet: distributed packet switching for local computer networks. Communications of the ACM, 19(7):395-404, July 1976.
29. 29 MIPS Computer Company. The MIPS RISC architecture.
30. 30 L. Rudolph and Z. Segall. Dynamic decentralized cache schemes for MIMD parallel processors. In 11 th Annual International Symposium on Computer Architecture, pages 340-347, June 1984.
31. 31 R.L. Sites. Alpha Architecture Reference Manual. Digital Press, Maynard, MA, 1992.
32. 32 J. Wing and C. Gong. Testing and verifying concurrent objects. Journal of Parallel and Distributed Computing, 17(2), February 1993.

Index Terms

• Computer systems organization

  • Architectures

    • Parallel architectures

      • Multiple instruction, multiple data

• Computing methodologies

  • Modeling and simulation

    • Model development and analysis

      • Modeling methodologies

• General and reference

  • Cross-computing tools and techniques

    • Performance

• Hardware

  • Integrated circuits

    • Semiconductor memory

      • Dynamic memory