My Master’s Thesis

I submitted my MSc thesis in computer science in October 2017.

It is titled “Memory Block Merging in Futhark”.

Download the thesis.

Resumé

(This section is in Danish.)

Velkommen til det danske resumé af mit speciale. På dansk hedder mit speciale “Hukommelsesblokfletning i Futhark”. Undskyld hvis resuméet er forvirrende og uklart. Det er svært at beskrive på kort plads, og en del af det kræver nok en vis computerviden.

Strukturbaggrund

I 2011 begyndte jeg på datalogistudiet på Københavns Universitet. I starten af 2015 fik jeg en bachelorgrad derfra, og senere på året begyndte jeg så på kandidaten, som er den anden del af uddannelsen. Nu har jeg her i 2017 så brugt et halvt år på at skrive mit speciale, som er den endelige opgave på kandidaten. Når jeg har forsvaret (præsenteret) specialet, får jeg en kandidatgrad.

Indholdsbaggrund

Der er to hoveddele i titlen:

• Hukommelsesblokfletning
• Futhark

Hukommelsesblokfletning er et delvist opfundet ord som jeg groft sagt siger betyder “at tage flere områder hukommelse (fra RAM) i en computer og ændre dem så de bruger det samme område, så vi sparer hukommelse”. Dette er den teoretiske del af mit speciale.

Futhark er et programmeringssprog rettet mod at køre programmer på grafikkort – ikke for at lave 3D, men for at lave generelle tunge udregninger på smarte måder der passer til hardwarens fordele og begrænsninger. Futhark er et eksisterende sprog og har en hjemmeside på futhark-lang.org hvor man kan læse mere om det.

Futhark-sproget har en tilhørende oversætter som tager Futhark-programmer og oversætter dem til at kunne køre på grafikkort. Jeg har i mit speciale udvidet denne oversætter til at lave hukommelsesblokfletning, hvilket vi kalder en optimering. Dette er den praktiske del af mit speciale.

Eksempel

Her et et computerprogram på et meget abstrakt niveau:

1. Gør plads til et stort billede. Kald pladsen M.
2. Indlæs et stort billede. Kald det I og læg det i pladsen M.
3. Udskriv det store billede I.
4. Gør plads til endnu et stort billede. Kald pladsen M2.
5. Indlæs et nyt stort billede. Kald det I2 og læg det i pladsen M2.
6. Udskriv det store billede I2.

Vi har to store billeder som skal udskrives på en printer. I trin 1 fortæller vi computeren at vi skal have plads til et stort billede. I trin 2 indlæser vi et stort billede (fx fra en fil) og fortæller computeren at det skal ligge der hvor vi har gjort plads til det. I trin 3 fortæller vi så computeren at den skal udskrive billedet. I trin 4-6 gentages dette, bare med et nyt stort billede.

Det er fjollet både at gøre trin 1 og trin 4. Det første billede bliver aldrig brugt mere efter det er udskrevet i trin 3, så dets plads M kan egentlig godt genbruges. Vi ændrer derfor programmet til at have 5 trin:

1. Gør plads til et stort billede. Kald pladsen M.
2. Indlæs et stort billede. Kald det I og læg det i pladsen M.
3. Udskriv det store billede I.
4. Indlæs et nyt stort billede. Kald det I2 og læg det i pladsen M.
5. Udskriv det store billede I2.

Trin 4 genbruger nu den allerede brugte plads M i stedet for at bruge en ny plads. Vi har flettet hukommelsesblokkene M og M2 og sparet plads.

Det her er et meget simplificeret eksempel, men idéen er nogenlunde derhenaf.

Resultater

Målet med min optimering er at

• få programmer i Futhark til at bruge mindre hukommelse, samt at
• få programmer i Futhark til at køre lidt hurtigere.

Futhark har en masse eksisterende større programmer som jeg har oversat og kørt både uden mine optimeringer og med mine optimeringer. Deres resultater har jeg så sammenlignet.

Med mine optimeringer bruger programmerne mellem 0% (ingen ændring) og 70% mindre hukommelse, hvilket er godt. De bliver mellem -28% (dvs. langsommere) og 16% hurtigere, hvilket er et lidt mere blandet resultat. Dog har jeg en okay idé om hvorfor nogle af dem bliver langsommere (læs mere om det i selve specialet).

Resten

Der er mange flere eksempler i rapporten, og der er de beskrevet bedre end her. Jeg har også forsøgt at formalisere mine optimeringer, men det gik knapt så godt.

Koden ligger på github.com/diku-dk/futhark/. Kig i mappen src/Futhark/Optimise/MemoryBlockMerging/. Det er okay, men ikke helt poleret.