Compiler autotuning using machine learning techniques

Recent developments in silicon production and fabrication led to the creation of much faster computational units such as CPUs, GPUs, FPGAs, and similar chips with varying instruction set architectures (ISAs). Software (SW) programming paradigms including OpenMP, MPI, OpenCL, and OpenACC allow software developers to exploit Hardware (HW) parallelism to port legacy serial codes on these emerging platforms to attain application speedups. Compilers struggle to keep up with the increasing development pace of ever-expanding hardware and software programming paradigms. Additionally, growing complexity of the modern compilers and the concern over security are among the more serious problems that compilers should answer. Moore’s law states that transistor density should double every two years; however, the rate of compilers, which are faced with many open-research problems, have not been able to improve more than a few percentage points each year. Diversity of today’s architectures have forced programmers to spend additional ef- fort to port and tune their application code across different platforms. Compilers within this process need additional tuning which is a hard task itself. Recent compilers of- fer a vast number of multilayered optimizations, capable of targeting different code segments of an application. Choosing among these optimizations can significantly im- pact the performance of the code being optimized. The selection of the right set of compiler optimizations for a particular code segment is a very hard problem, but find- ing the best ordering of these optimizations adds further complexity. In fact, finding the best ordering is a long standing problem in compilation research called the phase- ordering problem. The traditional approach of constructing compiler heuristics to solve this problem simply can not cope with the enormous complexity of choosing the right ordering of optimizations for every code segment in an application. In this PhD thesis, we provide break-through approaches to tackle and mitigate the well-known problems of compiler optimization using design space exploration and ma- chine learning techniques. We show that not all the optimization passes are beneficial to be used within an optimization sequence and in fact many of the available passes are obliterating the effect of one another when ordering of the phases are taken into account. Experimental results show major improvement in performance metrics when our customized prediction models are in place versus standard fixed optimization passes predefined within state-of-the-art compiler frameworks e.g. GCC, LLVM, etc. We per- form application specific optimization based on the characteristics of applications under analysis and we show that this methodology is beneficial to mitigate the hard problem of selecting the best compiler optimizations and the phase-ordering problem. Late but not least, we hope that the proposed approaches in this PhD thesis will be useful for a wide range of readers, including computer architects, compiler developers, researchers and technical professionals.

I recenti sviluppi nella produzione di silicio e la fabbricazione hanno portato alla creazione di unità molto più veloce di calcolo, come CPU, GPU, FPGA, e chip simili con diversi set di istruzioni architetture (ISA). Software (SW) programmazione paradigmi tra cui OpenMP, MPI, OpenCL, e OpenACC consentono agli sviluppatori di software di sfruttare hardware (HW) parallelismo codici seriali porta legacy su queste piattaforme emergenti per ottenere incrementi nella velocità di applicazione. I compilatori lottano per tenere il passo con il ritmo crescente sviluppo di continua espansione hardware e software paradigmi di programmazione. Inoltre, crescente complessità dei compilatori moderni e la preoccupazione per la sicurezza sono tra i problemi più gravi che i compilatori dovrebbero rispondere. La legge di Moore afferma che la densità transistor dovrebbe raddoppiare ogni due anni; tuttavia, il tasso di compilatori, che si trovano ad affrontare molti problemi aperti di ricerca, non sono stati in grado di migliorare più di un paio di punti percentuali ogni anno. La diversità delle architetture di oggi hanno costretto i programmatori a spendere ulteriore ef- forte alla porta e ottimizzare il loro codice di applicazione su diverse piattaforme. I compilatori all'interno di questo processo hanno bisogno di ulteriori operazioni di ottimizzazione, che è un compito difficile in sé. compilatori recenti di- fer un vasto numero di ottimizzazioni multistrato, capaci di colpire diversi segmenti di codice di un'applicazione. Scegliendo tra queste ottimizzazioni può significativamente impatto le prestazioni del codice essere ottimizzato. La scelta del giusto set di ottimizzazioni del compilatore per un particolare segmento di codice è un problema molto difficile, ma trovare, ing il migliore ordinamento di queste ottimizzazioni aggiunge ulteriore complessità. In effetti, trovare il miglior ordinamento è un annoso problema nella ricerca di compilazione chiamato il problema ordine di fase. L'approccio tradizionale di costruire euristiche compilatore per risolvere questo problema semplicemente non possono far fronte con l'enorme complessità di scegliere il giusto ordine delle ottimizzazioni per ogni segmento di codice in un'applicazione. In questa tesi di dottorato, forniamo approcci break-through per affrontare e mitigare i ben noti problemi di ottimizzazione del compilatore utilizzando l'esplorazione dello spazio di progettazione e tecniche di apprendimento macchina. Abbiamo dimostrato che non tutti i passi di ottimizzazione sono utili per essere utilizzato all'interno di una sequenza di ottimizzazione e di fatto molti dei passaggi disponibili sono cancellando l'effetto di uno con l'altro in fase d'ordine delle fasi sono presi in considerazione. I risultati sperimentali mostrano notevole miglioramento metriche di performance in cui i nostri modelli di previsione personalizzati sono in atto contro ottimizzazione fissa standard di pass predefiniti all'interno dello Stato-of-the-art quadri compilatore per esempio GCC, LLVM, ecc perfetta- ottimizzazione specifica applicazione modulo in base alle caratteristiche delle applicazioni oggetto di analisi e si dimostra che questa metodologia è utile per mitigare il problema difficile di selezionare i migliori ottimizzazioni del compilatore e il problema della fase-ordinazione. In ritardo ma non meno importante, ci auguriamo che gli approcci proposti in questa tesi di dottorato saranno utili per una vasta gamma di lettori, tra cui gli architetti informatici, sviluppatori del compilatore, ricercatori e professionisti tecnici.