C-based high level synthesis of parallel applications targeting adaptive hardware components

The ever increasing complexity} of embedded systems is driving design methodologies towards the use of abstractions higher than the Register Transfer Level (RTL). In this scenario, High Level Synthesis (HLS) plays a significant role by enabling the automatic generation of custom hardware accelerators starting from high level descriptions (e.g., C code). Typical HLS tools exploit parallelism mostly at the Instruction Level (ILP). They statically schedule the input specifications, and build centralized Finite Stat Machine (FSM) controllers. However, the majority of applications have limited ILP and, usually, centralized approaches do not efficiently exploit coarser granularities, because FSMs are inherently serial. Novel HLS approaches are now looking at exploiting coarser parallelism, such as Task Level Parallelism (TLP). Early works in this direction adopted particular specification languages such as Petri nets or process networks, reducing their applicability and effectiveness in HLS. This work presents novel HLS methodologies for the efficient synthesis of C-based parallel specifications. In order to overcome the limitations of the FSM model, a parallel controller design is proposed, which allows multiple flows to run concurrently, and offers natural support for variable latency operations, such as memory accesses. The adaptive controller is composed of a set of interacting modules that independently manage the execution of an operation or a task. These modules check dependencies and resource constraints at runtime, allowing as soon as possible execution without the need of a static scheduling. The absence of a statically determined execution order has required the definition of novel synthesis algorithms, since most of the common HLS techniques require the definition of an operation schedule. The proposed algorithms have allowed the design and actual implementation of a complete HLS framework. The flow features automatic parallelism identification and exploitation, at different granularities. An analysis step, interfacing with a software compiler, processes the input specification and identifies concurrent operations or tasks. Their parallel execution is then enabled by the parallel controller architecture. Experimental results confirm the potentiality of the approach, reporting encouraging performance improvements against typical techniques, on a set of common HLS benchmarks. Nevertheless, the interaction with software compilers, while profitable for the optimization of the input code, may represent a limitation in parallelism exploitation: compilation techniques are often over-conservative, and in the presence of memory operations accessing shared resources, force serialization. To overcome this issue, this work considers the adoption of parallel programming paradigms, based on the insertion of pragma annotations in the source code. Annotations, such as OpenMP pragmas, directly expose TLP, and enable a more accurate dependences analysis. However, also in these settings, the concurrent access to shared memories among tasks, common in parallel applications, still represents a bottleneck for performance improvement. In addition, it requires concurrency and synchronization management to ensure correct execution. This work deals with such challenges through the definition of efficient memory controllers, which support distributed and multi-ported memories and allow concurrent access to the memory resources while managing concurrency and synchronization. Concurrency is managed avoiding, at runtime, multiple operations to target the same memory location. Synchronization is managed providing support for atomic memory operations, commonly adopted in parallel programming. These techniques have been evaluated on several parallel applications, instrumented through OpenMP pragmas, demonstrating their effectiveness: experimental results show valuable speed-ups, often close to linearity with respect to the degree of available parallelism.

La crescente complessità dei sistemi dedicati forza le metodologie di progetto ad adottare livelli di astrazione più alti dello RTL. In questo scenario, la sintesi ad alto livello (HLS) ricopre un ruolo significativo, consentendo la generazione automatica di acceleratori hardware a partire dalla loro descrizione comportamentale (attraverso l'utilizzo del linguaggio C). Tipicamente le metodologie di HLS sfruttano parallelismo a livello di istruzione, schedulando staticamente la specifica, e costruendo controllori progettati come Macchine a Stati Finit (FSM). Tuttavia lo ILP è limitato nella maggior parte delle applicazioni, e l'impiego di controllori centralizzati spesso limita lo sfruttamento del parallelismo ad una grana più grezza, essendo inerentemente seriali. Approcci pionieristici per lo sfruttamento del parallelismo a grana grezza hanno adottato linguaggi di specifica particolari, come reti di Petri o reti di processi, in questo modo riducendone la loro applicabilità. Questo lavoro di tesi presenta delle metodolofie innovative per la sintesi di specifiche parallele, descritte tramite linguaggio C. In particolare, propone il progetto di un controllore parallelo come alternativa a quello centralizzato, che consente l'esecuzione concorrente di diversi flussi di esecuzione, e offre supporto per la gestione di operazioni a latenza variabile come gli accessi a memoria. Il controllore proposto è composto da moduli interagenti che in modo indipendente gestiscono l'esecuizione di una o un gruppo di opoerazioni. Questi verificano dinamicamente il soddisfacimento di vincoli di dipendenza o strutturali, e non necessitano della definizione di un ordine di esecuzione. L'assenza di un ordinamento stattico delle operazioni, requisito per i comuni algoritmi di sintesi, ha richiesto la definizione di techiche innovative. Il loro progetto ha consentito l'implementazione di un flusso di HLS completo. Quest'ultimo consente l'identificazione e lo sfruttamento automatico del parallelismo, a diversi livelli di granularità. Un passo di analisi, interfacciandosi con un compilatore software, processa la specifica in input identificando operazioni e task potenzialmente concorrenti. La loro esecuzione parallela è supportata dall'architettura del controllore parallelo. Risultati sperimentali confermano le potenzialità dell'approccio, mostrando vantaggi in termini di performance su diversi benchmarck. Tuttavia, l'interazione con compilatori software, per quanto vantaggiosa nell'ottimizzazione del codice in input, spesso rappresenta una limitazione nello sfruttamento del parallelismo: molte tecniche di compilazione, infatti, sono spesso più che conservative, forzando la serializzazione di porzioni di codice in presenza di operazioni di memoria. Per superare questa limitazione, questo lavoro valuta l'adozione di paradigmi di programmazione parallela basati sull'annotazione del codice sorgente. Tali annotazioni, come pragma OpenMP, espongono in modo esplicito il parallelismo consentendo un'analisi delle dipendenze più accurata. Ciònondimeno, anche in queste condizioni, l'accesso concorrente alla memoria rappresenta ancora un collo di bottiglia per le prestazioni. Il presente lavoro affronta queste problematica definendo dei controllori di memoria efficienti, in grado di supportare memorie distribuite e consentire l'accesso parallelo alle risorse di memoria, allo stesso tempo gestendo concorrenza e sincronizzazione. La concorrenza è gestita evitando a tempo di esecuzione, che più operazioni indirizzino la stessa locazione di memoria. La sincronizzazione è gestita attraverso il supporto per le operazioni di memoria atomiche, adottate comunemente nella programmazione parallela. Queste tecniche sono state valutate sintetizzando diverse applicazioni parallele, annotate con pragma OpenMP: i risultati sperimentali hanno mostrato un aumento delle performance rilevante, spesso vicino alla linearità rispetto al grado di parallelismo disponibile.