Machine learning of compiler heuristics for parallel architectures
Michele Tartara · 2013
Le architetture dei calcolatori sono in continua evoluzione: guadagnano nuove funzionalita e diventano piu veloci, e complesse ogni volta che ne viene rilasciata una nuova. Al fine di sfruttarle pienamente, e 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 e 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 e 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 e un compito estremamente complesso, e la complessita delle architetture rende impossibile l'uso di modelli esatti per predire il risultato, percio i compilatori utilizzano euristiche per prendere tali decisioni. Il processo di scrittura delle euristiche e, 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 gia state affrontate da recenti lavori dell'area, ma, unica dell'apprendimento di lungo termine e la capacita 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 piu macchine, o per eseguirlo in parallelo su una singola macchina suddividendone le risorse, usando un approaccio basato su MapReduce. Questo approccio non e limitato all'uso su long-term learning, ma e generale e puo 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 piu possibile i calcoli piu pesanti a compile-time ed applicando a runtime solo quelle trasformazioni che potrebbero beneficiare della disponibilita 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 sensibilita 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.