Phasers: a unified deadlock-free construct for collective and point-to-point synchronization

ABSTRACT

Coordination and synchronization of parallel tasks is a major source of complexity in parallel programming. These constructs take many forms in practice including mutual exclusion in accesses to shared resources, termination detection of child tasks, collective barrier synchronization, and point-to-point synchronization. In this paper, we introduce phasers, a new coordination construct that unifies collective and point-to-point synchronizations. We establish two safety properties for phasers: deadlock-freedom and phase-ordering. Performance results obtained from a portable implementation of phasers on three different SMP platforms demonstrate that phasers can deliver superior performance to existing barrier implementations, in addition to the productivity benefits that result from their generality and safety properties.

REFERENCES

• 1: Shivali Agarwal , Rajkishore Barik , Dan Bonachea , Vivek Sarkar , Rudrapatna K. Shyamasundar , Katherine Yelick, Deadlock-free scheduling of X10 computations with bounded resources, Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures, June 09-11, 2007, San Diego, California, USA [doi>10.1145/1248377.1248416]
• 2: Philippe Charles , Christian Grothoff , Vijay Saraswat , Christopher Donawa , Allan Kielstra , Kemal Ebcioglu , Christoph von Praun , Vivek Sarkar, X10: an object-oriented approach to non-uniform cluster computing, Proceedings of the 20th annual ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, October 16-20, 2005, San Diego, CA, USA
• 3: S. Deitz. Parallel programming in chapel. http://www.cct.lsu.edu/ estrabd/LACSI2006/Programming%20Models/deitz.pdf, 2006.
• 4: B. Goetz. Java Concurrency In Practice. Addison-Wesley, 2007.
• 5: Rajiv Gupta, The fuzzy barrier: a mechanism for high speed synchronization of processors, Proceedings of the third international conference on Architectural support for programming languages and operating systems, p.54-63, April 03-06, 1989, Boston, Massachusetts, United States
• 6: Habanero multicore software research project web page. http://habanero.rice.edu, 2008.
• 7: Maurice Herlihy , J. Eliot B. Moss, Transactional memory: architectural support for lock-free data structures, Proceedings of the 20th annual international symposium on Computer architecture, p.289-300, May 16-19, 1993, San Diego, California, United States
• 8: Paul N. Hilfinger , Dan Bonachea , David Gay , Susan Graham , Ben Liblit , Geoff Pike , Katherine Yelick, Titanium Language Reference Manual, University of California at Berkeley, Berkeley, CA, 2001
• 9: The Java Grande Forum benchmark suite. http://www.epcc.ed.ac.uk/javagrande/javag.html.
• 10: OpenMP specifications. http://www.openmp.org/blog/specifications/.
• 11: Robert D. Blumofe , Christopher F. Joerg , Bradley C. Kuszmaul , Charles E. Leiserson , Keith H. Randall , Yuli Zhou, Cilk: an efficient multithreaded runtime system, Proceedings of the fifth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.207-216, July 19-21, 1995, Santa Barbara, California, United States
• 12: V. Sarkar, Synchronization using counting semaphores, Proceedings of the 2nd international conference on Supercomputing, p.627-637, June 1988, St. Malo, France [doi>10.1145/55364.55426]
• 13: J. Shirako, H. Kasahara, and V. Sarkar. Language extensions in support of compiler parallelization. In The 20th International Workshop on Languages and Compilers for Parallel Computing (LCPC'07), 2007.
• 14: L. A. Smith and J. M. Bull. A multithreaded java grande benchmark suite. In Proceedings of the Third Workshop on Java for High Performance Computing, June 2001.
• 15: Release 1.5 of x10 system dated 2007-06-29. http://sourceforge.net/project/showfiles.php?group_id=181722&package_id=210532&release_id=519811, 2007.
• 16: Katherine Yelick , Dan Bonachea , Wei-Yu Chen , Phillip Colella , Kaushik Datta , Jason Duell , Susan L. Graham , Paul Hargrove , Paul Hilfinger , Parry Husbands , Costin Iancu , Amir Kamil , Rajesh Nishtala , Jimmy Su , Michael Welcome , Tong Wen, Productivity and performance using partitioned global address space languages, Proceedings of the 2007 international workshop on Parallel symbolic computation, July 27-28, 2007, London, Ontario, Canada [doi>10.1145/1278177.1278183]

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming

General Terms:
Languages, Performance

Keywords:
barriers, semaphores