Hide menu

TDDC86 Compiler Optimizations and Code Generation

Project


Project task

The project task consists either of an experimental self-study of selected optimizations in a modern compiler framework or of a critical review of a recent conference paper or journal article in compiler technology.
  • Compiler framework projects:
    You do this project on your own computer at home.
    The target platform can be your own computer or one that is simulated on your computer by a cycle-accurate simulator. Ask the course leader if you are not sure about which platform to choose.

    This kind of project is intended to be done in a group of two students. If you do not find a project partner, it is OK to do it alone.

    Preparations: You choose a compiler framework you have access to, e.g. free or open-source compiler systems such as gcc, LLVM, ORC. Choose (at least) two compiler optimizations or transformations, such as software pipelining, loop unrolling, loop blocking, automatic vectorization, predication, etc. Read the documentation of your compiler to find out what switches need to be set to enable or disable the considered optimizations.
    Read about important architectural parameters of your target platform, such as processor instruction set, memory structure, cache sizes, or memory page size.
    Choose at least three test programs, such as simple matrix-matrix multiplication, FFT, FIR filter, or sorting. For test programs with input-dependent time behavior, such as most sorting algorithms, use a fixed input (e.g., fixed random number generator settings). You can also use program kernels from publically accessible benchmark suites. It is also OK to share test programs with other project groups. In any case, make sure that the test programs are correct before you begin with the experimental evaluation.

    Experiments: Compile the test programs with and without each of the two optimizations, giving at least four versions each. Dump and analyze the assembly code to find out what the compiler has (or has not) done. Try to predict from the assembly code (e.g., by counting instructions) the quantitative effect of the transformations on execution time.
    If the compiler is unable to do a certain transformation because of weak program analysis (check why!), it is ok to perform the corresponding optimization by hand in the source code to enforce it.
    Measure the different versions of your test programs for different problem sizes (use different orders of magnitude, such as 100, 1000, 10000). If execution times vary for the same version and problem size, measure multiple runs and take the average time. If your timer resolution is too coarse, replicate the program execution multiple times to get meaningful figures.
    Compare the results (across problem sizes and across versions, possibly also with different parameters such as unroll or block factors where applicable), and try to interpret your findings.
    Draw conclusions, e.g., try to derive simple rules for when and how to apply or not apply your considered optimizations.
    If you find similar studies described in the literature, include a reference in your presentation and summary.

  • Paper study projects:

    Select a recent (i.e., not older than 10 years) research paper in compiler technology that is related to our course contents and that seems significant to you. You can find some starting points for searching here. If you cannot find a suitable paper on your own, ask the course leader to assign one to you.
    Read and analyze the paper carefully, and check also related work (following the references and citation information e.g. in the ACM DL about later papers that refer to yours.

    This kind of project is intended to be done alone. It can be adapted to match a group of 2 students. In this case, two related papers/articles are to be chosen; presentations will be separate, but you can be opponent of each other. The relation between these papers (differences, common issues) should then be elaborated on, too.

Examination moments

The project result is to be presented both by an oral presentation with opposition of another project, and by a written summary paper. The course therefore concludes with a simulated compiler workshop (announced as seminar sessions (SE) in the web schedule) where the project results are presented for all participants. Presence during the seminar sessions is mandatory.

Schedule and Deadlines

  • Preparation phase:
    For compiler framework projects:
    Choose the compiler framework(s), at least two compiler optimizations, test programs, and a target platform for experiments, as described above. Find another project group for opposition.
    Send your choice with short motivation by email to C. Kessler by 25 sep 2009.
    Also, inform C. Kessler about who will be your opponent, and whom you will be opponent for.

    For paper study projects:
    Choose a recent research paper, as described above, in compiler technology for analysis. Find another project group for opposition.
    Send your choice with short motivation by email to C. Kessler by 25 sep 2009.
    Also, inform C. Kessler about who will be your opponent, and whom you will be opponent for.

  • Do the project. Deadline: 5 oct 2009.
  • For compiler framework projects:
    Prepare a slide presentation of about 20 minutes (per group member) on your project (framework, optimization, platform) and your results, and submit the slides to C. Kessler and to your opponent(s) by 5 oct 2009.

    For paper study projects:
    Prepare a slide presentation of about 20 minutes (per group member) on your paper(s), and submit the slides to C. Kessler and to your opponent(s) by 5 oct 2009.

    If you do not receive any feedback from me during 6 october, assume that you can proceed with the presentation.

  • Opposition preparation:
    If you are opponent of a paper project, you should have read that paper / these papers by now. If you are opponent of a compiler framework project, study their setup, results and conclusions from their slide material.
    Submit to C. Kessler, by email, at least three questions (at least two technical ones, maybe one of general character) that you are going to ask about the project of the group you are opponent of, by 6 oct 2009.

    If you do not receive any immediate feedback from me, assume that you can proceed with the opposition as planned.

  • Presentation sessions
    are scheduled for 7/10 10-12, 9/10 15-17, 12/10 13-15 and 13/10 08-10.
    Presence is mandatory even in sessions where you do not present or oppose.
    Presentations are 20 minutes (40 for groups of 2) plus 10 minutes for opposition and discussion.

  • Written summary
    A written summary of your presentation should be handed in to C. Kessler (cc your opponent for information) by 16 oct 2009 by email to chrke55.liu \at analys.urkund.se.

    The summary is expected to have 2-3 pages A4 single-spaced text including figures and diagrams, written in decent English and using appropriate scientific writing style. PDF format is preferred.
    For compiler framework projects: Include all necessary technical details of your experimental setup (such as compiler version etc.). Present your experimental results in appropriate form (diagrams).
    For paper study projects: Do not simply copy text material from the original paper - this would be considered plagiarism and is not accepted. Instead, express the paper's contributions and your critique of it with your own words.


    Page responsible: Christoph W Kessler
    Last updated: 2009-08-24