A methodology for the high level synthesis of iterative algorithms

Usually, algorithms for multimedia applications and image processing are formulated as an iteration of an elementary frame transformation. State-of-the-art implementations of these algorithms, however, do not consider the fact that there is a predefined dependencies pattern among the elements used by two consecutive iterations of that elementary frame transformation. As a consequence, every manipulated pixel typically depends on a limited number of neighbors coming from the previous iteration. In this thesis work, a flow that automatically generates modular architectures for a wide family of iterative algorithms, which are characterized by well-defined dependencies pattern is presented. The proposed flow automatically analyzes the dependencies between subsequent iterations, generates a set of candidate hardware architectures that exploit data dependencies locality, and finds the Pareto-optimal solutions that minimizes the resource usage while satisfying throughput requirements. The performance of the resulting architectures has been proved to be competitive with popular iterative algorithms of different complexities, even when compared to manually-optimized implementations. Two important case studies are presented: the iterative convolutions algorithms and the Chambolle algorithm.

Solitamente, gli algoritmi per applicazioni multimediali ed elaborazione di immagini sono formulati come l’iterazione di una trasformazione elementare applicata ad un frame in ingresso. Le implementazioni di questi algoritmi disponibili nello stato dell’arte, in ogni caso, non considerano il fatto che, tra gli elementi usati da due iterazioni consecutive della trasformazione elementare precedentemente introdotta, esiste uno schema predefinito. Di conseguenza, ogni pixel tipicamente dipende solo da un numero limitato di pixel vicini calcolati all’iterazione precedente. In questo lavoro di tesi, viene presentato un flusso che genera una architettura modulare per una larga famiglia di algoritmi iterativi caratterizzata da uno schema ben definito di dipendenze tra due iterazioni successive. In particolare, il flusso proposto analizza automaticamente queste dipendenze e genera un insieme di possibili architetture hardware che sfruttano la localitá spaziale dei dati e trova le soluzioni Pareto ottimali che minimizzano l’utilizzo di area soddisfacendo requisiti di throughput minimi richiesti dal progettista. Le prestazioni delle architetture risultanti sono competitive su algoritmi iterativi di differente complessitá anche quando comparate con implementazioni ottimizzate manualmente. Vengono presentati due importanti casi di studio: gli algoritmi convolutivi iterativi e l’algoritmo Chambolle.