On the role of polyhedral analysis in high performance reconfigurable hardware based computing systems

Recent years have seen dramatic improvements in High Level Synthesis (HLS) tools: from efficient translation of numeric algorithms to image processing algorithms, from stencil computations to neural networks, relevant application domains and industries are benefiting from research on compute and/or memory/-communications network. In order to systematically synthesize better circuits for specific programs and kernels, last decades’ studies focused on the development of sound, formal approaches; one notable such framework is the Polyhedral Model (PM) and the associated code analysis technique, collectively called Polyhedral Analysis (PA). Under this representation it is possible to compute dependencies, find loop bounds, and reorder instructions in a completely automated manner relying on the same set of sound and comprehensive assumptions of PM. We reconsider this rich state of the art, and elaborate on different methodologies and implement the related toolchains to generate highly parallel and power efficient kernels running on reconfigurable hardware, with the aim of distributing the workload on multiple computational blocks while maximizing the overall power efficiency of the resulting heterogeneous system. We approach this problem in three different, interrelated ways. First of all, we dedicated our early efforts to the development of an accelerator-rich platform where the focus is on the coordination of multiple custom and software processors, via a novel Domain Space Exploration (DSE) phase. Specifically, the work elaborates on two relevant aspects: the effectiveness of Partial Reconfiguration (PR) to attain improved energy delay and throughput metrics, and the effectiveness of the heuristics chosen to realize the DSE step, which feature both low complexity and good exploration times. To this matter, we devote Chapter 2. We also extended the scope of this work by assuming that multiple computing elements are in place, and an adequate communication architecture is required to coordinate those accelerators. This is discussed in Chapter 3. Secondly, we focus on amply data-parallel codes, and develop a novel High Level Synthesis (HLS) approach to using PM as a means to explicitly extract and isolate data and computation from affine codes in order to efficiently divide the workload among an arbitrary number of nodes, in the light of the current and foreseeable trend of adoption of reconfigurable hardware in the datacenter; towards energy proportional computing, we improve the current state of art in single core acceleration, as our methodology obtains near-linear speedup with the area at disposition to accelerate the given workload. To this subject, we devote Chapter 4 and 5. Lastly, we focus on a specific, and more restricted class of data parallel codes, namely Iterative Stencil Loop (ISL), as they play a crucial role in a variety of different fields of application. The computationally intensive nature of those algorithms created the need for solutions to efficiently implement them in order to save both execution time and energy. This, in combination with their regular structure, has justified their widespread study and the proposal of largely different approaches to their optimization. However, most of these works are focused on aggressive compile time optimization, cache locality optimization, and parallelism extraction for the multicore/multi processor domain, while fewer works are focused on the exploitation of custom architectures to further exploit the regular structure of ISLs, specifically with the goal of improving power efficiency. This work introduces a methodology to systematically design power efficient hardware accelerators for the optimal execution of ISLs algorithms on Field Programmable Gate Arrays (FPGAs). To this extensive methodology, we devote Chapter 6. As part of the methodology, we introduce the notion of Streaming Stencil Time-step (SST), a streaming-based architecture capable of achieving both low resource usage and efficient data reuse thanks to an optimal data buffering strategy; and we introduce a technique,called SSTs queuing, capable to deliver a quasi-linear execution time speedup with constant bandwidth. This is the core subject of Chapter 7. We validate all methodologies, approaches, and toolchains on significant benchmarks on either a Zynq-7000 or Virtex-7 FPGA using the Xilinx Vivado suite. Results, which are reported in each Chapter devoted to the respective subject, demonstrate how we are able to improve the efficiency of all the baselines we compare against; specifically, we improve the energy delay and throughput metric when using our accelerator-rich platform, and dramatically improve the on-chip memory resources usage using the PA-based methodologies, allowing us to treat problem sizes whose implementation would otherwise not be possible via direct synthesis of the original, unmanipulated HLS code. We finally conclude the dissertation in Chapter 8.

Durante gli ultimi anni gli strumenti di sintesi ad alto livello (High Level Synthesis (HLS)) hanno conosciuto notevoli miglioramenti: dalla traduzione efficiente di algoritmi numerici a quella degli algoritmi di elaborazione delle immagini, dai calcoli stencil alle reti neurali, disparati domini applicativi ed industrie stanno beneficiando della ricerca sulla sintesi di elementi di calcolo, sottosistemi di memoria, e reti di comunicazione. La ricerca degli ultimi decenni si é focalizzata sullo sviluppo di approcci formali e corretti finalizzati alla sistematica sintesi di circuiti più performanti per specifici programmi e nuclei computazionali complessi. In tale senso é di notevole interesse il Modello Poliedrale (Polyhedral Model (PM)) e la tecnica di analisi codice associata, cui ci si riferisce collettivamente con il termine Analisi Poliedrale (Polyhedral Analysis (PA)), descritta con dovizia di particolari nel capitolo 4. Tramite questa rappresentazione e manipolazione della computazione é possibile calcolare le dipendenze, i gli indici degli estremi delle iterazioni, riordinare le istruzioni in modo completamente automatizzato, ed altro ancora. In questa tesi riconsideriamo lo stato dell’arte ed i lavori relativi a quest’area di ricerca, elaborando metodologie innovative ed implementando le relative toolchain per generare hardware riconfigurabile, con l’obiettivo di distribuire il carico di lavoro su più blocchi di calcolo, massimizzando l’efficienza energetica complessiva di il sistema eterogeneo risultante. Approcciamo il problema in tre modi differenti. Prima di tutto, abbiamo sviluppato una piattaforma basata su acceleratori in cui l’attenzione é rivolta al coordinamento di più processori e software personalizzati, attraverso una fase di esplorazione dello spazio dei parametri (Domain Space Exploration (DSE)). Il lavoro approfondisce due aspetti rilevanti: primo, l’efficacia della riconfigurazione parziale (Partial Reconfiguration (PR)) per ottenere un miglioramento delle metriche prodotto energia-latenza e throughput; secondo, l’efficacia delle euristiche scelte per realizzare il passo DSE, di bassa complessità computazionale e con ottimi tempi di esecuzione. A questo lavoro dedichiamo il capitolo 2. Abbiamo anche ampliato la portata dello stesso assumendo che più elementi di calcolo siano presenti nel sistema, e sia necessario un’adeguata architettura di comunicazione al fine di coordinare tali acceleratori. Questo é discusso nel capitolo 3. Successivamente ci concentriamo sui codici affini ampiamente paralleli, e sviluppiamo un nuovo approccio alla sintesi ad alto livello (HLS) per utilizzare l’analisi poliedrale come un mezzo per estrarre ed isolare flusso dati e computazione, per poter dividere in modo efficiente il carico di lavoro tra un numero arbitrario di nodi alla luce della tendenza attuale e futura di adozione di hardware riconfigurabile nei centri di elaborazione dati; nell’ottica dei sistemi di calcolo energy proportional, miglioriamo l’attuale stato dell’arte in termini di accelerazione single core, come dimostra la metodologia descritta nel capitolo 5. Infine, ci concentriamo su una classe specifica e ristretta di cod- ici paralleli, gli iterative Stencil Loop (ISL), codici la cui computazione efficiente risulta cruciale in una varietà di campi di applicazione. La natura computazionalmente intensiva di questi algoritmi ha generato la necessità di disporre di metodi efficienti per la loro computazione al fine di risparmiare sia tempo che energia per la loro esecuzione. Questo, in combinazione con la loro struttura regolare, ha giustificato il loro ampio studio e la proposta di molteplici approcci per loro ottimizzazione. Tuttavia, la maggior parte di queste opere sono focalizzate sull’ottimizzazione statica aggressiva, l’ottimizzazione della località dei dati, e l’estrazione di parallelismo nel dominio multicore, mentre un minor numero di lavori sono focalizzati sullo sfruttamento di architetture riconfigurabili con l’obiettivo di migliorare l’efficienza energetica della computazione. Come parte della metodologia, si introduce il concetto di Streaming Stencil Time-step (SST), un’architettura basata sul modello dataflow in grado di coniugare tanto un basso utilizzo delle risorse quanto un riuso efficiente dei dati grazie ad una strategia ottimale di buffering dei dati; e si introduce una tecnica, chiamata accodamento di SST, in grado di fornire una riduzione del tempo di esecuzione in funzione del numero di elementi di calcolo presenti, con larghezza di banda off-chip costante, e incremento di efficienza energetica fino a saturazione del sistema di calcolo. I capitoli 6 e 7 introducono questa metodologia per la progettazione sistematica di acceleratori hardware efficienti per l’esecuzione ottimale di algoritmi ISL su Field Programmable Gate Array (FPGA) mediante SST. Convalidiamo ogni metodo, approccio, e toolchain su applicazioni di riferimento implementate su Zynq-7000 o Virtex-7 utilizzando la suite Xilinx Vivado. I risultati, che sono riportati in ogni capitolo dedicato al rispettivo argomento, dimostrano come siamo in grado di migliorare l’efficienza di tutte le soluzioni di base con cui ci confrontiamo; in particolare, miglioriamo il prodotto ritardo-energia ed il throughput quando utilizziamo la nostra piattaforma basata su acceleratori; miglioriamo sensibilmente l’utilizzo di risorse on-chip di memoria utilizzando le metodologie basate su PA, cosa che ci permette di trattare problemi dimensioni la cui attuazione sarebbe altrimenti non essere possibile via diretta sintesi del codice HLS manipolata originale; e siamo in grado di scalare la computazione basata su SST secondo modello teorico, cosa che massimizza l’efficienza energetica del sistema di calcolo risultante. Concludiamo la tesi col capitolo 8, in cui forniamo spunti per eventuali sviluppi futuri di queste linee di ricerca.