EduXchange.EU

Program Optimization

IN2053
Computer Science and ICT, Data, AI

About this course

The lecture starts with basic dataflow analyses like availability of expressions or liveness of variables together with the optimizing transformations enabled by these analyses. Motivated by the examples, we develop the theoretical background on complete lattices and monotone functions necessary for program analysis methods. Subsequently, we discuss more sophisticated analyses such as constant propagation. By discussing interval analysis, we present general methods for the case where ordinary fixpoint computation will not terminate. Further topics are:

  • interprocedural analysis;
  • pointer analysis;
  • fixpoint algorithms. We also consider hardware dependent optimizations such as:
  • register allocation;
  • instruction selection;
  • instruction scheduling and also optimizations to improve the cache behavior.

Learning outcomes

Participants know the often occurring conflict between good structure and readability of a program as well as the highest possible efficiency of the execution of the program which is likewise desired. They know the techniques to increase the efficiency of the program execution through optimizing transformations of a compiler. They are able to apply these to small example programs and are able to develop new analyses and optimizations on their own.

Examination

The assessment is by means of a written exam of 120 minutes. Some assignments offer small problems from the area of lattice theory by which students may demonstrate how well they are acquainted with basic concepts of program analysis and in how far they are able to apply these concepts in an original way. Other assignments evaluate how well students are able to apply the learnt analyses and transformations to small example programs. Further assignments ask to develop new analyses and optimizations. The successful completion of homework asignments may contribute to the grade as a bonus. The exact details for this are timely announced at the beginning of the lecture.

Course requirements

Bachelor Informatics, basic knowledge in programming languages or compilers

Activities

By means of a presentation, either by slides or whiteboard, the lecture presents fundamental techniques for the analysis and optimization of programs and illustrates these by means of small examples. Accompanying assignments for individual study deepen the understanding of the concepts explained in the lecture, train students to apply the learnt analyses and optimizations to example programs and develop the skill to realize analyses and optimizations on their own.

Additional information

  • Credits
    ECTS 8
  • Contact hours per week
    6
  • Instructors
    Systemadministrator, Anastasia Isychev, Yannick Stade, Ralf Vogler, Helmut Seidl, Peter Lammich
  • Mode of instruction
    Hybrid
If anything remains unclear, please check the FAQ of TUM (Germany).

Offering(s)

  • Start date

    16 October 2024

    • Ends
      6 February 2025
    • Term *
      Winter 2024/2025
    • Instruction language
    • Register between
      24 May - 29 Jul 2024
    Only 8 days to enrol
    Apply now
These offerings are valid for students of DTU (Denmark)