Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Scheduling-Based Contention Management Techniques for Transactional Memory

  • Chapter
Transactional Memory. Foundations, Algorithms, Tools, and Applications

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 8913))

Abstract

Contention management refers to the mechanisms used by transactional memory (TM) implementations “to ensure forward progress – to avoid livelock and starvation, and to promote throughput and fairness” [1]. Without effective contention management mechanisms, TM implementations are susceptible to performance degradation caused by numerous transaction collisions.

Early work on contention management focused on the narrower problem of conflict resolution. When two transactions collide, one transaction (the winner transaction) is allowed to proceed, while the other (the loser transaction) must wait and/or be aborted. Conflict resolution policies decide which transaction should win and which should lose and for how long the losing transaction should be delayed. However, it was shown that conflict resolution alone is insufficient for guaranteeing reasonable performance for high-contention TM workloads.

The key idea underlying transaction schedulers, introduced a few years ago, is that the execution of conflicting transactions must be serialized in the face of high contention and, more generally, that the level of parallelism between transactional threads should be controlled by the contention manager and dynamically adjusted. Transaction scheduling allows not only to resolve conflicts after they occur, but also to proactively reduce their probability, thus improving performance. This chapter provides a survey of the key approaches and techniques used by transaction schedulers.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

eBook
USD 15.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 15.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Scherer III, W.N., Scott, M.L.: Contention management in dynamic software transactional memory. In: Proceedings of the PODC Workshop on Concurrency and Synchronization in Java Programs (2004)

    Google Scholar 

  2. Herlihy, M., Luchangco, V., Moir, M., Scherer III, W.N.: Software transactional memory for dynamic-sized data structures. In: Proceedings of the Twenty-second Annual Symposium on Principles of Distributed Computing, PODC 2003, pp. 92–101. ACM, New York (2003)

    Chapter  Google Scholar 

  3. Herlihy, M., Luchangco, V., Moir, M.: Obstruction-free synchronization: Double-ended queues as an example. In: Proceedings of the 23rd IEEE International Conference on Distributed Computing Systems (ICDCS 2003), pp. 522–529 (2003)

    Google Scholar 

  4. Scherer III, W.N., Scott, M.L.: Advanced contention management for dynamic software transactional memory. In: Proceedings of the Twenty-fourth Annual ACM Symposium on Principles of Distributed Computing, PODC 2005, pp. 240–248. ACM, New York (2005)

    Google Scholar 

  5. Spear, M.F., Dalessandro, L., Marathe, V.J., Scott, M.L.: A comprehensive strategy for contention management in software transactional memory. In: Proceedings of the 14th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2009, pp. 141–150. ACM, New York (2009)

    Google Scholar 

  6. Dragojević, A., Guerraoui, R., Kapalka, M.: Stretching transactional memory. In: Proceedings of the 2009 ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2009, pp. 155–165. ACM, New York (2009)

    Chapter  Google Scholar 

  7. Felber, P., Riegel, T., Fetzer, C.: Dynamic performance tuning of word-based software transactional memory. In: 13th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPOPP), pp. 237–246 (2008)

    Google Scholar 

  8. Marathe, V.J., Spear, M.F., Heriot, C., Acharya, A., Eisenstat, D., Scherer III, W.N., Scott, M.L.: Lowering the overhead of nonblocking software transactional memory. In: Workshop on Languages, Compilers, and Hardware Support for Transactional Computing (TRANSACT 2006) (2006)

    Google Scholar 

  9. Attiya, H., Epstein, L., Shachnai, H., Tamir, T.: Transactional contention management as a non-clairvoyant scheduling problem. In: Proceedings of the Twenty-fifth Annual ACM Symposium on Principles of Distributed Computing, PODC 2006, pp. 308–315. ACM, New York (2006)

    Chapter  Google Scholar 

  10. Guerraoui, R., Herlihy, M., Pochon, B.: Toward a theory of transactional contention managers. In: Proceedings of the Twenty-fourth Annual ACM Symposium on Principles of Distributed Computing, PODC 2005, pp. 258–264. ACM, New York (2005)

    Google Scholar 

  11. Guerraoui, R., Herlihy, M., Pochon, B.: Towards a theory of transactional contention managers. In: Proceedings of the Twenty-fifth Annual ACM Symposium on Principles of Distributed Computing, PODC 2006, pp. 316–317. ACM, New York (2006)

    Chapter  Google Scholar 

  12. Adl-Tabatabai, A.R., Kozyrakis, C., Saha, B.: Unlocking concurrency. Queue 4, 24–33 (2007)

    Article  Google Scholar 

  13. Harris, T., Larus, J., Rajwar, R.: Transactional Memory, 2nd edn. Morgan and Claypool Publishers (2010)

    Google Scholar 

  14. Bai, T., Shen, X., Zhang, C., Scherer III, W.N., Ding, C., Scott, M.L.: A key-based adaptive transactional memory executor. In: IPDPS, pp. 1–8 (2007)

    Google Scholar 

  15. Guerraoui, R., Herlihy, M.P., Pochon, B.: Polymorphic contention management. In: Fraigniaud, P. (ed.) DISC 2005. LNCS, vol. 3724, pp. 303–323. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  16. Maldonado, W., Marlier, P., Felber, P., Suissa, A., Hendler, D., Fedorova, A., Lawall, J.L., Muller, G.: Scheduling support for transactional memory contention management. In: PPoPP 2010: Proceedings of the 15th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pp. 79–90. ACM, New York (2010)

    Google Scholar 

  17. Yoo, R.M., Lee, H.H.S.: Adaptive transaction scheduling for transactional memory systems. In: SPAA, pp. 169–178 (2008)

    Google Scholar 

  18. Dolev, S., Hendler, D., Suissa, A.: CAR-STM: scheduling-based collision avoidance and resolution for software transactional memory. In: Twenty-Seventh Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 125–134 (2008)

    Google Scholar 

  19. Ansari, M., Luján, M., Kotselidis, C., Jarvis, K., Kirkham, C., Watson, I.: Steal-on-abort: Improving transactional memory performance through dynamic transaction reordering. In: Seznec, A., Emer, J., O’Boyle, M., Martonosi, M., Ungerer, T. (eds.) HiPEAC 2009. LNCS, vol. 5409, pp. 4–18. Springer, Heidelberg (2009)

    Chapter  Google Scholar 

  20. Moore, K.E., Bobba, J., Moravan, M.J., Hill, M.D., Wood, D.A.: Logtm: Log-based transactional memory. In: Proceedings of the 12th International Conference on High Performance Computer Architecture, pp. 254–265 (2006)

    Google Scholar 

  21. Herlihy, M., Luchangco, V., Moir, M.: A flexible framework for implementing software transactional memory. In: Proceedings of the 21st Annual ACM SIGPLAN Conference on Object-oriented Programming Systems, Languages, and Applications, OOPSLA 2006, pp. 253–262. ACM, New York (2006)

    Chapter  Google Scholar 

  22. Atoofian, E.: Improving performance of software transactional memory through contention locality. The Journal of Supercomputing 64, 527–547 (2013)

    Article  Google Scholar 

  23. Attiya, H., Milani, A.: Transactional scheduling for read-dominated workloads. Journal of Parallel and Distributed Computing 72, 1386–1396 (2012)

    Article  MATH  Google Scholar 

  24. Blake, G., Dreslinski, R.G., Mudge, T.N.: Proactive transaction scheduling for contention management. In: MICRO, pp. 156–167 (2009)

    Google Scholar 

  25. Blake, G., Dreslinski, R.G., Mudge, T.N.: Bloom filter guided transaction scheduling. In: HPCA, pp. 75–86 (2011)

    Google Scholar 

  26. Didona, D., Felber, P., Harmanci, D., Romano, P., Schenker, J.: Identifying the optimal level of parallelism in transactional memory applications. In: NETYS, pp. 233–247 (2013)

    Google Scholar 

  27. Heber, T., Hendler, D., Suissa, A.: On the impact of serializing contention management on stm performance. Journal of Parallel and Distributed Computing 72, 739–750 (2012)

    Article  Google Scholar 

  28. Nicácio, D., Baldassin, A., Araujo, G.: Transaction scheduling using dynamic conflict avoidance. International Journal of Parallel Programming 41, 89–110 (2013)

    Article  Google Scholar 

  29. Pereira, M.M., Baldassin, A., Araujo, G., Buzato, L.E.: Transaction scheduling using conflict avoidance and contention intensity. In: HiPC, pp. 236–245 (2013)

    Google Scholar 

  30. di Sanzo, P., Re, F.D., Rughetti, D., Ciciani, B., Quaglia, F.: Regulating concurrency in software transactional memory: An effective model-based approach. In: SASO, pp. 31–40 (2013)

    Google Scholar 

  31. Dragojević, A., Guerraoui, R., Singh, A.V., Singh, V.: Preventing versus curing: Avoiding conflicts in transactional memories. In: Proceeding of the 28th ACM Symposium on Principles of Distributed Computing, pp. 7–16. ACM (2009)

    Google Scholar 

  32. Sainz, D., Attiya, H.: Relstm: A proactive transactional memory scheduler. In: TRANSACT 2013. ACM, New York (2013)

    Google Scholar 

  33. Ansari, M., Kotselidis, C., Jarvis, K., Luján, M., Kirkham, C.C., Watson, I.: Advanced concurrency control for transactional memory using transaction commit rate, pp. 719–728 (2008)

    Google Scholar 

  34. Rughetti, D., di Sanzo, P., Ciciani, B., Quaglia, F.: Analytical/ml mixed approach for concurrency regulation in software transactional memory. In: 2014 14th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing, Chicago, IL, USA, May 26-29, pp. 81–91 (2014)

    Google Scholar 

  35. Cao Minh, C., Chung, J., Kozyrakis, C., Olukotun, K.: STAMP: Stanford transactional applications for multi-processing. In: IISWC 2008: Proceedings of the IEEE International Symposium on Workload Characterization (2008)

    Google Scholar 

  36. Maldonado, W., Marlier, P., Felber, P., Lawall, J.L., Muller, G., Riviere, E.: Deadline-aware scheduling for software transactional memory. In: DSN, pp. 257–268 (2011)

    Google Scholar 

  37. Sharma, G., Busch, C.: Window-based greedy contention management for transactional memory: Theory and practice. Distributed Computing 25, 225–248 (2012)

    Article  MATH  Google Scholar 

  38. Sharma, G., Busch, C.: A competitive analysis for balanced transactional memory workloads. Algorithmica 63, 296–322 (2012)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, Ben-Gurion University of the Negev, Israel

    Danny Hendler

  2. School of Engineering and Applied Sciences, Harvard University, Cambridge, USA

    Adi Suissa-Peleg

Authors
  1. Danny Hendler
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Adi Suissa-Peleg
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. EPFL, 1015, Lausanne, Switzerland

    Rachid Guerraoui

  2. Instituto Superior Técnico, Universidade de Lisboa/INESC-ID, 1000-029, Lisboa, Portugal

    Paolo Romano

Rights and permissions

Reprints and permissions

Copyright information

© 2015 Springer International Publishing Switzerland

About this chapter

Cite this chapter

Hendler, D., Suissa-Peleg, A. (2015). Scheduling-Based Contention Management Techniques for Transactional Memory. In: Guerraoui, R., Romano, P. (eds) Transactional Memory. Foundations, Algorithms, Tools, and Applications. Lecture Notes in Computer Science, vol 8913. Springer, Cham. https://doi.org/10.1007/978-3-319-14720-8_10

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-14720-8_10

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-14719-2

  • Online ISBN: 978-3-319-14720-8

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation