Abstract
This paper is motivated by the difficulty in writing correct high-performance programs. Writing shared-memory multi-threaded programs imposes a complex trade-off between programming ease and performance, largely due to subtleties in coordinating access to shared data. To ensure correctness programmers often rely on conservative locking at the expense of performance. The resulting serialization of threads is a performance bottleneck. Locks also interact poorly with thread scheduling and faults, resulting in poor system performance.We seek to improve multithreaded programming trade-offs by providing architectural support for optimistic lock-free execution. In a lock-free execution, shared objects are never locked when accessed by various threads. We propose Transactional Lock Removal (TLR) and show how a program that uses lock-based synchronization can be executed by the hardware in a lock-free manner, even in the presence of conflicts, without programmer support or software changes. TLR uses timestamps for conflict resolution, modest hardware, and features already present in many modern computer systems.TLR's benefits include improved programmability, stability, and performance. Programmers can obtain benefits of lock-free data structures, such as non-blocking behavior and wait-freedom, while using lock-protected critical sections for writing programs.
- A. R. Alameldeen, C. J. Mauer, M. Xu, P. J. Harper, M. M. Martin, D. J. Sorin, M. D. Hill, and D. A. Wood. Evaluating non-deterministic multi-threaded commercial workloads. In Fifth Workshop on Computer Architecture Evaluation Using Commercial Workloads, pages 30-38, Feb. 2002.Google Scholar
- J. Allemany and E. Felten. Performance issues in non-blocking synchronization on shared-memory multiprocessors. In Proceedings of the 11th ACM Symposium on Principles of Distributed Computing, pages 125-134, Aug. 1992. Google ScholarDigital Library
- T. E. Anderson. The performance of spin lock alternatives shared-memory multiprocessors. IEEE Transactions on Parallel and Distributed Systems, 1(1): 6-16, Jan. 1990. Google ScholarDigital Library
- G. Barnes. Method for implementing lock-free shared data structures. In Proceedings of the Fifth Annual ACM Symposium on Parallel Algorithms and Architectures, pages 261-270, June 1993. Google ScholarDigital Library
- P. A. Bernstein and N. Goodman. Concurrency control in distributed database systems. ACM Computing Surveys, 13(2):185-221, June 1981. Google ScholarDigital Library
- B. N. Bershad. Practical considerations for lock-free concurrent objects. Technical Report CMU-CS-91-183, School of Computer Science, Carnegie Mellon University, Pittsburgh, PA, Sept. 1991.Google Scholar
- K. P. Eswaran, J. Gray, R. A. Lorie, and I. L. Traiger. The notions of consistency and predicate locks in a database system. Communications of the ACM, 11:624-633, 1976. Google ScholarDigital Library
- K. Gharachorloo, A. Gupta, and J. L. Hennessy. Two techniques to enhance the performance of memory consistency models. In Proceedings of the 1991 International Conference on Parallel Processing, pages 355-364, Aug. 1991.Google Scholar
- J. R. Goodman, M. K. Vernon, and P. J. Woest. Efficient synchronization primitives for large-scale cache-coherent shared-memory multiprocessors. In Proceedings of the Third Symposium on Architectural Support for Programming Languages and Operating Systems, pages 64-75, Apr. 1989. Google ScholarDigital Library
- J. Gray. The transaction concept: Virtues and limitations. In Seventh International Conference on Very Large Data Bases, 144-154, Sept. 1981.Google Scholar
- M. Herlihy. Wait-free synchronization. ACM Transactions on Programming Languages and Systems, 13(1):124-149, Jan. 1991. Google ScholarDigital Library
- M. Herlihy. A methodology for implementing highly concurrent data objects. ACM Transactions on Programming Languages and Systems, 15(5):745-770, 1993. Google ScholarDigital Library
- M. Herlihy and J. E. B. Moss. Transactional Memory: Architectural support for lock-free data structures. In Proceedings of the 20th Annual International Symposium on Computer Architecture, pages 289-300, May 1993. Google ScholarDigital Library
- 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, Livermore, CA, Nov. 1987.Google Scholar
- N. P. Jouppi. Improving direct-mapped cache performance by the addition of a small fully-associative cache and prefetch buffers. In Proceedings of the 17th Annual International Symposium on Computer Architecture, pages 364-373, May 1990. Google ScholarDigital Library
- A. Kägi, D. Burger, and J. R. Goodman. Efficient synchronization: Let them eat QOLB. In Proceedings of the 24th Annual International Symposium on Computer Architecture, pages 170-180, June 1997. Google ScholarDigital Library
- S. Kaxiras and J. R. Goodman. Improving CC-NUMA performance using instruction-based prediction. In Proceedings of the Fifth International Symposium on High-Performance Architecture, pages 161-170, Jan. 1999. Google ScholarDigital Library
- L. I. Kontothanassis, R. W. Wisniewski, and M. L. Scott. Scheduler-conscious synchronization. ACM Transactions on Computer Systems, 15(1):3-40, 1997. Google ScholarDigital Library
- S. Kumar, D. Jiang, R. Chandra, and J. P. Singh. Evaluating synchronization on shared address space multiprocessors: Methodology and performance. In Proceedings of the 1999 SIGMETRICS Conference on Measurements and Modeling of Computer Systems, pages 23-34, May 1999. Google ScholarDigital Library
- H. Kung and J. T. Robinson. On optimistic methods of concurrency control. ACM Transactions on Database Systems, 6(2):213-226, June 1981. Google ScholarDigital Library
- L. Lamport. Concurrent reading and writing. Communications of the ACM, 20(11):806-811, 1977. Google ScholarDigital Library
- L. Lamport. Time, clocks, and the ordering of events in a distributed system. Communications of the ACM, 21:558-565, 1978. Google ScholarDigital Library
- K. M. Lepak and M. H. Lipasti. Temporally silent stores. In Proceedings of the Tenth Symposium on Architectural Support for Programming Languages and Operating Systems, Oct. 2002. Google ScholarDigital Library
- J. F. Martínez and J. Torrellas. Speculative locks for concurrent execution of critical sections in shared-memory multiprocessors. In Workshop on Memory Performance Issues, June 2001.Google Scholar
- J. F. Martínez and J. Torrellas. Speculative synchronization: Applying thread-level speculation to explicitly parallel applications. In Proceedings of the Tenth Symposium on Architectural Support for Programming Languages and Operating Systems, Oct. 2002. Google ScholarDigital Library
- J. M. Mellor-Crummey and M. L. Scott. Algorithms for scalable synchronization on shared-memory multiprocessors. ACM Transactions on Computer Systems, 9(1):21-65, Feb. 1991. Google ScholarDigital Library
- M. M. Michael and M. L. Scott. Simple, fast, and practical nonblocking and blocking concurrent queue algorithms. In Proceedings of the 15th ACM Symposium on Principles of Distributed Computing, pages 267-275, May 1996. Google ScholarDigital Library
- M. M. Michael and M. L. Scott. Nonblocking algorithms and pre-emption-safe locking on multiprogrammed shared memory multiprocessors. Journal of Parallel and Distributed Computing, 51(1):1-26, 1998. Google ScholarDigital Library
- R. Rajwar. Speculation-Based Techniques for Transactional Lock-Free Execution of Lock-Based Programs. PhD thesis, University of Wisconsin, Madison, WI, 2002. Google ScholarDigital Library
- R. Rajwar and J. R. Goodman. Speculative Lock Elision: Enabling highly concurrent multithreaded execution. In Proceedings of the 34th International Symposium on Microarchitecture, pages 294-305, Dec. 2001. Google ScholarDigital Library
- R. Rajwar, A. Kägi, and J. R. Goodman. Improving the throughput of synchronization by insertion of delays. In Proceedings of the Sixth International Symposium on High-Performance Computer Architecture, pages 168-179, Jan. 2000.Google Scholar
- D. J. Rosenkrantz, R. E. Stearns, and P. M. Lewis. System level concurrency control for distributed database systems. ACM Transactions on Database Systems, 3(2):178-198, June 1978. Google ScholarDigital Library
- N. Shavit and D. Touitou. Software Transactional Memory. In Proceedings of the 14th ACM Symposium on Principles of Distributed Computing, pages 204-213, Aug. 1995. Google ScholarDigital Library
- J. P. Singh, W.-D. Weber, and A. Gupta. SPLASH: Stanford parallel applications for shared memory. Computer Architecture News, 20(1):5-44, Mar. 1992. Google ScholarDigital Library
- A. Singhal, D. Broniarczyk, F. M. Cerauskis, J. Price, L. Yuan, G. Cheng, D. Doblar, S. Fosth, N. Agarwal, K. Harvey, and E. Hagersten. Gigaplane: A high performance bus for large SMPs. In Proceedings of the Symposium on High Performance Interconnects IV, pages 41-52, Aug. 1996.Google Scholar
- J. M. Stone, H. S. Stone, P. Heidelberger, and J. Turek. Multiple reservations and the Oklahoma update. IEEE Parallel & Distributed Technology, 1(4):58-71, Nov. 1993. Google ScholarDigital Library
- J. Turek, D. Shasha, and S. Prakash. Locking without blocking: Making lock based concurrent data structure algorithms nonblocking. In Proceedings of the 11th ACM Symposium on Principles of Distributed Computing, pages 212-222, Aug. 1992. Google ScholarDigital Library
- J. D. Valois. Lock-Free Data Structures. PhD thesis, Rochester Institute of Technology, Rochester, NY, 1995. Google ScholarDigital Library
- S. C. Woo, M. Ohara, E. Torrie, J. P. Singh, and A. Gupta. The SPLASH-2 programs: Characterization and methodological considerations. In Proceedings of the 22nd Annual International Symposium on Computer Architecture, pages 24-36, June 1995. Google ScholarDigital Library
Index Terms
- Transactional lock-free execution of lock-based programs
Recommendations
Transactional lock-free execution of lock-based programs
ASPLOS X: Proceedings of the 10th international conference on Architectural support for programming languages and operating systemsThis paper is motivated by the difficulty in writing correct high-performance programs. Writing shared-memory multi-threaded programs imposes a complex trade-off between programming ease and performance, largely due to subtleties in coordinating access ...
Transactional lock-free execution of lock-based programs
This paper is motivated by the difficulty in writing correct high-performance programs. Writing shared-memory multi-threaded programs imposes a complex trade-off between programming ease and performance, largely due to subtleties in coordinating access ...
Comments