PolyFPGA : a tool to automatically accelerate iterative stencil loops

A wide range of scientific problems can be solved using stencil computations. Many particle interaction, computer vision algorithms as well as methods for solving Partial Differential equation are based on stencil computations. Therefore many studies have been done over the years in order to accelerate those kind of algorithms. The aim of this work is to introduce a framework, PolyFPGA, that allows in a completely automatic way to accelerate stencil computations. The framework focuses on the Iterative Stencil Loops (ISL), a type of scientific computation, and generates a streaming-based microarchitecture, known in literature as Streaming Stencil Time-step (SST), that can be synthesized on Field Programmable Gate Array. The SST-based architectures have shown interesting properties of scalability and data reuse, that permits it to be implemented using a low amount of resources. In order to obtain such architecture automatically, the framework leverages some of the mainstream Polyhedral tools, that are smoothly included, and also drives the synthesis using the Xilinx Vivado suite. The framework extends the methodology to generate SST already present in literature, addressing and solving some concrete problems that arise in the automatic generation of the architecture. It was built in a modular manner in order to allow it to target different FPGA boards and to be easily extended with new features and boards.

Molti problemi di natura scientifica possono essere risolti utilizzando algoritmi basati su stencil computations. Tra questi vi sono sistemi volti a studiare l’interazione tra particelle, algoritmi di computer vision e metodi di risoluzione per equazioni differenziali alle derivate parziali. Per questi motivi questo genere di algoritmi sono largamente studiati negli ambiti di ricerca. Il lavoro proposto introduce un framework, PolyFPGA, che permette l’accele- razione di algoritmi stencil in modo completamente automatico. Il framework si focalizza sull’analisi degli Iterative Stancil Loops (ISL), un particolare tipo di computazioni scientifiche, e genera una micro-architettura streaming conosciuta in letteratura come Stancil Streaming Time-step (SST) sintetizzabile su FPGA. Le architetture basate sugli SST hanno mostrato interessanti propriet di scalabilit e riuso di dati, che ne permettono l’implementazione utilizzando un basso numero di risorse. Al fine di ottenere quest’architettura in modo automatico, il framework utilizza alcuni tra i piu’ diffusi tool di analisi poliedrale, che include agevolmente, e guida la sintesi utilizzando il tool Vivado di Xilinx. PolyFPGA estende la metodologia gi presente in letteratura, riguardante la generazione automatica degli SST, affrontando e risolvendo vari problemi che sorgono durante la procedura automatica. costruito in maniera modulare permettendo cos utilizzo su diverse schede FPGA e in modo da permettere facilmente l’integrazione di nuove funzioni e schede.