Chunking parallel loops in the presence of synchronization

ABSTRACT

Modern languages for shared-memory parallelism are moving from a bulk-synchronous Single Program Multiple Data (SPMD) execution model to lightweight Task Parallel execution models for improved productivity. This shift is intended to encourage programmers to express the ideal parallelism in an application at a fine granularity that is natural for the underlying domain, while delegating to the compiler and runtime system the job of extracting coarser-grained useful parallelism for a given target system. A simple and important example of this separation of concerns between ideal and useful parallelism can be found in chunking of parallel loops, where the programmer expresses ideal parallelism by declaring all iterations of a loop to be parallel and the implementation exploits useful parallelism by executing iterations of the loop in sequential chunks.

Though chunking of parallel loops has been used as a standard transformation for several years, it poses some interesting challenges when the parallel loop may directly or indirectly (via procedure calls) perform synchronization operations such as barrier, signal or wait statements. In such cases, a straightforward transformation that attempts to execute a chunk of loops in sequence in a single thread may violate the semantics of the original parallel program. In this paper, we address the problem of chunking parallel loops that may contain synchronization operations. We present a transformation framework that uses a combination of transformations from past work (e.g., loop strip-mining, interchange, distribution, unswitching) to obtain an equivalent set of parallel loops that chunk together statements from multiple iterations while preserving the semantics of the original parallel program. These transformations result in reduced synchronization and scheduling overheads, thereby improving performance and scalability. Our experimental results for 11 benchmark programs on an UltraSPARC II multicore processor showed a geometric mean speedup of 0.52x for the unchunked case and 9.59x for automatic chunking using the techniques described in this paper. This wide gap underscores the importance of using these techniques in future compiler and runtime systems for programming models with lightweight parallelism.

REFERENCES

• 1: E. Allan et al. The Fortress language specification version 0.618. Technical report, Sun Microsystems, April 2005.
• 2: R. Barik et al. Experiences with an SMP implementation for X10 based on the Java concurrency utilities. In Proceedings of the Workshop on Programming Models for Ubiquitous Parallelism, Seattle, Washington, 2006.
• 3: Ganesh Bikshandi , Jose G. Castanos , Sreedhar B. Kodali , V. Krishna Nandivada , Igor Peshansky , Vijay A. Saraswat , Sayantan Sur , Pradeep Varma , Tong Wen, Efficient, portable implementation of asynchronous multi-place programs, Proceedings of the 14th ACM SIGPLAN symposium on Principles and practice of parallel programming, February 14-18, 2009, Raleigh, NC, USA
• 4: 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
• 5: 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
• 6: F. Darema et al. A Single-Program-Multiple-Data Computational model for EPEX/FORTRAN. Parallel Computing, 7(1):11--24, 1988.
• 7: S. Deitz. Parallel programming in chapel. http://www.cct.lsu.edu/ estrabd/LACSI2006/Programming 2006.
• 8: Pedro Diniz , Martin Rinard, Synchronization transformations for parallel computing, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.187-200, January 15-17, 1997, Paris, France [doi>10.1145/263699.263718]
• 9: Andy Georges , Dries Buytaert , Lieven Eeckhout, Statistically rigorous java performance evaluation, ACM SIGPLAN Notices, v.42 n.10, October 2007
• 10: B. Goetz. Java Concurrency In Practice. Addison-Wesley, 2007.
• 11: 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
• 12: Sri Hari Krishna Narayanan , Guilin Chen , Mahmut x. Mahmut Kandemir , Yuan Xie, Temperature-Sensitive Loop Parallelization for Chip Multiprocessors, Proceedings of the 2005 International Conference on Computer Design, p.677-682, October 02-05, 2005 [doi>10.1109/ICCD.2005.105]
• 13: Cray Inc. The Chapel language specification version 0.4. Technical report, Cray Inc., February 2005.
• 14: Ken Kennedy , John R. Allen, Optimizing compilers for modern architectures: a dependence-based approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2001
• 15: Clyde P. Kruskal , Alan Weiss, Allocating Independent Subtasks on Parallel Processors, IEEE Transactions on Software Engineering, v.11 n.10, p.1001-1016, October 1985 [doi>10.1109/TSE.1985.231547]
• 16: Michael Metcalf , John Reid, Fortran 90 explained, Oxford University Press, Inc., New York, NY, 1990
• 17: OpenMP Application Program Interface, version 3.0, May 2008. http://www.openmp.org/mp-documents/spec30.pdf.
• 18: C. D. Polychronopoulos , D. J. Kuck, Guided self-scheduling: A practical scheduling scheme for parallel supercomputers, IEEE Transactions on Computers, v.36 n.12, p.1425-1439, Dec. 1987 [doi>10.1109/TC.1987.5009495]
• 19: 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]
• 20: Jun Shirako , David M. Peixotto , Vivek Sarkar , William N. Scherer, Phasers: a unified deadlock-free construct for collective and point-to-point synchronization, Proceedings of the 22nd annual international conference on Supercomputing, June 07-12, 2008, Island of Kos, Greece [doi>10.1145/1375527.1375568]
• 21: Chau-Wen Tseng, Compiler optimizations for eliminating barrier synchronization, Proceedings of the fifth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.144-155, July 19-21, 1995, Santa Barbara, California, United States
• 22: R. Vallée-Rai et al. Soot-a Java Optimization Framework. In Proceedings of CASCON 1999, pages 125--135, 1999.
• 23: Michael Joseph Wolfe , Carter Shanklin , Leda Ortega, High Performance Compilers for Parallel Computing, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 24: X10 release on SourceForge. http://x10.sf.net.
• 25: 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

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors

General Terms:
Algorithms, Languages, Performance

Keywords:
exceptions, loop chunking, phasers