Code transformation in high level synthesis for iterative stencils

Scientific applications may be characterized by a high degree of parallelism which make them suitable to be implemented on programmable devices such as Field Programmable Gate Arrays. To automatize the creation of these hardware implementations, High Level Synthesis has been introduced. It consists of a set of methodologies aimed at creating a hardware implementation starting from a high level source code description. Among these methodologies the techniques for the data dependency analysis have a particular relevance. One of them is the polyhedral analysis which allows to identify some possibilities of parallelization inside loops that are due to the presence of the same operations applied to a large amount of data. To achieve this parallelism it is necessary to replicate the operations and to allow parallel accesses to the data. The contribution of this thesis is a methodology for the High Level Synthesis that is able to replicate the parallelizable section of the code, identified by the polyhedral analysis. This goal is reached with a data reorganization that satisfies data dependences, minimizes memory accesses and parallelizes the remaining accesses.

Le applicazioni utilizzate nell’ambito del calcolo scientifico possono essere caratterizzate da un elevato grado di parallelismo che ben si adatta alla struttura di dispositivi programmabili come Field Programmable Gate Array. Per poter automatizzare la generazione dell’implementazione hardware è stata introdotta la Sintesi ad Alto Livello, una serie di metodologie che permettono la generazione automatica di descrizioni hardware partendo da codice di alto livello. All’interno di queste tecniche rivestono un ruolo fondamentale le tecniche di analisi delle dipendenze dati. Tra queste l’analisi poliedrale permette di individuare delle possibilità di parallelizzazione all’interno dei cicli dovute all’applicazione delle stesse operazioni su una gran quantità di dati. Per poter massimizzare questo parallelismo è necessario che le operazioni vengano replicate e i dati possano essere acceduti in modo parallelo. Questa tesi vuole contribuire allo stato dell’arte proponendo una metodologia per replicare durante la sintesi ad alto livello la parte di codice parallelizzabile riconosciuta mediante analisi poliedrale. Questo obiettivo è ottenuto mediante una riorganizzazione dei dati in modo che siano rispettate le dipendenze di dato, sia minimizzato il numero di accessi ai dati e siano ottimizzati gli accessi paralleli.