Compiler-assisted dynamic scheduling for effective parallelization of loop nests on multicore processors

ABSTRACT

Recent advances in polyhedral compilation technology have made it feasible to automatically transform affine sequential loop nests for tiled parallel execution on multi-core processors. However, for multi-statement input programs with statements of different dimensionalities, such as Cholesky or LU decomposition, the parallel tiled code generated by existing automatic parallelization approaches may suffer from significant load imbalance, resulting in poor scalability on multi-core systems. In this paper, we develop a completely automatic parallelization approach for transforming input affine sequential codes into efficient parallel codes that can be executed on a multi-core system in a load-balanced manner. In our approach, we employ a compile-time technique that enables dynamic extraction of inter-tile dependences at run-time, and dynamic scheduling of the parallel tiles on the processor cores for improved scalable execution. Our approach obviates the need for programmer intervention and re-writing of existing algorithms for efficient parallel execution on multi-cores. We demonstrate the usefulness of our approach through comparisons using linear algebra computations: LU and Cholesky decomposition.

REFERENCES

• 1: Thomas L. Adam , K. M. Chandy , J. R. Dickson, A comparison of list schedules for parallel processing systems, Communications of the ACM, v.17 n.12, p.685-690, Dec 1974 [doi>10.1145/361604.361619]
• 2: Randy Allen , Ken Kennedy, Automatic translation of FORTRAN programs to vector form, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.4, p.491-542, Oct. 1987 [doi>10.1145/29873.29875]
• 3: Corinne Ancourt , François Irigoin, Scanning polyhedra with DO loops, Proceedings of the third ACM SIGPLAN symposium on Principles and practice of parallel programming, p.39-50, April 21-24, 1991, Williamsburg, Virginia, United States
• 4: Cedric Bastoul, Code Generation in the Polyhedral Model Is Easier Than You Think, Proceedings of the 13th International Conference on Parallel Architectures and Compilation Techniques, p.7-16, September 29-October 03, 2004 [doi>10.1109/PACT.2004.11]
• 5: C. Bastoul, A. Cohen, S. Girbal, S. Sharma, and O. Temam. Putting polyhedral loop transformations to work. In Workshop on Languages and Compilers for Parallel Computing (LCPC'03), pages 23--30, 2003.
• 6: U. Bondhugula, M. Baskaran, S. Krishnamoorthy, J. Ramanujam, A. Rountev, and P. Sadayappan. Affine transformations for communication minimal parallelization and locality optimization of arbitrarily nested loop sequences. Technical Report OSU-CISRC-5/07-TR43, Ohio State University, May 2007.
• 7: U. Bondhugula, M. Baskaran, S. Krishnamoorthy, J. Ramanujam, A. Rountev, and P. Sadayappan. Automatic transformations for communication-minimized parallelization and locality optimization in the polyhedral model. In International Conference on Compiler Construction (ETAPS CC), Apr. 2008.
• 8: Uday Bondhugula , Albert Hartono , J. Ramanujam , P. Sadayappan, A practical automatic polyhedral parallelizer and locality optimizer, Proceedings of the 2008 ACM SIGPLAN conference on Programming language design and implementation, June 07-13, 2008, Tucson, AZ, USA
• 9: U. Bondhugula, J. Ramanujam, and P. Sadayappan. Pluto: A practical and fully automatic polyhedral parallelizer and locality optimizer. Technical Report OSU-CISRC-10/07-TR70, The Ohio State University, Oct. 2007.
• 10: Pierre Boulet , Alain Darte , Georges-André Silber , Frédéric Vivien, Loop parallelization algorithms: from parallelism extraction to code generation, Parallel Computing, v.24 n.3-4, p.421-444, May, 1998 [doi>10.1016/S0167-8191(98)00020-9]
• 11: A. Buttari, J. Dongarra, P. Husbands, J. Kurzak, and K. Yelick. Multithreading for synchronization tolerance in matrix factorization. In Proceedings of the SciDAC 2007 Conference. Journal of Physics: Conference Series, 2007.
• 12: A. Buttari, J. Langou, J. Kurzak, and J. Dongarra. A class of parallel tiled linear algebra algorithms for multicore architectures. Technical Report UT-CS-07-600, Innovative Computing Laboratory, University of Tennessee Knoxville, September 2007. Submitted to Parallel Computing. LAPACK Working Note 191.
• 13: Ding-Kai Chen , Josep Torrellas , Pen-Chung Yew, An efficient algorithm for the run-time parallelization of DOACROSS loops, Proceedings of the 1994 conference on Supercomputing, p.518-527, December 1994, Washington, D.C., United States
• 14: Marcelo Cintra , Diego R. Llanos, Toward efficient and robust software speculative parallelization on multiprocessors, Proceedings of the ninth ACM SIGPLAN symposium on Principles and practice of parallel programming, June 11-13, 2003, San Diego, California, USA
• 15: CLooG: The Chunky Loop Generator. http://www.cloog.org.
• 16: A. Darte, G.-A. Silber, and F. Vivien. Combining retiming and scheduling techniques for loop parallelization and loop tiling. Parallel Processing Letters, 7(4):379--392, 1997.
• 17: Alain Darte , Frédéric Vivien, Optimal fine and medium grain parallelism detection in polyhedral reduced dependence graphs, International Journal of Parallel Programming, v.25 n.6, p.447-496, Dec. 1997 [doi>10.1023/A:1025168022993]
• 18: J. Dongarra. Four important concepts that will effect math software. In 9th International Workshop on State-of-the-Art in Scientific and Parallel Computing (PARA'08), 2008.
• 19: P. Feautrier. Dataflow analysis of array and scalar references. IJPP, 20(1):23--53, 1991.
• 20: Paul Feautrier, Some efficient solutions to the affine scheduling problem: I. One-dimensional time, International Journal of Parallel Programming, v.21 n.5, p.313-348, Oct. 1992 [doi>10.1007/BF01407835]
• 21: Paul Feautrier, Some efficient solutions to the affine scheduling problem: I. One-dimensional time, International Journal of Parallel Programming, v.21 n.5, p.313-348, Oct. 1992 [doi>10.1007/BF01407835]
• 22: Paul Feautrier, Automatic Parallelization in the Polytope Model, The Data Parallel Programming Model: Foundations, HPF Realization, and Scientific Applications, p.79-103, January 1996
• 23: A. Gerasoulis , T. Yang, On the Granularity and Clustering of Directed Acyclic Task Graphs, IEEE Transactions on Parallel and Distributed Systems, v.4 n.6, p.686-701, June 1993 [doi>10.1109/71.242154]
• 24: Sylvain Girbal , Nicolas Vasilache , Cédric Bastoul , Albert Cohen , David Parello , Marc Sigler , Olivier Temam, Semi-automatic composition of loop transformations for deep parallelism and memory hierarchies, International Journal of Parallel Programming, v.34 n.3, p.261-317, June 2006 [doi>10.1007/s10766-006-0012-3]
• 25: M. Griebl. Automatic Parallelization of Loop Programs for Distributed Memory Architectures. FMI, University of Passau, 2004. Habilitation Thesis.
• 26: Hironori Kasahara , Hiroki Honda , Seinosuke Narita, Parallel processing of near fine grain tasks using static scheduling on OSCAR (Optimally Scheduled Advanced Multiprocessor), Proceedings of the 1990 ACM/IEEE conference on Supercomputing, p.856-864, November 12-16, 1990, New York, New York
• 27: Yu-Kwong Kwok , Ishfaq Ahmad, Static scheduling algorithms for allocating directed task graphs to multiprocessors, ACM Computing Surveys (CSUR), v.31 n.4, p.406-471, Dec. 1999 [doi>10.1145/344588.344618]
• 28: Shun-Tak Leung , John Zahorjan, Improving the performance of runtime parallelization, ACM SIGPLAN Notices, v.28 n.7, p.83-91, July 1993
• 29: Amy Wingmui Lim , Monica S. Lam, Improving parallelism and data locality with affine partitioning, 2001
• 30: Amy W. Lim , Shih-Wei Liao , Monica S. Lam, Blocking and array contraction across arbitrarily nested loops using affine partitioning, Proceedings of the eighth ACM SIGPLAN symposium on Principles and practices of parallel programming, p.103-112, June 2001, Snowbird, Utah, United States
• 31: Amy W. Lim , Gerald I. Cheong , Monica S. Lam, An affine partitioning algorithm to maximize parallelism and minimize communication, Proceedings of the 13th international conference on Supercomputing, p.228-237, June 20-25, 1999, Rhodes, Greece [doi>10.1145/305138.305197]
• 32: Amy W. Lim , Monica S. Lam, Maximizing parallelism and minimizing synchronization with affine partitions, Parallel Computing, v.24 n.3-4, p.445-475, May, 1998 [doi>10.1016/S0167-8191(98)00021-0]
• 33: Parallel linear algebra for scalable multi-core architectures (PLASMA) project. http://icl.cs.utk.edu/plasma.
• 34: PLUTO: A polyhedral automatic parallelizer and locality optimizer for multicores. http://pluto-compiler.sourceforge.net.
• 35: R. Ponnusamy , J. Saltz , A. Choudhary, Runtime compilation techniques for data partitioning and communication schedule reuse, Proceedings of the 1993 ACM/IEEE conference on Supercomputing, p.361-370, December 1993, Portland, Oregon, United States [doi>10.1145/169627.169752]
• 36: William Pugh, A practical algorithm for exact array dependence analysis, Communications of the ACM, v.35 n.8, p.102-114, Aug. 1992 [doi>10.1145/135226.135233]
• 37: Fabien Quilleré , Sanjay Rajopadhye , Doran Wilde, Generation of Efficient Nested Loops from Polyhedra, International Journal of Parallel Programming, v.28 n.5, p.469-498, Oct. 2000 [doi>10.1023/A:1007554627716]
• 38: Carlos García Quiñones , Carlos Madriles , Jesús Sánchez , Pedro Marcuello , Antonio González , Dean M. Tullsen, Mitosis compiler: an infrastructure for speculative threading based on pre-computation slices, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, June 12-15, 2005, Chicago, IL, USA
• 39: Lawrence Rauchwerger , David Padua, The LRPD test: speculative run-time parallelization of loops with privatization and reduction parallelization, ACM SIGPLAN Notices, v.30 n.6, p.218-232, June 1995
• 40: P. Rundberg and P. S. Om. Low-cost thread-level data dependence speculation on multiprocessors. In In Fourth Workshop on Multithreaded Execution, Architecture and Compilation, pages 1--9, 2000.
• 41: Silvius Rus , Maikel Pennings , Lawrence Rauchwerger, Sensitivity analysis for automatic parallelization on multi-cores, Proceedings of the 21st annual international conference on Supercomputing, June 17-21, 2007, Seattle, Washington [doi>10.1145/1274971.1275008]
• 42: Joel Saltz , Kathleen Crowley , Ravi Mirchandaney , Harry Berryman, Run-time scheduling and execution of loops on message passing machines, Journal of Parallel and Distributed Computing, v.8 n.4, p.303-312, Apr. 1990 [doi>10.1016/0743-7315(90)90129-D]
• 43: Joel H. Salz , Ravi Mirchandaney , Kay Crowley, Run-Time Parallelization and Scheduling of Loops, IEEE Transactions on Computers, v.40 n.5, p.603-612, May 1991 [doi>10.1109/12.88484]
• 44: Vivek Sarkar, Partitioning and Scheduling Parallel Programs for Multiprocessors, MIT Press, Cambridge, MA, 1989
• 45: Vivek Sarkar , John Hennessy, Compile-time partitioning and scheduling of parallel programs, Proceedings of the 1986 SIGPLAN symposium on Compiler construction, p.17-26, June 25-27, 1986, Palo Alto, California, United States
• 46: N. Vasilache, C. Bastoul, and A. Cohen. Polyhedral code generation in the real world. In International Conference on Compiler Construction (ETAPS CC'06), pages 185--201, Mar. 2006.
• 47: Nicolas Vasilache , Cedric Bastoul , Albert Cohen , Sylvain Girbal, Violated dependence analysis, Proceedings of the 20th annual international conference on Supercomputing, June 28-July 01, 2006, Cairns, Queensland, Australia [doi>10.1145/1183401.1183448]
• 48: M. E. Wolf , M. S. Lam, A Loop Transformation Theory and an Algorithm to Maximize Parallelism, IEEE Transactions on Parallel and Distributed Systems, v.2 n.4, p.452-471, October 1991 [doi>10.1109/71.97902]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Code generation

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization; Compilers; Run-time environments

General Terms:
Algorithms, Performance

Keywords:
compile-time optimization, dynamic scheduling, run-time optimization