Document Open Access Logo

HaTS: Hardware-Assisted Transaction Scheduler

Authors Zhanhao Chen, Ahmed Hassan, Masoomeh Javidi Kishi, Jacob Nelson, Roberto Palmieri

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2019.10.pdf
  • Filesize: 0.78 MB
  • 16 pages

Document Identifiers

Author Details

Zhanhao Chen
  • Palo Alto Networks Inc, Santa Clara, CA, USA
Ahmed Hassan
  • Lehigh University, Bethlehem, PA, USA
Masoomeh Javidi Kishi
  • Lehigh University, Bethlehem, PA, USA
Jacob Nelson
  • Lehigh University, Bethlehem, PA, USA
Roberto Palmieri
  • Lehigh University, Bethlehem, PA, USA

Funding

This material is based upon work supported by the Air Force Office of Scientific Research under award number FA9550-17-1-0367 and by the National Science Foundation under Grant No. CNS-1814974.

Cite As Get BibTex

Zhanhao Chen, Ahmed Hassan, Masoomeh Javidi Kishi, Jacob Nelson, and Roberto Palmieri. HaTS: Hardware-Assisted Transaction Scheduler. In 23rd International Conference on Principles of Distributed Systems (OPODIS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 153, pp. 10:1-10:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.OPODIS.2019.10

Abstract

In this paper we present HaTS, a Hardware-assisted Transaction Scheduler. HaTS improves performance of concurrent applications by classifying the executions of their atomic blocks (or in-memory transactions) into scheduling queues, according to their so called conflict indicators. The goal is to group those transactions that are conflicting while letting non-conflicting transactions proceed in parallel. Two core innovations characterize HaTS. First, HaTS does not assume the availability of precise information associated with incoming transactions in order to proceed with the classification. It relaxes this assumption by exploiting the inherent conflict resolution provided by Hardware Transactional Memory (HTM). Second, HaTS dynamically adjusts the number of the scheduling queues in order to capture the actual application contention level. Performance results using the STAMP benchmark suite show up to 2x improvement over state-of-the-art HTM-based scheduling techniques.

Subject Classification

ACM Subject Classification
  • Software and its engineering → Scheduling
Keywords
  • Transactions
  • Scheduling
  • Hardware Transactional Memory

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Yehuda Afek, Amir Levy, and Adam Morrison. Software-improved Hardware Lock Elision. In Proceedings of the 2014 ACM Symposium on Principles of Distributed Computing, PODC '14, pages 212-221, New York, NY, USA, 2014. ACM. URL: https://doi.org/10.1145/2611462.2611482.
  2. Dan Alistarh, Syed Kamran Haider, Raphael Kübler, and Giorgi Nadiradze. The Transactional Conflict Problem. In Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures, SPAA '18, pages 383-392, New York, NY, USA, 2018. ACM. URL: https://doi.org/10.1145/3210377.3210406.
  3. Dan Alistarh, Justin Kopinsky, Petr Kuznetsov, Srivatsan Ravi, and Nir Shavit. Inherent limitations of hybrid transactional memory. Distributed Computing, 31(3):167-185, June 2018. URL: https://doi.org/10.1007/s00446-017-0305-3.
  4. Mohammad Ansari, Behram Khan, Mikel Luján, Christos Kotselidis, Chris C. Kirkham, and Ian Watson. Improving Performance by Reducing Aborts in Hardware Transactional Memory. In High Performance Embedded Architectures and Compilers, 5th International Conference, HiPEAC 2010, Pisa, Italy, January 25-27, 2010. Proceedings, pages 35-49, 2010. Google Scholar
  5. Mohammad Ansari, Mikel Luján, Christos Kotselidis, Kim Jarvis, Chris C. Kirkham, and Ian Watson. Steal-on-Abort: Improving Transactional Memory Performance through Dynamic Transaction Reordering. In High Performance Embedded Architectures and Compilers, Fourth International Conference, HiPEAC 2009, Paphos, Cyprus, January 25-28, 2009. Proceedings, pages 4-18, 2009. Google Scholar
  6. Jayaram Bobba, Kevin E. Moore, Haris Volos, Luke Yen, Mark D. Hill, Michael M. Swift, and David A. Wood. Performance pathologies in hardware transactional memory. In 34th International Symposium on Computer Architecture (ISCA 2007), June 9-13, 2007, San Diego, California, USA, pages 81-91, 2007. Google Scholar
  7. Harold W. Cain, Maged M. Michael, Brad Frey, Cathy May, Derek Williams, and Hung Le. Robust Architectural Support for Transactional Memory in the Power Architecture. In ISCA, pages 225-236, 2013. Google Scholar
  8. Irina Calciu, Justin Gottschlich, Tatiana Shpeisman, Gilles Pokam, and Maurice Herlihy. Invyswell: A Hybrid Transactional Memory for Haswell’s Restricted Transactional Memory. In Proceedings of the 23rd International Conference on Parallel Architectures and Compilation Techniques, PACT '14, 2014. Google Scholar
  9. Calin Cascaval, Colin Blundell, Maged Michael, Harold W. Cain, Peng Wu, Stefanie Chiras, and Siddhartha Chatterjee. Software Transactional Memory: Why Is It Only a Research Toy? Queue, 6(5):40:46-40:58, September 2008. URL: https://doi.org/10.1145/1454456.1454466.
  10. Dave Dice, Yossi Lev, Mark Moir, and Daniel Nussbaum. Early Experience with a Commercial Hardware Transactional Memory Implementation. In Proceedings of the 14th International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS XIV, pages 157-168, New York, NY, USA, 2009. ACM. URL: https://doi.org/10.1145/1508244.1508263.
  11. Dave Dice, Ori Shalev, and Nir Shavit. Transactional Locking II. In Shlomi Dolev, editor, Distributed Computing, volume 4167 of Lecture Notes in Computer Science, pages 194-208. Springer Berlin Heidelberg, 2006. URL: https://doi.org/10.1007/11864219_14.
  12. Nuno Diegues and Paolo Romano. Self-Tuning Intel Transactional Synchronization Extensions. In 11th International Conference on Autonomic Computing, ICAC '14. USENIX Association, 2014. Google Scholar
  13. Nuno Diegues, Paolo Romano, and Stoyan Garbatov. Seer: Probabilistic Scheduling for Hardware Transactional Memory. In Proceedings of the 27th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA '15, pages 224-233, New York, NY, USA, 2015. ACM. URL: https://doi.org/10.1145/2755573.2755578.
  14. Shlomi Dolev, Danny Hendler, and Adi Suissa. CAR-STM: scheduling-based collision avoidance and resolution for software transactional memory. In Proceedings of the Twenty-Seventh Annual ACM Symposium on Principles of Distributed Computing, PODC 2008, Toronto, Canada, August 18-21, 2008, pages 125-134, 2008. Google Scholar
  15. Aleksandar Dragojevic, Rachid Guerraoui, Anmol V. Singh, and Vasu Singh. Preventing versus curing: avoiding conflicts in transactional memories. In Proceedings of the 28th Annual ACM Symposium on Principles of Distributed Computing, PODC 2009, Calgary, Alberta, Canada, August 10-12, 2009, pages 7-16, 2009. Google Scholar
  16. Ricardo Filipe, Shady Issa, Paolo Romano, and João Barreto. Stretching the Capacity of Hardware Transactional Memory in IBM POWER Architectures. In Proceedings of the 24th Symposium on Principles and Practice of Parallel Programming, PPoPP '19, pages 107-119, New York, NY, USA, 2019. ACM. URL: https://doi.org/10.1145/3293883.3295714.
  17. Ahmed Hassan, Roberto Palmieri, and Binoy Ravindran. Transactional Interference-Less Balanced Tree. In Distributed Computing - 29th International Symposium, DISC 2015, Tokyo, Japan, October 7-9, 2015, Proceedings, pages 325-340, 2015. Google Scholar
  18. Maurice Herlihy and J. Eliot B. Moss. Transactional Memory: Architectural Support for Lock-free Data Structures. In Proceedings of the 20th Annual International Symposium on Computer Architecture, ISCA '93, pages 289-300, New York, NY, USA, 1993. ACM. URL: https://doi.org/10.1145/165123.165164.
  19. Maurice Herlihy and Nir Shavit. The Art of Multiprocessor Programming. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2008. Google Scholar
  20. Junwhan Kim, Roberto Palmieri, and Binoy Ravindran. Enhancing Concurrency in Distributed Transactional Memory through Commutativity. In Felix Wolf, Bernd Mohr, and Dieter an Mey, editors, Euro-Par 2013 Parallel Processing, pages 150-161, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg. Google Scholar
  21. Alexander Matveev and Nir Shavit. Reduced Hardware Transactions: A New Approach to Hybrid Transactional Memory. In Proceedings of the Twenty-fifth Annual ACM Symposium on Parallelism in Algorithms and Architectures, SPAA '13, pages 11-22, New York, NY, USA, 2013. ACM. URL: https://doi.org/10.1145/2486159.2486188.
  22. Alexander Matveev and Nir Shavit. Reduced Hardware NOrec: A Safe and Scalable Hybrid Transactional Memory. In Proceedings of the Twentieth International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS '15, pages 59-71, New York, NY, USA, 2015. ACM. URL: https://doi.org/10.1145/2694344.2694393.
  23. Chi Cao Minh, Jaewoong Chung, C. Kozyrakis, and K. Olukotun. STAMP: Stanford transactional applications for multi-processing. In Workload Characterization, 2008. IISWC 2008. IEEE International Symposium on, pages 35-46, September 2008. URL: https://doi.org/10.1109/IISWC.2008.4636089.
  24. M. Mohamedin, R. Palmieri, A. Hassan, and B. Ravindran. Managing Resource Limitation of Best-Effort HTM. IEEE Transactions on Parallel and Distributed Systems, 28(8):2299-2313, August 2017. URL: https://doi.org/10.1109/TPDS.2017.2668415.
  25. Mohamed Mohamedin, Roberto Palmieri, and Binoy Ravindran. Brief Announcement: On Scheduling Best-Effort HTM Transactions. In Proceedings of the 27th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA '15, pages 74-76, New York, NY, USA, 2015. ACM. URL: https://doi.org/10.1145/2755573.2755612.
  26. Ravi Rajwar and James R. Goodman. Speculative lock elision: enabling highly concurrent multithreaded execution. In Proceedings of the 34th Annual International Symposium on Microarchitecture, Austin, Texas, USA, December 1-5, 2001, pages 294-305, 2001. Google Scholar
  27. James Reinders. Transactional synchronization in haswell. Intel Software Network. URL: http://software.intel.com/en-us/blogs/2012/02/07/transactional-synchronization-in-haswell/, 2012.
  28. Hugo Rito and João P. Cachopo. ProPS: A Progressively Pessimistic Scheduler for Software Transactional Memory. In Euro-Par 2014 Parallel Processing - 20th International Conference, Porto, Portugal, August 25-29, 2014. Proceedings, pages 150-161, 2014. Google Scholar
  29. Christopher J. Rossbach, Owen S. Hofmann, Donald E. Porter, Hany E. Ramadan, Bhandari Aditya, and Emmett Witchel. TxLinux: using and managing hardware transactional memory in an operating system. In Proceedings of the 21st ACM Symposium on Operating Systems Principles 2007, SOSP 2007, Stevenson, Washington, USA, October 14-17, 2007, pages 87-102, 2007. Google Scholar
  30. Lingxiang Xiang and Michael L. Scott. Conflict Reduction in Hardware Transactions Using Advisory Locks. In Proceedings of the 27th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA '15, pages 234-243, New York, NY, USA, 2015. ACM. URL: https://doi.org/10.1145/2755573.2755577.
  31. Richard M. Yoo and Hsien-Hsin S. Lee. Adaptive transaction scheduling for transactional memory systems. In SPAA 2008: Proceedings of the 20th Annual ACM Symposium on Parallelism in Algorithms and Architectures, Munich, Germany, June 14-16, 2008, pages 169-178, 2008. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact