Microarchitecture-aware mixed precision tuning

The increasing demand to perform more complex computations on every kind of platform - ranging from low-cost processors found in internet of things devices, to large data centers - demands an increased effort in the optimization of each algorithm for the particular target architecture. The requirement of ever faster processing time and devices with longer battery life of portable devices calls for deeper knowledge of the applications domains in order to better optimize each algorithm. Because of these factors, mixed precision tuning is increasingly being used in a vast number of application areas. This technique aims at lowering the execution time of an algorithm by changing the precision of some values. It exploits the great multitude of data types for number representation, each one with its own strength. In this field, scientific research has focused its efforts on finding innovative approaches to automate the process, and as a result it developed several tools to do so, although they require very long processing times. In this thesis, we propose an innovative approach to deal with the problem of precision tuning, based on the widely used theory of linear programming. It works by building a model of the program being optimized during the compilation. This approach tackles the problem in a static way, thus reducing the computation time. The proposed solution has been implemented by extending a state of the art tool, TAFFO, which in turn relies on the LLVM toolchain. This tool, originally built to convert existing programs to work with fixed point math, has been extended to allow it to handle multiple output data types. Our work has been evaluated by applying mixed precision tuning on the Polybench benchmark suite, to prove the effectiveness of the solution proposed.

La crescente necessità di effettuare computazioni sempre più complesse su ogni tipo di piattaforma, dai processori a basso costo utilizzati in contesti di tecnologia pervasiva ai grandi centri di elaborazione, richiede uno sforzo sempre maggiore nell'ottimizzare ogni algoritmo per la specifica architettura sulla quale verrà eseguito. La richiesta di tempi di elaborazione sempre più brevi e l'obiettivo di rendere l'autonomia dei dispositivi sempre più lunga richiedono una conoscenza approfondita dei domini di applicazione al fine di ottimizzare gli algoritmi. Per questo motivo, il mixed precision tuning viene sempre più spesso utilizzato negli ambiti più diversi. Questa tecnica permette di ridurre il tempo di esecuzione di alcuni algoritmi riducendo la precisione di alcuni valori, grazie all'utilizzo di svariati tipi di rappresentazione per i dati numerici, ognuno con i propri vantaggi, all'interno di un singolo programma. La ricerca in questo settore sta concentrando gli sforzi per trovare modi innovativi di automatizzare l'operazione, proponendo diversi tool che adempiono al compito, a discapito dei lunghi tempi di elaborazione. In questa tesi, viene proposta una nuova metodologia per affrontare il problema, basandosi sulle tecniche emergenti della programmazione lineare, costruendo un modello del programma durante la compilazione. Il metodo proposto permette quindi di risolvere il problema in modo statico, riducendo quindi i tempi di elaborazione. La modellizzazione proposta è stata quindi implementata in un tool allo stato dell'arte, TAFFO, basato sulla toolchain LLVM. Questo tool, pensato inizialmente per convertire programmi esistenti al fine di utilizzare i fixed point, è stato esteso per permettere la conversione in diversi tipi di dato finali. Il lavoro è stato quindi valutato effettuando il processo di precision tuning sulla suite di benchmark Polybench, per confermare la validità del modello.