Document Open Access Logo

ActiveMonitor: Asynchronous Monitor Framework for Scalability and Multi-Object Synchronization

Authors Wei-Lun Hung, Himanshu Chauhan, Vijay K. Garg

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2015.29.pdf
  • Filesize: 0.6 MB
  • 17 pages

Document Identifiers

Author Details

Wei-Lun Hung
Himanshu Chauhan
Vijay K. Garg

Cite As Get BibTex

Wei-Lun Hung, Himanshu Chauhan, and Vijay K. Garg. ActiveMonitor: Asynchronous Monitor Framework for Scalability and Multi-Object Synchronization. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 29:1-29:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.OPODIS.2015.29

Abstract

Monitor objects are used extensively for thread-safety and synchronization in shared memory parallel programs. They provide ease of use, and enable straightforward correctness analysis. However, they inhibit parallelism by enforcing serial executions of critical sections, and thus the performance of parallel programs with monitors scales poorly with number of processes. Their current design and implementation is also ill-suited for thread synchronization across multiple thread-safe objects. We present ActiveMonitor - a framework that allows multi-object synchronization without global locks, and improves parallelism by exploiting asynchronous execution of critical sections. We evaluate the performance of Java based implementation of ActiveMonitor on micro-benchmarks involving light and heavy critical sections, as well as on single-source-shortest-path problem in directed graphs. Our results show that on most of these problems, ActiveMonitor based programs outperform programs implemented using Java's reentrant-lock and condition constructs.

Subject Classification

Keywords
  • concurrent/parallel programming
  • monitors
  • concurrency

Metrics

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

References

  1. ActiveMonitor: Technical Report Version. URL: http://pdsl.ece.utexas.edu/TechReports/2016/opodis_tr.pdf.
  2. David A Bader and Kamesh Madduri. Gtgraph: A synthetic graph generator suite. Atlanta, GA, February, 2006. Google Scholar
  3. Peter A. Buhr, Michel Fortier, and Michael H Coffin. Monitor classification. ACM Computing Surveys, 27(1):63-107, March 1995. Google Scholar
  4. Irina Calciu, Dave Dice, Tim Harris, Maurice Herlihy, Alex Kogan, Virendra J. Marathe, and Mark Moir. Message passing or shared memory: Evaluating the delegation abstraction for multicores. In OPODIS, pages 83-97, 2013. Google Scholar
  5. Deepayan Chakrabarti, Yiping Zhan, and Christos Faloutsos. R-mat: A recursive model for graph mining. In SDM, volume 4, pages 442-446. SIAM, 2004. Google Scholar
  6. Philippe Charles, Christian Grothoff, Vijay Saraswat, Christopher Donawa, Allan Kielstra, Kemal Ebcioglu, Christoph Von Praun, and Vivek Sarkar. X10: an object-oriented approach to non-uniform cluster computing. Acm Sigplan Notices, 40(10):519-538, 2005. Google Scholar
  7. E. W. Dijkstra. A note on two problems in connexion with graphs. Numer. Math., 1(1):269-271, December 1959. URL: http://dx.doi.org/10.1007/BF01386390.
  8. 9th DIMACS Implementation Challenge - Shortest Paths. URL: http://www.dis.uniroma1.it/challenge9/download.shtml.
  9. P. Dudnik and M. Swift. Condition variables and transactional memory: Problem or opportunity? In The 4th ACM SIGPLAN Workshop on Transactional Computing, 2009. Google Scholar
  10. Panagiota Fatourou and Nikolaos D Kallimanis. Revisiting the combining synchronization technique. ACM SIGPLAN Notices, 47(8):257-266, 2012. Google Scholar
  11. Faith Fich, Danny Hendler, and Nir Shavit. On the inherent weakness of conditional synchronization primitives. In Proceedings of the Twenty-third Annual ACM Symposium on Principles of Distributed Computing, PODC'04, pages 80-87, 2004. Google Scholar
  12. Robert H. Halstead. Multilisp: A language for concurrent symbolic computation. ACM Trans. Program. Lang. Syst., 7(4):501-538, October 1985. Google Scholar
  13. Timothy L Harris. A Pragmatic Implementation of Non-blocking Linked-Lists. In Proceedings of the 15th International Conference on Distributed Computing, pages 300-314, 2001. Google Scholar
  14. Steve Heller, Maurice Herlihy, Victor Luchangco, Mark Moir, WilliamN III Scherer, and Nir Shavit. A Lazy Concurrent List-Based Set Algorithm. In Principles of Distributed Systems, pages 3-16. Springer Berlin Heidelberg, 2006. Google Scholar
  15. Danny Hendler, Itai Incze, Nir Shavit, and Moran Tzafrir. Flat Combining and the Synchronization-parallelism Tradeoff. In SPAA, pages 355-364, 2010. Google Scholar
  16. Danny Hendler, Nir Shavit, and Lena Yerushalmi. A scalable lock-free stack algorithm. In Proceedings of the Sixteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, SPAA'04, pages 206-215, 2004. Google Scholar
  17. Maurice Herlihy and Zhiyu Liu. Well-structured futures and cache locality. In ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP'14, Orlando, FL, USA, February 15-19, 2014, pages 155-166, 2014. 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, 1993. Google Scholar
  19. Maurice Herlihy and Nir Shavit. The Art of Multiprocessor Programming. Morgan Kaufmann Publishers Inc., 2008. Google Scholar
  20. Maurice P. Herlihy. Impossibility and universality results for wait-free synchronization. In Proceedings of the Seventh Annual ACM Symposium on Principles of Distributed Computing, PODC'88, pages 276-290, 1988. Google Scholar
  21. Maurice P Herlihy and Jeannette M Wing. Linearizability: A Correctness Condition for Concurrent Objects. ACM Transactions on Programming Languages and Systems, 12(3):463-492, 1990. Google Scholar
  22. C A R Hoare. Monitors: An Operating System Structuring Concept. Communications of the ACM, 17(10):549-557, 1974. Google Scholar
  23. C A R Hoare. Communicating sequential processes. Communications of the ACM, 21(8):666-677, 1978. Google Scholar
  24. Wei-Lun Hung and Vijay K. Garg. AutoSynch: An Automatic-signal Monitor Based on Predicate Tagging. In PLDI, pages 253-262, 2013. Google Scholar
  25. Joseph Izraelevitz and Michael L. Scott. Brief announcement: a generic construction for nonblocking dual containers. In ACM Symposium on Principles of Distributed Computing, PODC'14, pages 53-55, 2014. Google Scholar
  26. David Klaftenegger, Konstantinos Sagonas, and Kjell Winblad. Delegation locking libraries for improved performance of multithreaded programs. In Euro-Par, 2014. Google Scholar
  27. Alex Kogan and Maurice Herlihy. The future (s) of shared data structures. In Proceedings of the 2014 ACM symposium on Principles of distributed computing, pages 30-39. ACM, 2014. Google Scholar
  28. Alex Kogan and Erez Petrank. Wait-free queues with multiple enqueuers and dequeuers. In Proceedings of the 16th ACM Symposium on Principles and Practice of Parallel Programming, PPoPP'11, pages 223-234, 2011. Google Scholar
  29. Alex Kogan and Erez Petrank. A methodology for creating fast wait-free data structures. In Proceedings of the 17th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP'12, pages 141-150, 2012. Google Scholar
  30. Doug Lea. The Java.Util.Concurrent Synchronizer Framework. Sci. Comput. Program., 58(3):293-309, 2005. Google Scholar
  31. Jean-Pierre Lozi et al. Remote core locking: Migrating critical-section execution to improve the performance of multithreaded applications. In USENIX Annual Technical Conference, pages 65-76, 2012. Google Scholar
  32. V. Luchangco and V. J. Marathe. Revisiting condition variables and transactions. In The 6th ACM SIGPLAN Workshop on Transactional Computing, 2011. Google Scholar
  33. Maged M Michael. High Performance Dynamic Lock-free Hash Tables and List-based Sets. In Proceedings of the Fourteenth Annual ACM Symposium on Parallel Algorithms and Architectures, pages 73-82, 2002. Google Scholar
  34. Aravind Natarajan and Neeraj Mittal. Fast concurrent lock-free binary search trees. In Proceedings of the 19th ACM SIGPLAN symposium on Principles and practice of parallel programming, pages 317-328. ACM, 2014. Google Scholar
  35. Yoshihiro Oyama, Kenjiro Taura, and Akinori Yonezawa. Executing parallel programs with synchronization bottlenecks efficiently. In Proceedings of International Workshop on Parallel and Distributed Computing for Symbolic and Irregular Applications (PDSIA'99). World Scientific, 1999. Google Scholar
  36. Darko Petrovic, Thomas Ropars, and André Schiper. Leveraging hardware message passing for efficient thread synchronization. In ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP'14, Orlando, FL, USA, February 15-19, 2014, pages 143-154, 2014. Google Scholar
  37. Nir Shavit and Dan Touitou. Software transactional memory. In Proceedings of the Fourteenth Annual ACM Symposium on Principles of Distributed Computing, PODC'95, pages 204-213, 1995. Google Scholar
  38. A. Skyrme and N. Rodriguez. From locks to transactional memory: Lessons learned from porting a real-world application. In The 8th ACM SIGPLAN Workshop on Transactional Computing, 2013. Google Scholar
  39. Shahar Timnat, Anastasia Braginsky, Alex Kogan, and Erez Petrank. Wait-free linked-lists. In Proceedings of the 17th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP'12, pages 309-310, 2012. Google Scholar
  40. TMWare - TMJava. URL: http://tmware.org/.
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