Compiling OpenMP task graphs to parallel hardware: a static analysis and synthesis approach

Questa tesi presenta una metodologia e un'estensione della toolchain per la sintesi del parallelismo basato su task di OpenMP su acceleratori FPGA. Sebbene il modello parallelo for di OpenMP sia stato mappato con successo sull'hardware tramite tecniche di High-Level Synthesis (HLS), le applicazioni irregolari che si basano su #pragma omp task depend(...) continuano a rappresentare una sfida per la sintesi hardware, a causa della loro natura dinamica e orientata al flusso di dati. In questi casi, le dipendenze tra task vengono risolte a runtime, rendendo i programmi OpenMP standard incompatibili con la pianificazione statica e la sintesi hardware. Per affrontare questo problema, abbiamo esteso il tool di sintesi PandA Bambu per supportare le direttive OpenMP task con clausole depend, introducendo un approccio completamente statico all’analisi e alla schedulazione. In particolare, il metodo (1) rileva le regioni di task e le relative dipendenze tramite passaggi personalizzati in LLVM, (2) genera un grafo di dipendenze tra task (TDG) noto a compile-time a partire dal programma originale, e (3) integra questo TDG nella pipeline di sintesi di Bambu, consentendo la generazione di hardware dotato di un datapath dedicato e di un controllore distribuito implicito. In questo modo si elimina la necessità di una logica di schedulazione a runtime, permettendo all’hardware risultante di sfruttare il parallelismo a livello di task in maniera deterministica. Per valutare le potenzialità dell’approccio proposto, sono stati utilizzati due benchmark rappresentativi: la fattorizzazione LU sparsa, che evidenzia flussi di controllo irregolari e dipendenze annidate, e la classificazione di cifre MNIST, che sfrutta il parallelismo a livello di input durante le fasi di training e inferenza.

This thesis presents a methodology and toolchain extension to synthesize OpenMP task-based parallelism on FPGA accelerators. While OpenMP’s parallel for model has been successfully mapped to hardware using high-level synthesis (HLS), irregular applications that rely on #pragma omp task depend(...) remain challenging to synthesize due to their dynamic and data flow nature. In such cases, task dependencies are resolved at runtime, making vanilla OpenMP programs incompatible with static scheduling and hardware synthesis. To address this, we extend the PandA Bambu HLS tool to support OpenMP task constructs with depend clauses by introducing a fully static analysis and scheduling approach. Specifically, the method (1) detects task regions and their dependencies through custom LLVM passes, (2) generates a statically known task-dependency graph (TDG) from the original program, and (3) feeds this TDG into Bambu’s synthesis pipeline, enabling hardware generation with a dedicated datapath and an implicit distributed controller. This eliminates the need for runtime scheduling logic, allowing the resulting hardware to exploit task-level parallelism deterministically. To assess the capabilities of the proposed approach, two representative benchmarks were employed: Sparse LU Factorization, showcasing irregular control flow and nested dependencies, and MNIST digit classification, which leverages input-level parallelism during both training and inference phases.