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

Stiamo assistendo alla fine della legge di Moore, cosi 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 comunita 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 possibilita 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 piu 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, nonche 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, e 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 e capace di sfruttare il parallelismo sia all'interno che tra i timestep dell'algoritmo (ossia le iterazioni nel loop piu 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 proprieta 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 e 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 puo 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 puo 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 e davvero efficace, come anticipato, su reti di dimensione piccola, e pertanto non puo essere utilizzata su reti piu grandi e profonde, che sono invece il tipo di rete utilizzato maggiormente ai giorni nostri. L'approccio proposto e valutato su due casi di studio, una rete allenata sul dataset USPS (caratteri scritti a mano dal servizio postale USA), e la piu 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 e in grando di sfruttare parallelismi a differenti livelli. Ad esempio, puo processare piu feature map di input contemporaneamente, o produrre piu 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 possibilita di sfruttare un parallelismo piu 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 e 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 e 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.