Iterative optimization in the polyhedral model: part ii, multidimensional time

ABSTRACT

High-level loop optimizations are necessary to achieve good performance over a wide variety of processors. Their performance impact can be significant because they involve in-depth program transformations that aim to sustain a balanced workload over the computational, storage, and communication resources of the target architecture. Therefore, it is mandatory that the compiler accurately models the target architecture as well as the effects of complex code restructuring.

However, because optimizing compilers (1) use simplistic performance models that abstract away many of the complexities of modern architectures, (2) rely on inaccurate dependence analysis, and (3) lack frameworks to express complex interactions of transformation sequences, they typically uncover only a fraction of the peak performance available on many applications. We propose a complete iterative framework to address these issues. We rely on the polyhedral model to construct and traverse a large and expressive search space. This space encompasses only legal, distinct versions resulting from the restructuring of any static control loop nest. We first propose a feedback-driven iterative heuristic tailored to the search space properties of the polyhedral model. Though, it quickly converges to good solutions for small kernels, larger benchmarks containing higher dimensional spaces are more challenging and our heuristic misses opportunities for significant performance improvement. Thus, we introduce the use of a genetic algorithm with specialized operators that leverage the polyhedral representation of program dependences. We provide experimental evidence that the genetic algorithm effectively traverses huge optimization spaces, achieving good performance improvements on large loop nests.

REFERENCES

• 1: F. Agakov , E. Bonilla , J. Cavazos , B. Franke , G. Fursin , M. F. P. O'Boyle , J. Thomson , M. Toussaint , C. K. I. Williams, Using Machine Learning to Focus Iterative Optimization, Proceedings of the International Symposium on Code Generation and Optimization, p.295-305, March 26-29, 2006 [doi>10.1109/CGO.2006.37]
• 2: Nawaaz Ahmed , Nikolay Mateev , Keshav Pingali, Tiling imperfectly-nested loop nests, Proceedings of the 2000 ACM/IEEE conference on Supercomputing (CDROM), p.31-es, November 04-10, 2000, Dallas, Texas, United States
• 3: Ken Kennedy , John R. Allen, Optimizing compilers for modern architectures: a dependence-based approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2001
• 4: Denis Barthou , Jean-François Collard , Paul Feautrier, Fuzzy array dataflow analysis, Journal of Parallel and Distributed Computing, v.40 n.2, p.210-226, Feb. 1997 [doi>10.1006/jpdc.1996.1261]
• 5: 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]
• 6: C. Bastoul and P. Feautrier. Improving data locality by chunking. In Intl. Conf. on Compiler Construction (ETAPS CC 12), volume 2622, pages 320--335, Warsaw, Poland, Apr. 2003.
• 7: A. Bernstein. Analysis of programs for parallel processing. IEEE Trans. on Electronic Computers, 15(5):757--763, Oct. 1966.
• 8: F. Bodin, T. Kisuki, P. M. W. Knijnenburg, M. F. P. O'Boyle, and E. Rohou. Iterative compilation in a non-linear optimisation space. In W. on Profile and Feedback Directed Compilation, Paris, Oct. 1998.
• 9: 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 Intl. Conf. on Compiler Construction (ETAPS CC 17), Budapest, Hungary, Apr. 2008.
• 10: 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
• 11: Keith D. Cooper , Alexander Grosul , Timothy J. Harvey , Steven Reeves , Devika Subramanian , Linda Torczon , Todd Waterman, ACME: adaptive compilation made efficient, Proceedings of the 2005 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems, June 15-17, 2005, Chicago, Illinois, USA
• 12: Keith D. Cooper , Philip J. Schielke , Devika Subramanian, Optimizing for reduced code space using genetic algorithms, Proceedings of the ACM SIGPLAN 1999 workshop on Languages, compilers, and tools for embedded systems, p.1-9, May 05-05, 1999, Atlanta, Georgia, United States
• 13: Keith D. Cooper , Devika Subramanian , Linda Torczon, Adaptive Optimizing Compilers for the 21st Century, The Journal of Supercomputing, v.23 n.1, p.7-22, August 2002 [doi>10.1023/A:1015729001611]
• 14: Alain Darte , Yves Robert , Frederic Vivien, Scheduling and Automatic Parallelization, Birkhauser Boston, 2000
• 15: P. Feautrier. Parametric integer programming. RAIRO Recherche Opérationnelle, 22(3):243--268, 1988.
• 16: 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]
• 17: 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]
• 18: 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]
• 19: David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 20: M. Haneda , P. M. W. Knijnenburg , H. A. G. Wijshoff, Automatic Selection of Compiler Options Using Non-parametric Inferential Statistics, Proceedings of the 14th International Conference on Parallel Architectures and Compilation Techniques, p.123-132, September 17-21, 2005 [doi>10.1109/PACT.2005.9]
• 21: Wayne Anthony Kelly , William W. Pugh, Optimization within a unified transformation framework, University of Maryland at College Park, College Park, MD, 1996
• 22: W. Kelly , W. Pugh , E. Rosser, Code generation for multiple mappings, Proceedings of the Fifth Symposium on the Frontiers of Massively Parallel Computation (Frontiers'95), p.332, February 06-09, 1995
• 23: T. Kisuki , P. M. W. Knijnenburg , M. F. P. O'Boyle, Combined Selection of Tile Sizes and Unroll Factors Using Iterative Compilation, Proceedings of the 2000 International Conference on Parallel Architectures and Compilation Techniques, p.237, October 15-19, 2000
• 24: Prasad A. Kulkarni , Stephen R. Hines , David B. Whalley , Jason D. Hiser , Jack W. Davidson , Douglas L. Jones, Fast and efficient searches for effective optimization-phase sequences, ACM Transactions on Architecture and Code Optimization (TACO), v.2 n.2, p.165-198, June 2005 [doi>10.1145/1071604.1071607]
• 25: M. Le Fur. Scanning parameterized polyhedron using Fourier-Motzkin elimination. Concurrency -- Practice and Experience, 8(6):445--460, 1996.
• 26: C. Lee. UTDSP benchmark suite, 1998. http://www.eecg.toronto.edu/char‘ corinna/DSP.
• 27: Amy W. Lim , Monica S. Lam, Maximizing parallelism and minimizing synchronization with affine transforms, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.201-214, January 15-17, 1997, Paris, France [doi>10.1145/263699.263719]
• 28: S. Long and G. Fursin. Systematic search within an optimisation space based on unified transformation framework. IJCSE Intl. J. of Computational Science and Engineering, 2006.
• 29: Shun Long , Michael O'Boyle, Adaptive java optimisation using instance-based learning, Proceedings of the 18th annual international conference on Supercomputing, June 26-July 01, 2004, Malo, France [doi>10.1145/1006209.1006243]
• 30: Andy Nisbet, GAPS: A Compiler Framework for Genetic Algorithm (GA) Optimised Parallelisation, Proceedings of the International Conference and Exhibition on High-Performance Computing and Networking, p.987-989, April 21-23, 1998
• 31: M. Palkovič. Enhanced Applicability of Loop Transformations. PhD thesis, T.U. Eindhoven, The Netherlands, Sept. 2007.
• 32: S. Pop, A. Cohen, C. Bastoul, S. Girbal, P. Jouvelot, G.-A. Silber, and N. Vasilache. GRAPHITE: Loop optimizations based on the polyhedral model for GCC. In Proc. of the 4th GCC Developper's Summit, Ottawa, Canada, June 2006.
• 33: L.-N. Pouchet, C. Bastoul, J. Cavazos, and A. Cohen. A note on the performance distribution of affine schedules. 2nd Workshop on Statistical and Machine learning approaches to ARchitectures and compilaTion (SMART'08), Göteborg, Sweden, Jan. 2008.
• 34: Louis-Noel Pouchet , Cedric Bastoul , Albert Cohen , Nicolas Vasilache, Iterative Optimization in the Polyhedral Model: Part I, One-Dimensional Time, Proceedings of the International Symposium on Code Generation and Optimization, p.144-156, March 11-14, 2007 [doi>10.1109/CGO.2007.21]
• 35: William Pugh, The Omega test: a fast and practical integer programming algorithm for dependence analysis, Proceedings of the 1991 ACM/IEEE conference on Supercomputing, p.4-13, November 18-22, 1991, Albuquerque, New Mexico, United States [doi>10.1145/125826.125848]
• 36: Markus Püschel , José M. F. Moura , Bryan Singer , Jianxin Xiong , Jeremy Johnson , David Padua , Manuela Veloso , Robert W. Johnson, Spiral: A Generator for Platform-Adapted Libraries of Signal Processing Algorithms, International Journal of High Performance Computing Applications, v.18 n.1, p.21-45, February 2004 [doi>10.1177/1094342004041291]
• 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: Lakshminarayanan Renganarayanan , DaeGon Kim , Sanjay Rajopadhye , Michelle Mills Strout, Parameterized tiled loops for free, ACM SIGPLAN Notices, v.42 n.6, June 2007
• 39: Alexander Schrijver, Theory of linear and integer programming, John Wiley & Sons, Inc., New York, NY, 1986
• 40: Mark Stephenson , Saman Amarasinghe , Martin Martin , Una-May O'Reilly, Meta optimization: improving compiler heuristics with machine learning, ACM SIGPLAN Notices, v.38 n.5, May 2003
• 41: S. Triantafyllis, M. Vachharajani, and D. I. August. Compiler optimization-space exploration. In J. of Instruction-level Parallelism, volume 7, Jan. 2005.
• 42: N. Vasilache, C. Bastoul, and A. Cohen. Polyhedral code generation in the real world. In Proc. of the Intl. Conf. on Compiler Construction (ETAPS CC 16), volume 3923, pages 185--201, Vienna, Austria, Mar. 2006. Springer-Verlag.
• 43: Nicolas Vasilache , Albert Cohen , Louis-Noel Pouchet, Automatic Correction of Loop Transformations, Proceedings of the 16th International Conference on Parallel Architecture and Compilation Techniques, p.292-304, September 15-19, 2007 [doi>10.1109/PACT.2007.17]
• 44: Frédéric Vivien, On the Optimality of Feautrier's Scheduling Algorithm, Proceedings of the 8th International Euro-Par Conference on Parallel Processing, p.299-308, August 27-30, 2002
• 45: D. K. Wilde. A library for doing polyhedral operations. Technical Report 785, IRISA, Rennes, France, 1993.
• 46: Michael Joseph Wolfe , Carter Shanklin , Leda Ortega, High Performance Compilers for Parallel Computing, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 47: Jingling Xue, Transformations of nested loops with non-convex iteration spaces, Parallel Computing, v.22 n.3, p.339-368, March 1996 [doi>10.1016/0167-8191(95)00069-0]

INDEX TERMS

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

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

General Terms:
Algorithms, Experimentation, Performance

Keywords:
affine scheduling, genetic algorithm, iterative compilation, loop transformation