Optimization Techniques for Auto-tuning GPUs: An Empirical Study of Image-based GPU Kernels

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.

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.