On how to design optimized spatial architectures: from iterative stencils to convolutional neural networks

We are approaching the end of Moore's law and Dennard scaling, while demand for computing power increases constantly. Traditional processors are struggling to keep up with performance requirements, and both scientific research and industry are exploring reconfigurable architectures as an alternative. It is common knowledge that an increasing number of technology leaders, such as Microsoft, IBM, Intel, Google, Amazon to name a few, are currently exploring the employment of reconfigurable architectures as hardware accelerators. Fine grained inherent parallelism and low power consumption thanks to direct hardware execution are the key aspects that make reconfigurable architectures an attractive choice for High-Performance Computing (HPC). This thesis is focused on a set of algorithms sharing a similar computational pattern, namely iterative stencils and Convolutional Neural Networks (CNNs). The key computation for both algorithms consists in sliding a filter on the input data, computing new elements using a submatrix of the input. Iterative stencil algorithms are heavily employed in physics, numerical solvers and even finance, while CNNs are one of the recently developed deep learning algorithms, currently used in industry to perform image classification, analysis of video and even speech recognition and recommender systems. While High-Level Synthesis (HLS) capabilities have improved dramatically over the recent years, the synthesis tools have yet to reach the level of sophistication required to properly optimise these algorithms, and extract sufficient parallelism or generate highly scalable solution, or automate the acceleration creation and integration in a way that resembles the development experience that is in place for CPUs and GPUs. Indeed, the process of designing and deploying hardware accelerators for iterative stencils of CNNs is still a hard and complex task that requires expertise in FPGA programming and knowledge of hardware design tools. The complex dependencies that arise from the filtering conditions, the iterative nature of the algorihtms, and the low operational intensity, make current HLS solutions inadequate to really optimise the resulting implementations. This thesis objective is to improve with respect to the proposed solutions targeting all the presented challenges. For both the target algorithms, we designed optimized spatial architectures that are able to exploit different sources of parallelism of such algorithms, reduce the cost of data movements alleviating the burden on external memory and that can easily scale up to multi-FPGA systems. In particular, we propose spatial accelerators for iterative stencils, small CNNs and the features extraction stage of deep CNNs. The resulting designs, consisting of distributed architectures of independent elements communicating using read- and write-blocking FIFOs, can scale in size if enough resources are available, unfolding the algorithms computation in space. Such architectures can exploit different levels of parallelism offered by the target algorithms. Moreover, we address the scalability of the proposed solutions implementing the accelerators on very big Stacked Silicon Interconnect (SSI) FPGAs or even on custom-designed multi-FPGA systems. Finally, we provide automation flows and performance models that can automate completely or support the automation of the design process, starting from high-level specification of the algorithms, either being C/C++ for iterative stencils, or standard formats as the one implemented in Caffe for CNNs. The validation performed shows that for iterative stencils, the proposed solution is comparable with the state of the art for the single FPGA implementation, but we are able to perform substantially better on multi-FPGA, thanks to an approximately linear scaling in performance. Moreover, for deep CNNs our implementations for AlexNet and VGG-16 achieve a throughput of respectively 1.61 and 2.99 TOPS, where for VGG-16 we are the second-best implementation -- by a narrow margin -- available in the State of the Art, while for AlexNet we substantially outperform the previous work.

Stiamo assistendo alla fine della legge di Moore, così come del Dennard scaling, ma la richiesta di potenza computazionale continua inesorabilmente a crescere. I processori tradizionali fanno fatica a tenere il passo con i sempre maggiori requisiti prestazionali, e sia la comunità scientifica che quella industriale hanno cominciato ad investigare l'utilizzo di architetture riconfigurabili come alternativa. E' infatti di pubblico dominio il fatto che un crescente numero di leader tecnologici, come Microsoft, IBM, Intel, Google, Amazon, per citarne alcuni, stanno attivamente esplorando la possibilità di utilizzare architetture riconfigurabili come acceleratori hardware. Parallelismo granulare intrinseco e bassi consumi di potenza grazie alla esecuzione di algoritmi direttamente in hardware sono gli aspetti chiave che rendono le architetture riconfigurabili un valido candidato per l'utilizzo nel settore delle computazioni ad alte prestazioni (High-Performance Computing, o HPC). In questa tesi investighiamo l'utilizzo di architetture riconfigurabili, e nello specifico di FPGA, come forma di acceleratore. In particolare, questa tesi si focalizza su un insieme di algoritmi che condividono un pattern computazionale simile, e sono gli stencil iterativi, e le reti neurali convoluzionali (CNN). Il tipo ti computazione che li accomuna consiste nello scorrere un filtro sui dati di input, generando gli elementi di output a partire da una sottomatrice dell'input. Gli stencil iterativi sono lagramente usati in simulazioni di tipo fisico, in risolutori numerici, e persino in finanza, mentre le CNN sono uno tra i più popolari algoritmi di deep learning recentemente sviluppati, e sono correntemente utilizzate nell'industria per effettuare classificazione di immagini, analisi di video e persino riconoscimento vocale e sistemi di raccomandazione. Per entrambi, abbiamo disegnato architetture spaziali ottimizzate capaci di sfruttare differenti sorgenti di parallelismo di questi algoritmi, nonché di ridurre il costo del movimento dei dati alleviando il carico sulla memoria esterna, e che possono scalare facilmente su sistemi multi-FPGA. Inoltre, le soluzioni proposte condovidono la caratteristica comune di essere architetture distribuite costituite da moduli indipendenti che usano FIFO con letture e scritture bloccanti per comunicare. Nel Capitolo 1 discutiamo il contesto operativo, ossia il settore HPC e le relative sfide che emergono dal tentativo di evolvere le soluzioni correnti verso nuovi orizzonti prestazionali, introducendo i sistemi eterogenei, e in particolare le architetture riconfigurabili e le FPGA, come possibile mezzo per affrontare suddette sfide. Il capitolo che segue, ossia il Capitolo 2, è invece devoto alla definizione delle classi di algoritmi su cui questa tesi si focalizza, descrivendo prima gli stencil iterativi, e poi presentando l'architettura delle CNN, dettagliando i vari layer che le caratterizzano. Successivamente, nel Capitolo 3, proponiamo un template per realizzare un acceleratore dataflow per gli stencil iterativi che è capace di sfruttare il parallelismo sia all'interno che tra i timestep dell'algoritmo (ossia le iterazioni nel loop più esterno da cui prendono la denominazione di iterativi), tenendo allo stesso tempo bassi i requisiti di memoria sul chip. Nel capitolo analizziamo in maniera approfondita le proprietà dell'acceleratore, e per valutare come la soluzione proposta scala, implementiamo un sistema multi-FPGA da utilizzare come piattaforma di valutazione. Inoltre, proponiamo un flusso di automazione del design capace di generare l'acceleratore a partire da una sua specifica in C/C++. La valutazione effettuata mostra che siamo comparabili allo stato dell'arte sulla singola FPGA, ma siamo in grando di offrire prestazioni altamente superiori sul sistema multi-FPGA, grazie a un incremento prestazionale che è approssimativamente lineare con l'aumento della dimensione dell'acceleratore. Nel Capitolo 4 presentiamo un framework per l'implementazione dataflow automatica su FPGA di piccole CNN. Il framework si integra con il tool Caffe, uno standard nell'implementazione di CNN, e può essere usato per istanziare la rete implementata in locale tramite SDAccel o nel cloud usanto le istanze F1 di Amazon. L'acceleratore risultante realizza una pipeline ad alto livello tra i diversi layer della rete, il che garantisce un incremento prestazionale quando la CNN viene utilizzata per processare un insieme di input in contemporanea, invece che uno solo. Inoltre, la soluzione può scalare ogni layer da singola porta in input e output a totalmente parallelo, a seconda delle risorse a disposizione sul dispositivo riconfigurabile. Tuttavia, questa metodologia è davvero efficace, come anticipato, su reti di dimensione piccola, e pertanto non può essere utilizzata su reti più grandi e profonde, che sono invece il tipo di rete utilizzato maggiormente ai giorni nostri. L'approccio proposto è valutato su due casi di studio, una rete allenata sul dataset USPS (caratteri scritti a mano dal servizio postale USA), e la più famosa LeNet, e mostra che effettivamente il tempo medio per processare un'immagine cala all'aumentare del numero di immagini processate, e tende a convergere ad un valore fisso quando il numero di immagini diviene superiore al numero di layera della rete, che sono anche il numero di stadi della pipeline reaizzata. In ultimo, nel Capitolo 5 proponiamo una metodologia per implementare su FPGA la parte di estrazione di feature di CNN profonde. L'acceleratore risultante è in grando di sfruttare parallelismi a differenti livelli. Ad esempio, può processare più feature map di input contemporaneamente, o produrre più output feature map in parallelo, nel singolo layer, o creare una pipeline tra i differenti layer della rete. Al fine di sfruttare i DSP della FPGA in modo efficiente, abbiamo elaborato una tecnica di time-sharing che consente di computare ogni convoluzione utilizzando un solo DSP, e per la quale la maggior parte dei dati fluiscono a un sottomultiplo della frequenza, risultando nella possibilità di sfruttare un parallelismo più elevato nell'acceleratore, e raggiungere una elevata efficienza energetica e bassi requisiti di banda esterna. Inoltre, forniamo anche un semplice modello di prestazioni per assistere il processo di design e permettere di stimare le prestazioni ottenibili con buona accuratezza. La metodologia proposta è validata su due popolari CNN, AlexNet e VGG-16, e le implementazioni migliori per entrambe raggiungono un throughput rispettivamente di 1.61 e 2.99 TOPS (Tera Operations Per Second). Nel caso di VGG-16 questo risultato è il secondo rispetto allo stato dell'arte, ma si avvicina al primo con un margine molto ristretto, mentre nel caso di AlexNet siamo in grado di avere prestazioni decisamente superiori ai lavori precedenti.