Abstract
We wish to extend the effectiveness of loop-restructuring compilers by improving the robustness of loop transformations and easing their composition in long sequences. We propose a formal and practical framework for program transformation. Our framework is well suited for iterative optimization techniques searching not only for the appropriate parameters of a given transformation, but for the program transformations themselves, and especially for compositions of program transformations. This framework is based on a unified polyhedral representation of loops and statements, enabling the application of generalized control and data transformations without reference to a syntactic program representation. The key to our framework is to clearly separate the impact of each program transformation on three independent components: the iteration domain, the iteration schedule and the memory access functions. The composition of generalized transformations builds on normalization rules specific to each component of the representation. Our techniques have been implemented on top of Open64/ORC.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Barreteau, M., Bodin, F., Chamski, Z., Charles, H.-P., Eisenbeis, C., Gurd, J.R., Hoogerbrugge, J., Hu, P., Jalby, W., Kisuki, T., Knijnenburg, P.M.W., van der Mark, P., Nisbet, A., O’Boyle, M.F.P., Rohou, E., Seznec, A., Stöhr, E., Treffers, M., Wijshoff, H.A.G.: Oceans - optimising compilers for embedded applications. In: Amestoy, P.R., Berger, P., Daydé, M., Duff, I.S., Frayssé, V., Giraud, L., Ruiz, D. (eds.) Euro-Par 1999. LNCS, vol. 1685, pp. 1171–1775. Springer, Heidelberg (1999)
Barthou, D., Collard, J.-F., Feautrier, P.: Fuzzy array dataflow analysis. J. of Parallel and Distributed Computing 40, 210–226 (1997)
Bastoul, C.: Efficient code generation for automatic parallelization and optimization. In: ISPDC’2 IEEE International Symposium on Parallel and Distributed Computing, Ljubjana, Slovenia (October 2003)
Bastoul, C., Cohen, A., Girbal, S., Sharma, S., Temam, O.: Putting polyhedral loop transformations to work. In: Rauchwerger, L. (ed.) LCPC 2003. LNCS, vol. 2958, Springer, Heidelberg (2004)
Blume, W., Eigenmann, R., Faigin, K., Grout, J., Hoeflinger, J., Padua, D., Petersen, P., Pottenger, W., Rauchwerger, L., Tu, P., Weatherford, S.: Parallel programming with Polaris. IEEE Computer 29(12), 78–82 (1996)
Cohen, A., Girbal, S., Temam, O.: Facilitating the exploration of compositions of program transformations. Research report 5114, INRIA Futurs, France (February 2004)
Cooper, K.D., Hall, M.W., Hood, R.T., Kennedy, K., McKinley, K.S., Mellor- Crummey, J.M., Torczon, L., Warren, S.K.: The ParaScope parallel programming environment. Proceedings of the IEEE 81(2), 244–263 (1993)
Cooper, K.D., Subramanian, D., Torczon, L.: Adaptive optimizing compilers for the 21st century. J. of Supercomputing (2002)
Darte, A., Robert, Y., Vivien, F.: Scheduling and Automatic Parallelization. Birkhaüser, Boston (2000)
Feautrier, P.: Some efficient solutions to the affine scheduling problem, part II, multidimensional time. Int. J. of Parallel Programming 21(6), 389–420 (1992); See also Part I, one dimensional time 21(5), 315–348
Fursin, G., O’Boyle, M., Knijnenburg, P.: Evaluating iterative compilation. In: Pugh, B., Tseng, C.-W. (eds.) LCPC 2002. LNCS, vol. 2481, pp. 362–376. Springer, Heidelberg (2005)
Guillou, A.-C., Quilleré, F., Quinton, P., Rajopadhye, S., Risset, T.: Hardware design methodology with the Alpha language. In: FDL 2001, Lyon, France (September 2001)
Hall, M., et al.: Maximizing multiprocessor performance with the SUIF compiler. IEEE Computer 29(12), 84–89 (1996)
Irigoin, F., Jouvelot, P., Triolet, R.: Semantical interprocedural parallelization: An overview of the pips project. In: ACM Int. Conf. on Supercomputing (ICS’2), Cologne, Germany (June 1991)
Kelly, W.: Optimization within a unified transformation framework. Technical Report CS-TR-3725, University of Maryland (1996)
Kelly, W., Pugh, W., Rosser, E.: Code generation for multiple mappings. In: Frontiers 1995 Symp. on the frontiers of massively parallel computation, McLean (1995)
Kodukula, I., Pingali, K.: Transformations for imperfectly nested loops. In: Supercomputing (SC 1996) (January 1996)
Lim, A.W., Lam, M.S.: Communication-free parallelization via affine transformations. In: 24th ACM Symp. on Principles of Programming Languages, Paris, France, January 1997, pp. 201–214 (1997)
Lim, A.W., Liao, S.-W., Lam, M.S.: Blocking and array contraction across arbitrarily nested loops using affine partitioning. In: ACM Symp. on Principles and Practice of Parallel Programming (PPoPP 2001), pp. 102–112 (2001)
Loechner, V., Wilde, D.: Parameterized polyhedra and their vertices. Int. J. of Parallel Programming 25(6) (December 1997), http://icps.u-strasbg.fr/PolyLib
O’Boyle, M.: MARS: a distributed memory approach to shared memory compilation. In: Proc. Language, Compilers and Runtime Systems for Scalable Computing, Pittsburgh, May 1998, Springer, Heidelberg (1998)
Parello, D., Temam, O., Verdun, J.-M.: On increasing architecture awareness in program optimizations to bridge the gap between peak and sustained processor performance? matrix-multiply revisited. In: SuperComputing 2002, Baltimore, Maryland (November 2002)
Quilleré, F., Rajopadhye, S., Wilde, D.: Generation of efficient nested loops from polyhedra. Intl. J. of Parallel Programming 28(5), 469–498 (2000)
Schreiber, R., Aditya, S., Rau, B., Kathail, V., Mahlke, S., Abraham, S., Snider, G.: High-level synthesis of nonprogrammable hardware accelerators. Technical report, Hewlett-Packard (May 2000)
Wolf, M.E.: Improving Locality and Parallelism in Nested Loops. PhD thesis, Stanford University (August 1992); Published as CSL-TR-92-538
Wolfe, M.J.: High Performance Compilers for Parallel Computing. Addison-Wesley, Reading (1996)
Wonnacott, D., Pugh, W.: Nonlinear array dependence analysis. In: Proc. Third Workshop on Languages, Compilers and Run-Time Systems for Scalable Computers, Troy, New York (1995)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cohen, A., Girbal, S., Temam, O. (2004). A Polyhedral Approach to Ease the Composition of Program Transformations. In: Danelutto, M., Vanneschi, M., Laforenza, D. (eds) Euro-Par 2004 Parallel Processing. Euro-Par 2004. Lecture Notes in Computer Science, vol 3149. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-27866-5_38
Download citation
DOI: https://doi.org/10.1007/978-3-540-27866-5_38
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-22924-7
Online ISBN: 978-3-540-27866-5
eBook Packages: Springer Book Archive