OPoly: an OpenMP polyhedral compiler

In questa tesi introduciamo la polyhedral compilation, una moltitudine di tecniche volte a rappresentare programmi, specialmente quelli che coinvolgono cicli innestati e vettori, rappresentandoli attraverso poliedri parametrici e sfruttando alcune trasformazioni su di essi per analizzare e ottimizzare automaticamente i programmi dati. In particolare, descriviamo la nostra implementazione di un polyhedral compiler: OPoly. OPoly è un'applicazione realizzata in Python in grado di parallelizzare automaticamente cicli innestati che possono essere espressi attraverso un insieme di equazioni ricorsive uniformi. OPoly analizza dei cicli innestati scritti in pseudolinguaggio e genera del codice sorgente parallelizzabile scritto in C e compreso di direttive OpenMP, che può rimpiazzare l'implementazione seriale originale, senza cambiarne il significato. OPoly sfrutta il linguaggio di modellazione per programmazione a vincoli MiniZinc per modellare il problemi di ottimizzazione dell'approccio poliedrico, che sono cruciali per trovare la trasformazione migliore possibile dal ciclo originale a quello parallelizzabile. Descriviamo l'architettura di OPoly e diamo alcune soluzioni pratiche a problemi che sorgono implementando un polyhedral compiler. Infine, compariamo le prestazioni del codice parallelizzabile generato da OPoly con quelle della relativa implementazione originale, studiando il caso di un noto algoritmo scientifico.