Machine learning of compiler heuristics for parallel architectures

Computer architectures are continuously evolving: they become faster, more feature rich and more complex every time a new one is released. In order to fully exploit them, compilers have to be updated as well, to allow the programmers to have full access to all the computational power these modern architectures provide. Unfortunately, while Moore's law predicts that the number of transistors in processors doubles roughly every two years, Proebsting's Law tells us that the optimization level provided by compilers can be expected to double every eighteen years. Such numbers give us a clear insight about how difficult it is for compilers to keep the pace with the innovations introduced by the hardware. The main problem is that most compiler optimizations can provide either speedups or slowdowns depending on the code they are applied to and depending on which other transformations are applied before and after the one being considered. Deciding whether and when to apply an optimization algorithm is a daunting task, and the complexity of the architectures makes the usage of exact models to predict the outcome unfeasible, so compilers rely on heuristics to make such decisions. The process of writing heuristics is, traditionally, mostly based on the personal experience of the compiler writer and involves a time-consuming trial and error process. Much work has been done recently to try and substitute the compiler writer with automated algorithms for performing this task. Iterative compilation and machine learning approaches have been studied, each with its own merits and shortcomings. This thesis work is rooted in this research area. First of all, it presents long-term learning, a new learning algorithm that aims at automatically determining efficient compilation heuristics. Long-term learning tries to overcome the main issue of most iterative compilation and machine learning approaches (the long compilation times and the need for a time-consuming initial training phase) while still providing their advantages. Similar challenges have been faced already by recent works in the area, but, unique to long-term learning is the ability to solve them while generating human-readable heuristics (in the form of mathematical formulas) and while taking into consideration the fact that the single code transformation algorithms are not independent, therefore their heuristics need to be evolved in such a way to interact well with one another. In order to further speedup the execution of the long-term learning algorithm, this thesis presents a method to parallelize it across multiple machines or to execute it in parallel on a single machine by splitting up its resources, using an approach based upon MapReduce. This approach is not limited to long-term learning, but it is general and it can be applied to most iterative compilation algorithms. Finally, two proposals are presented as future work. First, a new lightweight compilation method for highly dynamic parallel programs, allowing one to divide the compilation process between compile-time and runtime, keeping as much as possible of the heavyweight computations at compile-time, and applying at runtime only those transformations that could benefit from information not available at compile-time, using a technique derived from long-term learning to choose which optimizations to postpone at runtime. Second, starting from an analysis of the sensitivity to hardware faults of synchronization primitives, namely locks and transactional memories, a use of long-term learning as the basis for a novel approach to fault recovery is presented.

Le architetture dei calcolatori sono in continua evoluzione: guadagnano nuove funzionalità e diventano più veloci, e complesse ogni volta che ne viene rilasciata una nuova. Al fine di sfruttarle pienamente, è necessario che anche i compilatori vengano aggiornati, per permettere ai programmatori di avere pieno accesso a tutta la potenza di calcolo fornita da tali architetture moderne. Sfortunatamente, mentre la legge di Moore predice che il numero di transistor nei processori raddoppi circa ogni due anni, la legge di Proebsting ci dice che il livello di ottimizzazione fornito dai compilatori è previsto raddoppiare ogni diciotto anni. Tali numeri ci danno una chiara idea di quanto sia complicato per i compilatori tenere il passo delle innovazioni introdotte dall'hardware. Il problema principale è che molte ottimizzazioni di compilazione possono fornire sia un miglioramento sia un peggioramento delle prestazioni, a seconda del codice a cui sono applicate, e a seconda di quali altre trasformazioni vengono applicate prima e dopo quella considerata. Decidere se e quando applicare un algoritmo di ottimizzazione è un compito estremamente complesso, e la complessità delle architetture rende impossibile l'uso di modelli esatti per predire il risultato, perciò i compilatori utilizzano euristiche per prendere tali decisioni. Il processo di scrittura delle euristiche è, tradizionalmente, basato soprattutto sull'esperienza personale del compilatorista e include un lungo processo di evoluzione delle stesse per prove ed errori. Molti lavori si sono occupati di recente di provare a sostituire al compilatorista degli algoritmi automatici per svolgere questo compito. A tale scopo sono state sviluppate la compilazione iterativa e algoritmi di apprendimento automatico applicato alla compilazione: ognuno di questi due approcci presenta pregi e difetti. Questa tesi si colloca in quest'area di ricerca. Prima di tutto, essa presenta \emph{long-term learning} (apprendimento di lungo termine), un nuovo algoritmo di apprendimento che mira a definire automaticamente delle euristiche di compilazione efficienti. Long-term learning prova a superare i principali ostacoli della compilazione iterativa e degli approcci di apprendimento automatico (i lunghi tempi di compilazione e il bisogno di svolgere una lunga fase di addestramento iniziale) e al tempo stesso ne mantiene i vantaggi. Sfide simili sono già state affrontate da recenti lavori dell'area, ma, unica dell'apprendimento di lungo termine è la capacità di risolverli generando euristiche facilmente comprensibili (nella forma di formule matematiche) e tenendo in considerazione il fatto che i singoli algoritmi di trasformazione del codice non sono indipendenti, quindi le loro euristiche necessitano di essere evolute in modo tale da interagine bene le une con le altre. Al fine di velocizzare ulteriormente l'esecuzione dell'algoritmo di apprendimento di lungo termine, questa tesi presenta un metodo per parallelizzarlo su più macchine, o per eseguirlo in parallelo su una singola macchina suddividendone le risorse, usando un approaccio basato su MapReduce. Questo approccio non è limitato all'uso su long-term learning, ma è generale e può essere applicato alla maggior parte degli algoritmi di compilazione iterativa. Infine, vengono presentate due proposte di lavori futuri. Primo, un nuovo metodo leggero di compilazione per programmi altamente dinamici, che permette di suddividere il processo di compilazione tra compile-time e runtime, mantenendo quanto più possibile i calcoli più pesanti a compile-time ed applicando a runtime solo quelle trasformazioni che potrebbero beneficiare della disponibilità di ulteriori informazioni non disponibili in precedenza, uando una tecnica derivata dall'apprendimento di lungo termine per determinare quali ottimizzazioni posticipare a runtime. Secondo, a partire da un analisi della sensibilità delle primitive di sincronizzazione (lock e memorie transazionali) ai guasti hardware, viene proposto un uso dell'apprendimento di lungo termine come base per un nuovo approccio al recupero dai guasti.