William N. Scherer
Michael L. Scott
ABSTRACT
The obstruction-free Dynamic Software Transactional Memory (DSTM) system of Herlihy et al@. allows only one transaction at a time to acquire an object for writing. Should a second require an object currently in use, a contention manager must determine which may proceed and which must wait or abort.We analyze both new and existing policies for this contention management problem, using experimental results from a 16-processor SunFire machine. We consider both visible and invisible versions of read access, and benchmarks that vary in complexity, level of contention, tendency toward circular dependence, and mix of reads and writes. We present fair proportional-share prioritized versions of several policies, and identify a candidate default policy: one that provides, for the first time, good performance in every case we test. The tradeoff between visible and invisible reads remains application-specific: visible reads reduce the overhead for incremental validation when opening new objects, but the requisite bookkeeping exacerbates contention for the memory interconnect.
- T. E. Anderson. The Performance of Spin Lock Alternatives for Shared-Memory Multiprocessors. IEEE Trans. on Parallel and Distributed Systems, 1(1):6--16, Jan. 1990.]] Google Scholar
Digital Library
- K. M. Chandy and J. Misra. The Drinking Philosophers Problem. ACM Trans. on Programming Languages and Systems, 6(4):632--646, Oct. 1984.]] Google ScholarDigital Library
- K. Fraser. Practical Lock-Freedom. Ph.17emD. dissertation, UCAM-CL-TR-579, Computer Laboratory, University of Cambridge, Feb. 2004.]]Google Scholar
- T. Harris and K. Fraser. Language Support for Lightweight Transactions. In OOPSLA 2003 Conf. Proc., Anaheim, CA, Oct. 2003.]] Google ScholarDigital Library
- B. He, W. N. Scherer III, and M. L. Scott. Preemption Adaptivity in Time-Published Queue-Based Spin Locks. TR 867, Computer Science Dept., Univ. of Rochester, May 2005.]]Google Scholar
- M. Herlihy, V. Luchangco, and M. Moir. Obstruction-Free Synchronization: Double-Ended Queues as an Example. In Proc. of the 23rd Intl. Conf. on Distributed Computing Systems, Providence, RI, May, 2003.]] Google ScholarDigital Library
- M. Herlihy, V. Luchangco, M. Moir, and W. N. Scherer III. Software Transactional Memory for Dynamic-sized Data Structures. In Proc. of the 22nd ACM Symp. on Principles of Distributed Computing, pages 92--101, Boston, MA, July 2003.]] Google ScholarDigital Library
- M. Herlihy and J. E. Moss. Transactional Memory: Architectural Support for Lock-Free Data Structures. In Proc. of the 20th Intl. Symp. on Computer Architecture, pages 289--300, San Diego, CA, May 1993. Expanded version available as CRL 92/07, Dec. Cambridge Research Laboratory, Dec. 1992.]] Google ScholarDigital Library
- D. Lea. Concurrency JSR-166 Interest Site. http://gee.cs.oswego.edu/dl/concurrency-interest/.]]Google Scholar
- V. J. Marathe, M. L. Scott, and W. N. Scherer III. Adaptive Software Transactional Memory. TR 868, Computer Science Dept., Univ. of Rochester, May 2005.]]Google Scholar
- J. T. Robinson and M. V. Devarakonda. Data Cache Management Using Frequency-Based Replacement. In Proc. of ACM SIGMETRICS, pages 134--142, 1990.]] Google ScholarDigital Library
- W. N. Scherer III and M. L. Scott. Contention Management in Dynamic Software Transactional Memory. In Proc. of the ACM PODC Workshop on Concurrency and Synchronization in Java Programs, St. John's, NL, Canada, July, 2004.]] Google ScholarDigital Library
- N. Shavit and D. Touitou. Software Transactional Memory. In Proc. of the 14th ACM Symp. on Principles of Distributed Computing, pages 204--213, Ottawa, Canada, Aug. 1995.]] Google ScholarDigital Library
- E. Tune, D. Liang, D. M. Tullsen, and B. Calder. Dynamic Prediction of Critical Path Instructions. In Proc. of the 7th Intl. Symp. on High Performance Computer Architecture, pages 185--196, Jan. 2001.]] Google ScholarDigital Library
- C. A. Waldspurger and W. E. Weihl. Lottery Scheduling: Flexible Proportional-Share Resource Management. In Proc. of the 1st Symp. on Operating Systems Design and Implementation, Monterey, CA, Nov. 1994.]] Google ScholarDigital Library
Index Terms
- Advanced contention management for dynamic software transactional memory
Recommendations
A comprehensive strategy for contention management in software transactional memory
PPoPP '09: Proceedings of the 14th ACM SIGPLAN symposium on Principles and practice of parallel programmingIn Software Transactional Memory (STM), contention management refers to the mechanisms used to ensure forward progress--to avoid livelock and starvation, and to promote throughput and fairness. Unfortunately, most past approaches to contention ...
Scheduling support for transactional memory contention management
PPoPP '10Transactional Memory (TM) is considered as one of the most promising paradigms for developing concurrent applications. TM has been shown to scale well on >multiple cores when the data access pattern behaves "well," i.e., when few conflicts are induced. ...
Scheduling support for transactional memory contention management
PPoPP '10: Proceedings of the 15th ACM SIGPLAN Symposium on Principles and Practice of Parallel ProgrammingTransactional Memory (TM) is considered as one of the most promising paradigms for developing concurrent applications. TM has been shown to scale well on >multiple cores when the data access pattern behaves "well," i.e., when few conflicts are induced. ...
Comments