On the decidability of phase ordering problem in optimizing compilation

ABSTRACT

We are interested in the computing frontier around an essential question about compiler construction: having a program P and a set M of non parametric compiler optimization modules (called also phases), is it possible to find a sequence s of these phases such that the performance (execution time for instance) of the final generated program P′ is "optimal" ? We prove in this article that this problem is undecidable in two general schemes of optimizing compilation: iterative compilation and library optimization/generation. Fortunately, we give some simplified cases when this problem be-comes decidable, and we provide some algorithms (not necessary efficient) that can answer our main question. Another essential question that we are interested in is parame-ters space exploration in optimizing compilation (tuning optimizing compilation parameters). In this case, we assume a fixed sequence of optimization, but each optimization phase is allowed to have a parameter. We try to figure out how to compute the best parameter values for all program transformations when the compilation sequence is given. We also prove that this general problem is undecidable and we provide some simplified decidable instances.

REFERENCES

• 1: A. Cohen and S. Girbal and O. Temam. A Polyhedral Approach to Ease the Composition of Program Transformations. In Proceedings of Euro-Par'04, Aug. 2004.
• 2: Bas Aarts , Michel Barreteau , François Bodin , Peter Brinkhaus , Zbigniew Chamski , Henri-Pierre Charles , Christine Eisenbeis , John R. Gurd , Jan Hoggerbrugge , Ping Hu , William Jalby , Peter M. W. Knijnenburg , Michael F. P. O'Boyle , Erven Rohou , Rizos Sakellariou , Henk Schepers , André Seznec , Elena Stöhr , Marco Verhoeven , Harry A. G. Wijshoff, OCEANS: Optimizing Compilers for Embedded Applications, Proceedings of the Third International Euro-Par Conference on Parallel Processing, p.1351-1356, August 26-29, 1997
• 3: Cliff Click , Keith D. Cooper, Combining analyses, combining optimizations, ACM Transactions on Programming Languages and Systems (TOPLAS), v.17 n.2, p.181-196, March 1995 [doi>10.1145/201059.201061]
• 4: David Callahan , John Cocke , Ken Kennedy, Estimating interlock and improving balance for pipelined architectures, Journal of Parallel and Distributed Computing, v.5 n.4, p.334-358, August 1988 [doi>10.1016/0743-7315(88)90002-0]
• 5: 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 ]
• 6: L. Eeckhout, H. Vandierendonck, and K. D. Bosschere. Quantifying the Impact of Input Data Sets on Program Behavior and its Applications. Journal of Instruction-Level Parallelism, 5, 2003. Electronic journal : www.jilp.org.
• 7: S. M. Freudenberger and J. C. Ruttenberg. Phase Ordering of Register Allocation and Instruction Scheduling. In Code Generation - Concepts, Tools, Techniques. Proceedings of the International Workshop on Code Generation, pages 146--172, London, 1992. Springer-Verlag.
• 8: Matteo Frigo, A fast Fourier transform compiler, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.169-180, May 01-04, 1999, Atlanta, Georgia, United States
• 9: John E. Hopcroft , Jeffrey D. Ullman, Introduction To Automata Theory, Languages, And Computation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 10: J. P. Jones. Universal Diophantine Equation. Journal of Symbolic Logic, 47(3):403--410, 1982.
• 11: K. Kennedy, N. McIntosh, and K. McKinley. Static Performance Estimation in a Parallelizing Compiler. Technical Report CRPC-TR92204, Center for Research on Parallel Computation, Rice University, May 1992.
• 12: L. Almagor , Keith D. Cooper , Alexander Grosul , Timothy J. Harvey , Steven W. Reeves , Devika Subramanian , Linda Torczon , Todd Waterman, Finding effective compilation sequences, Proceedings of the 2004 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems, June 11-13, 2004, Washington, DC, USA
• 13: Michael E. Wolf , Dror E. Maydan , Ding-Kai Chen, Combining loop transformations considering caches and scheduling, International Journal of Parallel Programming, v.26 n.4, p.479-503, Aug. 1998 [doi>10.1023/A:1018754616274 ]
• 14: M. Pschel and J. M. F. Moura and J. Johnson and D. Padua and M. Veloso and B. Singer and J. Xiong and F. Franchetti and A. Gacic and Y. Voronenko and K. Chen and R. W. Johnson and N. Rizzolo. SPIRAL: Code Generation for DSP Transforms. Proceedings of the IEEE special issue on Program Generation, Optimization and Adaptation, (2):232--275, 2005.
• 15: Min Zhao , Bruce R. Childers , Mary Lou Soffa, A Model-Based Framework: An Approach for Profit-Driven Optimization, Proceedings of the international symposium on Code generation and optimization, p.317-327, March 20-23, 2005 [doi>10.1109/CGO.2005.2]
• 16: W. Mangione-Smith, T.-P. Shih, S. Abraham, and E. Davidson. Approaching a Machine-Application Bound in Delivered Performance on Scientifique Code. In Proceedings of the IEEE, volume 81, pages 1166--1178, Aug. 1993.
• 17: Yuri Matiyasevich, Elimination of quantifiers from arithmetical formulas defining recursively enumerable sets, Mathematics and Computers in Simulation, v.67 n.1-2, p.125-133, 3 September 2004 [doi>10.1016/j.matcom.2004.05.013]
• 18: R. Jain. The Art of Computer Systems Performance Analysis: Techniques for Experimental Design, Measurement, Simulation, and Modeling. John Wiley and Sons, Inc., New York, 1991.
• 19: R. Whaley and A. Petitet and J. Dongarra. Automated Empirical Optimizations of Software and the ATLAS Project. Parallel Computing, 27(1-2):3--25, 2001. ISSN 0167--8191.
• 20: Uwe Schwiegelshohn , Franco Gasperoni , Kemal Ebcio>ilde;lu, On optimal parallelization of arbitrary loops, Journal of Parallel and Distributed Computing, v.11 n.2, p.130-134, Feb. 1991 [doi>10.1016/0743-7315(91)90118-S]
• 21: T. Alexander. Performance Prediction for Loop Restructuring Optimization. Master thesis, University of Carnegie Mellon. Physics/Computer Science Department, July 1993.
• 22: Todd L. Veldhuizen , Andrew Lumsdaine, Guaranteed Optimization: Proving Nullspace Properties of Compilers, Proceedings of the 9th International Symposium on Static Analysis, p.263-277, September 17-20, 2002
• 23: Kevin B. Theobald , Guang R. Gao , Laurie J. Hendren, On the limits of program parallelism and its smoothability, Proceedings of the 25th annual international symposium on Microarchitecture, p.10-19, December 01-04, 1992, Portland, Oregon, United States
• 24: S. Triantafyllis, M. Vachharajani, and D. I. August. Compiler Optimization-Space Exploration. Journal of Instruction-Level Parallelism, 7, Jan. 2005. Electronic journal: www.jilp.org.
• 25: Ko-Yang Wang, Precise compile-time performance prediction for superscalar-based computers, ACM SIGPLAN Notices, v.29 n.6, p.73-84, June 1994
• 26: Deborah L. Whitfield , Mary Lou Soffa, An approach for exploring code improving transformations, ACM Transactions on Programming Languages and Systems (TOPLAS), v.19 n.6, p.1053-1084, Nov. 1997 [doi>10.1145/267959.267960]

INDEX TERMS

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

General Terms:
Algorithms, Performance, Theory

Keywords:
input data I, iterative compilation, library generation, optimizing compilation, parameters space exploration, phase ordering