Antal högskolepoäng: 7,5. Betygsskala: TH. Nivå: A (Avancerad nivå). Huvudområde: Teknik. Undervisningsspråk: Kursen ges på svenska. Valfri för: D4, D4is, D4pv, E4, E4pv, Pi4. Kursansvarig: Univ.lektor Jonas Skeppstedt, Jonas.Skeppstedt@cs.lth.se, Datavetenskap. Förkunskapskrav: EDAF05 Algoritmer, datasrukturer och komplexitet eller EDA027 Algoritmer och datastrukturer. Prestationsbedömning: Tentamen är skriftlig. Ett projekt ingår i kursen. Detta skall fullgöras inom en månad efter kursens slut. Slutbetyget bestäms av betygen på den skriftliga tentamen och ett frivilligt extra projekt. Poängsatta delmoment: 2. Övrigt: Obligatoriska moment: Övningar, datorlaborationer och projektuppgift. Hemsida: http://cs.lth.se/eda230.

Syfte
Kursens syfte är att studenterna skall förstå möjligheter och begränsningar hos moderna optimerande kompilatorer, och därigenom veta vad de behöver optimera för hand och vad kompilatorer kan optimera automatiskt.

Mål

Kunskap och förståelse
För godkänd kurs skall studenten

• förstå vilka algoritmer och datastrukturer som används vid implementation av moderna optimerande kompilatorer, samt

• förstå vilka språkkonstruktioner som begränsar optimeringsmöjligheter.

Färdighet och förmåga
För godkänd kurs skall studenten

• kunna analysera benchmarkprogram för att se vilka optimeringsalgoritmer som är lämpliga att implementera, samt

• kunna implementera givna optimeringsalgoritmer på SSA form, kontrollera att de är korrekt implementerade, samt mäta prestandaeffekter.

Värderingsförmåga och förhållningssätt
För godkänd kurs skall studenten

• kunna på egen hand sätta sig in i en vetenskaplig artikel i ämnet, och presentera denna muntligt för de andra studenterna,

• kunna bedöma ungefär hur lång tid det kan tänkas ta att implementera den presenterade algoritmen, samt bedöma om det kan anses vara värt arbetet, samt

• kunna bedöma om en optimeringsteknik kan vara lämplig att använda för hand i de fall kompilatorn inte kan göra det automatiskt.

Innehåll
Kontrollflödesanalys, dataflödesanalys, beroendeanalys, aliasanalys, elimination av redundans, optimering av loopar, optimering av proceduranrop, registerallokering, schemaläggning av instruktioner, optimering för objektorienterade språk, optimering av minneshierarkin samt vektorisering för processorer med SIMD instruktioner, t.ex. AltiVec och CELL.

Litteratur
Skeppstedt, J: An Introduction to the Theory of Optimising Compilers with Performance Measurements on Power Processors.

Kod: 0111. Benämning: Obligatoriska moment.
Antal Högskolepoäng: 3. Betygsskala: UG. Prestationsbedömning: För godkänt betyg krävs fullgjorna övningar, laborationer och projekt.

Kod: 0211. Benämning: Tentamen i optimerande kompilatorer.
Antal Högskolepoäng: 4,5. Betygsskala: TH. Prestationsbedömning: Skriftlig tentamen. Slutbetyg på kursen baseras på resultatet av denna tentamen och ett frivilligt extra projekt.