dc.contributor.advisor | Elster, Anne C. | |
dc.contributor.author | Tørring, Jacob Odgård | |
dc.date.accessioned | 2021-09-15T16:16:51Z | |
dc.date.available | 2021-09-15T16:16:51Z | |
dc.date.issued | 2020 | |
dc.identifier | no.ntnu:inspera:57320302:24037381 | |
dc.identifier.uri | https://hdl.handle.net/11250/2777877 | |
dc.description | Full text not available | |
dc.description.abstract | Med den moderne utviklingen av datamaskinarkitektur, spesielt med utviklingen av akseleratorer
slik som GPUer(Graphics Processing Unit), så blir det stadig vanskeligere å
skrive effektive programmer. Når disse arkitekturene i tillegg endrer seg fra år til år, så blir
det enda vanskeligere å få utnyttet ytelsen til systemene. Av denne grunnen har vi sett en
økning av interesse for empirisk auto-tuning de siste tiårene.
Selv om nye auto-tuning algoritmer regelmessig blir publisert, så er det likevel en betydelig
utfordring å sammenligne disse på en god måte. I denne oppgaven presenterer vi et
empirisk studie over de mest avanserte auto-tuning algoritmene i feltet. Vi sammenligner
dem ved å variere en rekke faktorer, inkludert eksempelstørrelser, standard programmer
og datamaskinarkitekturer. Dette eksponerer at det ideelle valget av auto-tuning algoritme
er sterkt avhengig av antall eksempler som algoritmen blir matet med. Våre resultater gi
ny viten, ved å vise at ingen av metodene våre utkonkurrerer alle andre for alle størrelser
av prøver.
Vi sammenligner Tilfeldig Søk(RS), Random Forest Regression(RF), AUMA, Genetiske
Algoritmer(GA), Bayesisk Optimalisering med Gaussiske Prosesser (BO GP) og Bayesisk
Optimalisering med Tree-Parzen Estimators(BO TPE).
Resultatene våres viser at BO GP utkonkurrerer de andre algoritmene i de fleste tilfeller
med eksempelstørrelser mellom 25 og 100, mens GA normalt utkonkurrerer de andre for
størrelser fra 200 og videre. Den optimale algoritmen kan variere avhengig av den spesifikke
kombinasjonen av benchmark og arkitektur, spesielt for lave eksempelstørrelser slik
som 25 hvor BO TPE eller AUMA ofte gjør det bedre. Studiet våres viser at veldig lave eksempelstørrelser
er underrepresentert i faglitteraturen. Resultatene våres viser at selv om
BO GP gjør det bra generelt sett for eksempelstørrelse 25, så er resultatene sterkt avhengig
av benchmarken og arkitekturen. Noen ganger gjør BO GP det betydelig dårligere enn RS
i disse tilfellene. Vi oppfordrer dermed til mer forskning på algoritmer for veldig lave
eksempelstørrelser.
Generelt er det størst forbedring sammenlignet med RS ved lave eksempelstørrelser,
fra 25 til 100. Etterhvert som eksempel størrelsene vokser, så minker gapet mellom de
model-baserte metodene og RS. Det optimale valget for model-baserte algoritmer sammenlignet
med RS for eksempelstørrelse 25, 50, 100, 200, og 400 har gjennomsnittsverdi
på henholdshvis 1.16x, 1.18x, 1.14x, 1.09x og 1.08x, på tvers av all benchmarks og
arkitekturer.
Denne eksperimentelle metodikken viser et større behov for empirisk nøyaktighet når
man presenterer nye auto-tuning algoritmer. Vi publiserer herved våres resultater sammen
med en fullstendig kodebase og alle våre rådata, slik at det akademiske miljøet har alle
ressurser tilgjengelig for videre studier. Vi presenterer også viktig videre arbeid i slutten
av rapporten. | |
dc.description.abstract | With advances in computing systems, especially with the complexities of modern accelerators,
such as GPUs (Graphic Processing Units), it has become challenging to write
efficient programs that take advantage of the available parallelism and complex memory
systems. Added to that, these architectures change yearly, if not more often, further challenging
how to get the desired performance out of these systems. For this reason, empirical
auto-tuning has gained interest during the past decades.
While new auto-tuning algorithms are regularly presented and published, comparing
these auto-tuning algorithms is a deceptively difficult task. In this thesis, a thorough empirical
study of state-of-the-art auto-tuning algorithms is conducted to compare them on
a range of sample sizes, benchmarks and architectures. Our work exposes that the ideal
auto-tuning algorithm is heavily dependent on the sample size, and shows that no single
state-of-the-art algorithm outperforms the rest for all sample sizes.
We compare Random Search (RS), Random Forest Regression (RF), AUMA, Genetic
Algorithms (GA), Bayesian Optimization with Gaussian Processes (BO GP) and Bayesian
Optimization with Tree-Parzen Estimators (BO TPE). Our results show that BO GP outperforms
the other algorithms in most scenarios with sample sizes from 25 to 100, while GA
usually outperforms the others for sample sizes 200 and beyond. For very low sample sizes
like 25, BO TPE and AUMA sometimes outperforms BO GP for specific benchmarks and
architectures. Our survey shows that very low samples sizes like 25, are severely underrepresented
in previous research. We therefore encourage more research into algorithms
for very low sample sizes.
Our study found that in general, the most advantage over RS can be gained in the
lower range of sample sizes, with sample sizes from 25 to 100. As the sample sizes
grows larger, the gap between model-based approaches and RS decreases. The optimal
choice of a model-based algorithm for samples sizes 25, 50, 100, 200 and 400 have mean
improvements over RS of 1.16x, 1.18x, 1.14x, 1.09x and 1.08x across all benchmarks and
architectures.
This experimental methodology exposes a greater need to examine a wide range of
factors with empirical rigorousness when presenting novel auto-tuning algorithms. We
publish our results together with our full code base and all our raw data for the research
community to perform further analysis. We also provide directions for important future
work. | |
dc.language | | |
dc.publisher | NTNU | |
dc.title | Optimization Techniques for
Auto-tuning GPUs: An Empirical Study
of Image-based GPU Kernels | |
dc.type | Master thesis | |