Turno Tarde (14 a 17 horas)

Philippe Clauss, Université Louis Pasteur, Francia (Curso en inglés)

http://icps.u-strasbg.fr/~clauss

Philippe Clauss is Professor in Computer Science at Université Louis Pasteur in Strasbourg, France. His main research interests are concerned with program analysis and optimization for advanced compilers and program behavior modeling. He took part in the development of the polyhedral library PolyLib in particular for its parametric extensions. This library is dedicated to nested loops analysis and optimization by a polyhedral representation of iterations. His current activities are concerned with non-linear program analysis and dynamic analysis and optimization. His list of publications can be found at http://icps.u-strasbg.fr/~clauss.

Objetivos del Curso:

This tutorial shows some recent issues for accurate analysis and optimization of programs. Efficient approaches are presented to optimize program performance or to reduce ressource consumption of programs running on embedded systems. The key is to model the behavior of the software/hardware couple in order to extract useful information and generate guided optimizations. The tutorial is organized in two main parts. The first one is concerned with static approaches, where analysis and transformation are done from the knowledge of the source code and maybe of the target machine architecture. The second one is concerned with dynamic approches, where execution profiles are used to model the program behavior either during an off-line phase or a learning on-line phase. Then, dynamic optimization processes are implemented optimizing the program behavior while it is running.

Programa:

DAY 1 (3 hours)

• I - INTRODUCTION
  • Challenges - performance - technology limits - memory bottleneck - critical systems - embedded systems
• I.1. The memory hierarchy
• I.2. Modeling & optimizing the software/hardware behavior

• II - STATIC APPROACH
• II.1. Program modeling and analysis in the Polytope Model
  • The nested loops program model
  • Geometrical representation of nested loops by polyhedra in the integer lattice
  • Data dependencies analysis
  • Geometrical transformations yield program transformations : unimodular and affine transformations, validity and semantic preservation
  • Parameterized polytopes for parameterized programs and architectures : parametric vertices, Ehrhart polynomials

• II - STATIC APPROACH (continued)
• II.2. Program transformations and optimizations in the Polytope Model
  • Parallel schedules
  • Processor allocation : linear and non-linear allocation
  • Temporal data locality optimization
  • Spatial data locality optimization

• II - STATIC APPROACH (continued)
• II.3. Non-linear analysis
  • Symbolic Bernstein Expansion
• III - DYNAMIC APPROACH
  • Modeling & optimizing behavior from execution profiling & source code.
• III.1. Hardware mecanisms
  • Hardware Dynamic optimization : branch prediction - data prediction (Markov model)
• III.2. Hybrid hardware/software mecanisms
  • Using hardware counters for bottlenecks detections.

• III - DYNAMIC APPROACH (continued)
• III.3. Software mecanisms
  • Off line trace analysis : the periodic-linear model of behavior capture
  • On line trace analysis : n-depth Markov model, learning & optimization phases

Requisitos:

• Only the knowledge of the basic elements of computer architecture, programming and linear algebra is requested.

Bibliografía

• John L. Hennessy and David A. Patterson. Computer Architecture: A Quantitative Approach. Morgan Kaufmann Publishers, third edition, 2002.
• A. Aho, R. Sethi, J. Ullman, Compilers: Principles, Techniques, and Tools, Addison-Wesley, 1986.
• P. Feautrier, The Data Parallel Programming Model, chapter Automatic Parallelization in the Polytope Model, pages = 79-100, Springer-Verlag, LNCS 1132, 1996.
• Michael Wolfe, High Performance Compilers For Parallel Computing, Addison-Wesley, 1996.
• Uptal Banerjee, Loop Transformations for Restructuring Compilers, The Foundations, Kluwer Academic Publishers, 1993.
• Ph. Clauss and I. Tchoupaeva, A Symbolic Approach to Bernstein Expansion for Program Analysis and Optimization, 13th International Conference on Compiler Construction, CC 2004, LNCS, vol. 2985, Springer, pages 120-133, Ed. Evelyn Duesterwald, Barcelona, Spain, April 2004.
• Vincent Loechner, Benoît Meister and Philippe Clauss, Precise data locality optimization of nested loops, in The Journal of Supercomputing, volume 21(1), pages 37-76, Kluwer Academic Pub., January 2002.
• Ph. Clauss, Counting Solutions to Linear and Nonlinear Constraints throughEhrhart polynomials: Applications to Analyse and Transform Scientific Programs, Proceedings of the 10th International Conference on Supercomputing, ICS'96, Philadelphia, May 1996.

Material del curso

• http://polytope.u-strasbg.fr/eci2005/
• Transparencias y examen

Calificaciones