Chao Wang
ABSTRACT
Few transactional memory implementations allow for condition synchronization among transactions. The problems are many, most notably the lack of consensus about a single appropriate linguistic construct, and the lack of mechanisms that are compatible with hardware transactional memory. In this paper, we introduce a broadly useful mechanism for supporting condition synchronization among transactions. Our mechanism supports a number of linguistic constructs for coordinating transactions, and does so without introducing overhead on in-flight hardware transactions. Experiments show that our mechanisms work well, and that the diversity of linguistic constructs allows programmers to chose the technique that is best suited to a particular application.
- A.-R. Adl-Tabatabai, T. Shpeisman, and J. Gottschlich. Draft Specification of Transactional Language Constructs for C++, Feb. 2012. Version 1.1, http://justingottschlich.com/tm-specification-for-c-v-1-1/.Google Scholar
- T. Anderson and M. Dahlin. Operating Systems Principles & Practice. Recursive Books, 2014. Google ScholarDigital Library
- C. Bienia, S. Kumar, J. P. Singh, and K. Li. The PARSEC Benchmark Suite: Characterization and Architectural Implications. In Proceedings of the 17th International Conference on Parallel Architectures and Compilation Techniques, Toronto, ON, Canada, Oct. 2008. Google ScholarDigital Library
- B. D. Carlstrom, A. McDonald, H. Chafi, J. Chung, C. C. Minh, C. Kozyrakis, and K. Olukotun. The Atomos Transactional Programming Language. In Proceedings of the 27th ACM Conference on Programming Language Design and Implementation, June 2006. Google ScholarDigital Library
- P. Charles, C. Donawa, K. Ebcioglu, C. Grothoff, A. Kielstra, C. von Praun, V. Saraswat, and V. Sarkar. X10: An Object-Oriented Approach to Non-Uniform Cluster Computing. In Proceedings of the 20th ACM Conference on Object-Oriented Programming, Systems, Languages, and Applications, San Diego, CA, Oct. 2005. Google ScholarDigital Library
- L. Dalessandro, F. Carouge, S. White, Y. Lev, M. Moir, M. Scott, and M. Spear. Hybrid NOrec: A Case Study in the Effectiveness of Best Effort Hardware Transactional Memory. In Proceedings of the 16th International Conference on Architectural Support for Programming Languages and Operating Systems, Newport Beach, CA, Mar. 2011. Google ScholarDigital Library
- L. Dalessandro, M. Spear, and M. L. Scott. NOrec: Streamlining STM by Abolishing Ownership Records. In Proceedings of the 15th ACM Symposium on Principles and Practice of Parallel Programming, Bangalore, India, Jan. 2010. Google ScholarDigital Library
- D. Dice, O. Shalev, and N. Shavit. Transactional Locking II. In Proceedings of the 20th International Symposium on Distributed Computing, Stockholm, Sweden, Sept. 2006. Google ScholarDigital Library
- A. Dragojevic, Y. Ni, and A.-R. Adl-Tabatabai. Optimizing Transactions for Captured Memory. In Proceedings of the 21st ACM Symposium on Parallelism in Algorithms and Architectures, Calgary, AB, Canada, Aug. 2009. Google ScholarDigital Library
- P. Dudnik and M. M. Swift. Condition Variables and Transactional Memory: Problem or Opportunity? In Proceedings of the 4th ACM SIGPLAN Workshop on Transactional Computing, Raleigh, NC, Feb. 2009.Google Scholar
- P. Felber, C. Fetzer, and T. Riegel. Dynamic Performance Tuning of Word-Based Software Transactional Memory. In Proceedings of the 13th ACM Symposium on Principles and Practice of Parallel Programming, Salt Lake City, UT, Feb. 2008. Google ScholarDigital Library
- Free Software Foundation. Transactional Memory in GCC, 2012. http://gcc.gnu.org/wiki/TransactionalMemory.Google Scholar
- R. Guerraoui and M. Kapalka. On the Correctness of Transactional Memory. In Proceedings of the 13th ACM Symposium on Principles and Practice of Parallel Programming, Salt Lake City, UT, Feb. 2008. Google ScholarDigital Library
- T. Harris and K. Fraser. Language Support for Lightweight Transactions. In Proceedings of the 18th ACM Conference on Object-Oriented Programming, Systems, Languages, and Applications, Oct. 2003. Google ScholarDigital Library
- T. Harris, S. Marlow, S. Peyton Jones, and M. Herlihy. Composable Memory Transactions. In Proceedings of the 10th ACM Symposium on Principles and Practice of Parallel Programming, Chicago, IL, June 2005. Google ScholarDigital Library
- M. P. Herlihy and J. E. B. Moss. Transactional Memory: Architectural Support for Lock-Free Data Structures. In Proceedings of the 20th International Symposium on Computer Architecture, San Diego, CA, May 1993. Google ScholarDigital Library
- M. Lesani and J. Palsberg. Communicating Memory Transactions. In Proceedings of the 16th ACM Symposium on Principles and Practice of Parallel Programming, San Antonio, TX, Feb. 2011. Google ScholarDigital Library
- Y. Liu, S. Diestelhorst, and M. Spear. Delegation and Nesting in Best Effort Hardware Transactional Memory. In Proceedings of the 24th ACM Symposium on Parallelism in Algorithms and Architectures, Pittsburgh, PA, June 2012. Google ScholarDigital Library
- V. Luchangco and V. Marathe. Revisiting Condition Variables and Transactions. In Proceedings of the 6th ACM SIGPLAN Workshop on Transactional Computing, San Jose, CA, June 2011.Google Scholar
- V. Luchangco and V. Marathe. Transaction Communicators: Enabling Cooperation Among Concurrent Transactions. In Proceedings of the 16th ACM Symposium on Principles and Practice of Parallel Programming, San Antonio, TX, Feb. 2011. Google ScholarDigital Library
- A. Matveev and N. Shavit. Reduced Hardware NORec: A Safe and Scalable Hybrid Transactional Memory. In Proceedings of the 19th International Conference on Architectural Support for Programming Languages and Operating Systems, Istanbul, Turkey, Mar. 2015. Google ScholarDigital Library
- Y. Ni, A. Welc, A.-R. Adl-Tabatabai, M. Bach, S. Berkowits, J. Cownie, R. Geva, S. Kozhukow, R. Narayanaswamy, J. Olivier, S. Preis, B. Saha, A. Tal, and X. Tian. Design and Implementation of Transactional Constructs for C/C++. In Proceedings of the 23rd ACM Conference on Object Oriented Programming, Systems, Languages, and Applications, Nashville, TN, USA, Oct. 2008. Google ScholarDigital Library
- M. Olszewski, J. Cutler, and J. G. Steffan. JudoSTM: A Dynamic Binary-Rewriting Approach to Software Transactional Memory. In Proceedings of the 16th International Conference on Parallel Architecture and Compilation Techniques, Brasov, Romania, Sept. 2007. Google ScholarDigital Library
- R. Rajwar and J. R. Goodman. Speculative Lock Elision: Enabling Highly Concurrent Multithreaded Execution. In Proceedings of the 34th IEEE/ACM International Symposium on Microarchitecture, Austin, TX, Dec. 2001. Google ScholarDigital Library
- T. Riegel, C. Fetzer, and P. Felber. Time-Based Transactional Memory with Scalable Time Bases. In Proceedings of the 19th ACM Symposium on Parallelism in Algorithms and Architectures, San Diego, California, June 2007. Google ScholarDigital Library
- T. Riegel, C. Fetzer, and P. Felber. Automatic Data Partitioning in Software Transactional Memories. In Proceedings of the 20th ACM Symposium on Parallelism in Algorithms and Architectures, Munich, Germany, June 2008. Google ScholarDigital Library
- T. Riegel, P. Marlier, M. Nowack, P. Felber, and C. Fetzer. Optimizing Hybrid Transactional Memory: The Importance of Nonspeculative Operations. In Proceedings of the 23rd ACM Symposium on Parallelism in Algorithms and Architectures, June 2011. Google ScholarDigital Library
- M. Ringenburg and D. Grossman. AtomCaml: First-Class Atomicity via Rollback. In Proceedings of the 10th ACM International Conference on Functional Programming, Tallinn, Estonia, Sept. 2005. Google ScholarDigital Library
- W. Ruan, T. Vyas, Y. Liu, and M. Spear. Transactionalizing Legacy Code: An Experience Report Using GCC and Memcached. In Proceedings of the 19th International Conference on Architectural Support for Programming Languages and Operating Systems, Salt Lake City, UT, Mar. 2014. Google ScholarDigital Library
- Y. Smaragdakis, A. Kay, R. Behrends, and M. Young. Transactions with Isolation and Cooperation. In Proceedings of the 22nd ACM Conference on Object Oriented Programming, Systems, Languages, and Applications, Montreal, Quebec, Canada, Oct. 2007. Google ScholarDigital Library
- M. Spear, L. Dalessandro, V. J. Marathe, and M. L. Scott. A Comprehensive Strategy for Contention Management in Software Transactional Memory. In Proceedings of the 14th ACM Symposium on Principles and Practice of Parallel Programming, Raleigh, NC, Feb. 2009. Google ScholarDigital Library
- C. Wang, Y. Liu, and M. Spear. Transaction-Friendly Condition Variables. In Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures, Prague, Czech Republic, June 2014. Google ScholarDigital Library
- H. Wettstein. The Problem of Nested Monitor Calls Revisited. SIGOPS Operating Systems Review, 12(1):19--23, Jan. 1978. Google ScholarDigital Library
- R. Yates and M. Scott. A Hybrid TM for Haskell. In Proceedings of the 9th ACM SIGPLAN Workshop on Transactional Computing, Salt Lake City, UT, Mar. 2014.Google Scholar
- R. Yoo, C. Hughes, K. Lai, and R. Rajwar. Performance Evaluation of Intel Transactional Synchronization Extensions for High Performance Computing. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, Denver, CO, Nov. 2013. Google ScholarDigital Library
- R. Yoo, Y. Ni, A. Welc, B. Saha, A.-R. Adl-Tabatabai, and H.-H. Lee. Kicking the Tires of Software Transactional Memory: Why the Going Gets Tough. In Proceedings of the 20th ACM Symposium on Parallelism in Algorithms and Architectures, Munich, Germany, June 2008. Google ScholarDigital Library
- T. Zhou and M. Spear. The Mimir Approach to Transactional Output. In Proceedings of the 11th ACM SIGPLAN Workshop on Transactional Computing, Barcelona, Spain, Mar. 2016.Google Scholar
- C. Zilles and L. Baugh. Extending Hardware Transactional Memory to Support Non-Busy Waiting and Non-Transactional Actions. In Proceedings of the 1st ACM SIGPLAN Workshop on Languages, Compilers, and Hardware Support for Transactional Computing, Ottawa, ON, Canada, June 2006.Google Scholar
Index Terms
- Practical condition synchronization for transactional memory
Recommendations
Transaction-friendly condition variables
SPAA '14: Proceedings of the 26th ACM symposium on Parallelism in algorithms and architecturesRecent microprocessors and compilers have added support for transactional memory (TM). While state-of-the-art TM systems allow the replacement of lock-based critical sections with scalable, optimistic transactions, there is not yet an acceptable ...
Towards transactional memory semantics for C++
SPAA '09: Proceedings of the twenty-first annual symposium on Parallelism in algorithms and architecturesTransactional memory (TM) eliminates many problems associated with lock-based synchronization. Over recent years, much progress has been made in software and hardware implementation techniques for TM. However, before transactional memory can be ...
A comprehensive strategy for contention management in software transactional memory
PPoPP '09In 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 ...
Comments