Cover Page The handle http://hdl.handle.net/25180 holds

Cover Page
The handle http://hdl.handle.net/1887/25180 holds various files of this Leiden University
dissertation
Author: Rietveld, K.F.D.
Title: A versatile tuple-based optimization framework
Issue Date: 2014-04-10
Samenvatting
Een veelzijdig optimalisatieraamwerk gebaseerd op tupels
Het hart van een computer is de Centrale Verwerkingseenheid (CVE, Engels:
CPU, Central Processing Unit). Deze eenheid voert programma’s uit welke zijn
opgebouwd uit elementaire instructies zoals het lezen van data uit het geheugen
en het uitvoeren van simpele operaties op data. Het opstellen van programma’s
in dit soort elementaire instructies is een zeer tijdrovend proces. Dit heeft geleid
tot de ontwikkeling van programmeertalen, waarin programma’s op een hoger,
abstracter niveau kunnen worden uitgedrukt. Met behulp van software kunnen
programma’s die zijn geschreven in zo’n programmeertaal automatisch worden
vertaald naar een machinecode die door de Centrale Verwerkingseenheid kan
worden uitgevoerd.
Programmeertalen kunnen worden ingedeeld in verschillende paradigma’s.
Twee paradigma’s die in dit proefschrift centraal staan zijn imperatieve programmeertalen en declaratieve programmeertalen. Met imperatieve programmeertalen wordt de berekening die moet worden uitgevoerd stap voor stap beschreven.
Er wordt dus exact vastgelegd hoe de berekening moet worden uitgevoerd. Daarentegen wordt met declaratieve programmeertalen vastgelegd wat moet worden
gedaan, bijvoorbeeld welke data moet worden opgehaald uit een database, maar
niet hoe en niet in welke volgorde.
Tijdens de vertaalslag naar machinecode kunnen programma’s worden aangepast zodat deze effici¨enter werken, onder de voorwaarde dat de semantiek/betekenis van het programma ongewijzigd blijft. Deze effici¨entere machinecodes voeren
het programma uit in minder tijd of werkgeheugen. In de praktijk is de manier
waarop deze optimalisaties worden uitgevoerd afhankelijk van het programmeerparadigma. Bij de optimalisatie van declaratieve programma’s ligt de nadruk
op het bepalen van een effici¨ent stappenplan voor het ophalen van de gespecificeerde data. Dit stappenplan bestaat uit een aaneenschakeling van aanroepen
naar vooraf vastgelegde routines die al in machinecode zijn uitgedrukt. Imperatieve programma’s worden in de regel vertaald naar machinecode met een “compiler”. Geavanceerde compilers zijn uitgerust met transformaties. Dit zijn transformaties als het herordenen van de stappen die door het programma worden
uitgevoerd of het selecteren van effici¨ente instructies om de benodigde berekeningen uit te voeren. Deze transformaties hebben als doel specifieke functionaliteiten
en karakteristieken van het beoogde hardwareplatform beter te benutten. Compi-
242
Samenvatting
lers die in staat zijn dit soort optimaliserende transformaties toe te passen worden
“Optimizing Compilers” genoemd.
In de regel worden applicatieprogramma’s geschreven in een imperatieve programmeertaal. Specificaties voor het ophalen van data uit een database worden
veelvuldig geschreven in een declaratieve programmeertaal. Een voorbeeld van
zo’n declaratieve taal is SQL en specificaties geschreven in SQL worden “queries”
genoemd. Database applicaties zijn applicatieprogramma’s die data verwerken
welke zijn opgeslagen in een database. Zulke applicaties zijn dus opgebouwd uit
zowel imperatieve als declaratieve codes. Deze codes worden onafhankelijk van
elkaar geoptimaliseerd op verschillende manieren en in verschillende modules.
Dus, de declaratieve codes die data ophalen worden onafhankelijk geoptimaliseerd van imperatieve codes die de opgehaalde data verder verwerken.
Het eerste deel van dit proefschrift richt zich op database applicaties en in het
bijzonder op web applicaties. Web applicaties verzorgen interactieve websites,
waarop bijvoorbeeld reizen kunnen worden geboekt of aankopen gedaan. Deze
applicaties zijn in het algemeen modulair opgebouwd: naast de applicatie zelf
wordt er gebruik gemaakt van een web server en een databasesysteem (DBMS:
Database Management System). Door deze modulariteit kunnen web applicaties
in een (zeer) kort tijdbestek worden ge¨ımplementeerd. Echter, deze modulariteit
heeft zijn prijs. Door de verschillende modules met elkaar te integreren kunnen
deze applicaties vele malen effici¨enter worden gemaakt. 90% van de machinecode instructies kunnen worden ge¨elimineerd zonder dat dit het eindresultaat
be¨ınvloed. Naast een significante verhoging in snelheid leidt dit ook tot een besparing van energie: minder servers zijn nodig om eenzelfde aantal bezoekers te
kunnen verwerken.
Het integreren van deze verschillende modules betekent ook dat de verschillende methodologi¨en om declaratieve en imperatieve programma’s te optimaliseren moeten worden samengevoegd. In dit proefschrift wordt een raamwerk
ge¨ıntroduceerd om deze integratie te faciliteren: het forelem raamwerk. Het forelem
raamwerk biedt een generieke methode om declaratieve codes voor de toegang
tot data uit te drukken in codes gebaseerd op imperatieve constructies zoals simpele loops (de forelem loop) en benaderingen van arrays. Dit maakt het mogelijk
oorspronkelijk declaratieve codes te mengen met imperatieve codes. Een belangrijke consequentie hiervan is dat traditionele analyses voor imperatieve codes,
zoals het ontdekken van ongebruikte resultaten, alsook traditionele imperatieve
transformaties, kunnen worden toegepast op deze gecombineerd codes. Hiermee
wordt het aantal optimalisatiemogelijkheden sterk vergroot.
Hoewel het forelem raamwerk in eerste instantie is ontwikkeld voor database
applicaties is het door de generieke aard ook toepasbaar in andere gebieden. Omdat het raamwerk is ontworpen voor database applicaties, is het opgebouwd rond
het wiskundige concept van tupels. Tupels zijn echter zeer geschikt als elementaire data representatie voor imperatieve codes, omdat tupels de meest fundamentele objecten zijn om met elkaar gerelateerd waarden te koppelen.
In het tweede deel van dit proefschrift wordt het gebruik van het forelem raamwerk bestudeerd voor het optimaliseren van irreguliere applicaties. Irreguliere
applicaties zijn moeilijk te optimaliseren door compilers, omdat het verloop van
de berekening van te voren niet geheel vast staat. Een optimalisatiemethode
243
wordt beschreven waarbij data gebruikt door een berekening wordt vertaald naar
tupels en de berekening zelf uitgedrukt wordt als forelem loops die deze tupels
verwerken en manipuleren. Op deze manier kan zowel de berekening worden
herordend alsmede de manier waarop tupels worden opgeslagen en gestructureerd. In feite leidt dit tot de automatische generatie van datastructuren door een
compiler. Deze technieken worden bestudeerd aan de hand van sparse matrix
berekeningen. Sparse matrices kennen vele toepassingen in het wetenschappelijk
rekenen en technische wetenschappen, zoals circuit simulaties en vloeistofdynamica.
Om het raamwerk toepasbaar te maken voor meerdere klassen van irreguliere
applicaties, wordt een uitbreiding beschreven voor het coderen van data afhankelijkheden. Een conditie kan worden aangegeven dat een tupel pas mag worden
verwerkt als tupels die aan de conditie voldoen al verwerkt zijn. Ten slotte beschrijft dit proefschrift een uitbreiding voor het uitdrukken van gedistribueerde
berekening in het forelem raamwerk.
Het forelem raamwerk dat is beschreven in dit proefschrift is in staat om zowel
traditionele imperatieve codes (zoals sparse matrix berekeningen) en declaratieve
codes (zoals database queries) te optimaliseren. Dit maakt het raamwerk veelzijdig en in vele gebieden toepasbaar. Ook kunnen optimalisatietechnieken die zijn
ontwikkeld in een bepaald gebied worden toepast in andere gebieden, iets dat
zonder onderliggend generiek raamwerk niet mogelijk is.
244
Samenvatting

Download Report