Bombyx: Compilazione OpenCilk per l'Accelerazione Hardware FPGA

Informazioni Fondamentali

• ID Articolo: 2511.21346
• Titolo: Bombyx: OpenCilk Compilation for FPGA Hardware Acceleration
• Autori: Mohamed Shahawy, Julien de Castelnau, Paolo Ienne (École Polytechnique Fédérale de Lausanne)
• Classificazione: cs.AR (Architettura dei Calcolatori)
• Data di Pubblicazione: 26 novembre 2025 (preprint arXiv)
• Link Articolo: https://arxiv.org/abs/2511.21346

Riassunto

Questo articolo propone Bombyx, una toolchain che compila programmi OpenCilk in acceleratori hardware FPGA. Bombyx converte il modello di parallelismo implicito dei compiti di OpenCilk in una rappresentazione intermedia di trasmissione di continuazioni esplicita nello stile di Cilk-1, più adatta alle caratteristiche di streaming dell'FPGA. Lo strumento supporta molteplici target di compilazione: runtime compatibile con OpenCilk per la verifica, e generatori di unità di elaborazione sintetizzabili per strumenti di sintesi di alto livello come Vitis HLS. Inoltre, Bombyx introduce l'ottimizzazione Decoupled Access-Execution (DAE), che genera automaticamente unità di elaborazione ad alte prestazioni, migliorando la sovrapposizione memoria-calcolo e il throughput complessivo.

Contesto di Ricerca e Motivazione

1. Problema Centrale da Risolvere

Il parallelismo a livello di compiti (TLP) è una tecnica di parallelizzazione ampiamente utilizzata nel software, in grado di creare e pianificare dinamicamente compiti indipendenti a runtime. Sebbene esistano framework hardware (come ParallelXL e HardCilk) che supportano TLP su FPGA, manca uno strumento automatizzato per estrarre e compilare automaticamente il codice delle unità di elaborazione (PE) dai framework software TLP. I framework esistenti richiedono tipicamente agli utenti di fornire manualmente il codice PE, il che è sia tedioso che soggetto a errori.

2. Importanza del Problema

• Necessità di Automazione: Portare applicazioni TLP orientate alla CPU su FPGA richiede un lavoro manuale considerevole, inclusa la ristrutturazione del codice, l'adattamento delle interfacce hardware e la generazione di file di configurazione
• Ottimizzazione delle Prestazioni: Il codice scritto manualmente è difficile da sottoporre a ottimizzazioni hardware avanzate (come Decoupled Access-Execution)
• Efficienza dello Sviluppo: L'assenza di una toolchain automatizzata ostacola l'adozione diffusa di TLP nell'accelerazione FPGA

3. Limitazioni degli Approcci Esistenti

• Modello Implicito di OpenCilk: L'utilizzo di cilk_spawn e cilk_sync nel modello fork-join richiede commutazione di contesto nei punti di sincronizzazione. L'implementazione della commutazione di contesto in hardware richiede il salvataggio dell'intero stato del circuito, il che non è direttamente supportato dagli attuali strumenti HLS e richiede ingegneria RTL sostanziale
• Rappresentazione Intermedia TAPIR: TAPIR, utilizzato da OpenCilk, impiega costrutti compilatori di basso livello, rendendo difficile generare codice C++ leggibile e vicino al codice originale per HLS
• Scrittura Manuale di PE: Richiede la gestione manuale di allineamento di chiusure, interfacce di buffer di scrittura, generazione di file di configurazione e altri dettagli tediosi

4. Motivazione della Ricerca

Il modello di trasmissione di continuazioni esplicito di Cilk-1 è più adatto all'implementazione hardware, poiché divide le funzioni nei punti di sincronizzazione in funzioni di terminazione (eseguite atomicamente, senza necessità di commutazione di contesto). Sebbene questo modello non sia sufficientemente intuitivo per la programmazione software (e sia stato quindi abbandonato nell'evoluzione di Cilk), è naturale per l'implementazione hardware. L'obiettivo di Bombyx è automatizzare la conversione da OpenCilk a TLP esplicito e generare PE hardware ottimizzati.

Contributi Fondamentali

1. Processo di Compilazione Automatizzato: Propone una toolchain di compilazione completa e automatizzata da OpenCilk a acceleratori hardware FPGA denominata Bombyx
2. Rappresentazione Intermedia Esplicita: Progetta IR implicita e esplicita basata su grafi di flusso di controllo, realizzando la conversione automatica dal modello fork-join al modello di trasmissione di continuazioni
3. Generazione di Codice Multi-Target:
   • Backend HardCilk: genera automaticamente codice C++ HLS sintetizzabile e file di configurazione
   • Livello di Simulazione Cilk-1: verifica la correttezza della conversione utilizzando il runtime OpenCilk
4. Ottimizzazione Decoupled Access-Execution: supporta l'ottimizzazione DAE tramite direttive di compilazione (pragma), separando accesso alla memoria e calcolo in compiti diversi, migliorando le prestazioni hardware
5. Verifica Sperimentale: Nei benchmark di attraversamento di grafi, l'ottimizzazione DAE realizza una riduzione del tempo di esecuzione del 26,5%

Dettagli del Metodo

Definizione del Compito

Input: Programmi C/C++ paralleli a livello di compiti scritti con OpenCilk (orientati alla CPU)
Output:

• Codice C++ HLS sintetizzabile (per la generazione di PE FPGA)
• File di configurazione del sistema HardCilk (formato JSON)
• O codice eseguibile nello stile Cilk-1 (per la verifica)

Vincoli:

• Il programma deve seguire il modello fork-join di OpenCilk
• Le dipendenze tra funzioni devono essere espresse esplicitamente tramite cilk_spawn e cilk_sync

Progettazione dell'Architettura Complessiva

Il processo di compilazione di Bombyx comprende tre fasi principali (vedi Figura 3):

Codice Sorgente OpenCilk → AST → IR Implicita → IR Esplicita → Generazione Codice
                            ↓              ↓          ↓
                        Frontend Clang  Ottimizzazione DAE  HardCilk/Cilk-1

1. Conversione da AST a IR Implicita

• Utilizza il frontend Clang di OpenCilk per generare l'albero di sintassi astratta
• Converte l'AST in una rappresentazione IR implicita espressa come grafo di flusso di controllo (CFG)
• Ogni funzione corrisponde a un CFG, contenente:
  • Un unico blocco di ingresso (senza archi in ingresso)
  • Uno o più blocchi di uscita (senza archi in uscita)
  • Blocchi di base composti da istruzioni C sequenziali, terminati da istruzioni di flusso di controllo

Perché non utilizzare TAPIR: TAPIR utilizza costrutti di basso livello (come nodi φ, alloca, ecc.), rendendo difficile generare codice C++ leggibile e vicino al codice originale. L'IR di Bombyx preserva la struttura del codice originale.

2. Conversione da IR Implicita a IR Esplicita

Questo è il passo di conversione centrale di Bombyx, che trasforma il modello di sincronizzazione implicito di OpenCilk nel modello di trasmissione di continuazioni esplicito di Cilk-1.

Concetti Chiave:

• Chiusura (Closure): Struttura dati che rappresenta un compito, contenente:
  • Parametri già pronti
  • Segnaposti in attesa di dipendenze
  • Puntatore di ritorno
• spawn_next: Crea un compito di continuazione in attesa di dipendenze
• send_argument: Scrive esplicitamente un parametro in una chiusura in attesa e notifica lo scheduler

Algoritmo di Conversione:

1. Partizione dei Percorsi: Attraversa il CFG, iniziando un nuovo percorso quando si incontra un blocco di terminazione della funzione (return) o un'operazione di sincronizzazione
   • Ogni percorso diventa una funzione di terminazione autocontenuta
   • Le aree grigie nella Figura 4(c) rappresentano due percorsi
2. Identificazione delle Dipendenze: Analizza le relazioni di dipendenza al confine della sincronizzazione
   • Identifica le variabili che devono essere utilizzate dopo la sincronizzazione (come x e y nella Figura 1)
   • Queste variabili devono essere archiviate esplicitamente nei campi della chiusura
3. Sostituzione di Parole Chiave:
   • Inserisce la dichiarazione di chiusura nella chiamata spawn
   • Sostituisce la sincronizzazione con una chiamata spawn_next alla funzione successiva
   • Modifica il valore di ritorno dello spawn per scrivere esplicitamente nei campi della chiusura
   • Preserva le istruzioni return, che possono essere successivamente convertite in send_argument

Esempio di Conversione (Figura 1 a Figura 2):

// Implicito (OpenCilk)
int x = cilk_spawn fib(n-1);
int y = cilk_spawn fib(n-2);
cilk_sync;
return x + y;

// Esplicito (Cilk-1)
cont int x, y;
spawn_next sum(k, ?x, ?y);  // Crea compito di continuazione
spawn fib(x, n-1);           // Scrive in segnaposto x
spawn fib(y, n-2);           // Scrive in segnaposto y
// Funzione termina, nessuna sincronizzazione necessaria

Generazione del Backend HardCilk

HardCilk è un generatore di architettura TLP FPGA open source, fornendo uno scheduler di work-stealing hardware. Bombyx automatizza la generazione di tutti i componenti richiesti da HardCilk:

1. Allineamento di Chiusure

• Aggiunge automaticamente padding per allineare le dimensioni delle chiusure a 128/256 bit
• Facilita l'implementazione hardware

2. Interfaccia di Buffer di Scrittura

• HardCilk utilizza un modulo di buffer di scrittura per gestire spawn_next e send_argument
• Bombyx inserisce automaticamente i metadati richiesti (tipo di compito, indirizzo di destinazione, ecc.)

3. Generazione di Configurazione JSON

Genera automaticamente file di descrizione del sistema tramite analisi statica, contenenti:

• Dimensioni delle chiusure
• Relazioni spawn/spawn_next/send_argument tra compiti
• Altri parametri di configurazione del sistema

Ottimizzazione Decoupled Access-Execution (DAE)

Motivazione

Nell'implementazione PE ingenua, la stessa unità è responsabile dell'avvio delle richieste di memoria e dell'esecuzione del calcolo, causando:

• Stalli di memoria che lasciano il PE inattivo
• Riduzione del throughput complessivo

Le pipeline tradizionali negli strumenti HLS (come Vitis) sono limitate:

• Non possono gestire i confini dei cicli con dipendenze di dati
• Lo scheduler statico non può determinare quando pianificare gli accessi alla memoria

Soluzione DAE

Sotto TLP, esprime accesso alla memoria ed esecuzione come compiti diversi:

• Compito di Accesso: Responsabile specificamente delle richieste di memoria
• Compito di Esecuzione: Gestisce la logica di calcolo
• Scheduler di Compiti: Coordina l'esecuzione, realizzando una pipeline elastica

Modalità di Implementazione

Tramite direttiva pragma per guidare il compilatore:

#PRAGMA BOMBYX DAE
struct node_t nd = *n;  // Operazione di accesso alla memoria
// Codice successivo diventa compito di esecuzione

Il compilatore automaticamente:

1. Estrae la riga annotata in una funzione indipendente (compito di accesso)
2. La sostituisce con una chiamata spawn
3. Inserisce una sincronizzazione
4. Dopo la conversione a forma esplicita, il compito di accesso genera il compito di esecuzione di continuazione

Configurazione Sperimentale

Benchmark

Programma di Attraversamento di Grafi (Figura 5):

• Attraversamento parallelo in ampiezza di grafi
• Accesso a liste di adiacenza dei nodi (intensivo in memoria)
• Accesso ricorsivo parallelo ai nodi adiacenti

Dataset

Grafi ad albero generati sinteticamente:

• Grafo 1: Profondità D=7, fattore di ramificazione B=4, totale 5.461 nodi
• Grafo 2: Profondità D=9, fattore di ramificazione B=4, totale 87.381 nodi
• Calcolo del numero di nodi: $\frac{B^D - 1}{B - 1}$

Configurazione Sperimentale

• Piattaforma FPGA: Xilinx Alveo U55C (xcu55c-fsvh2892-2L-e)
• Strumento di Sintesi: Vivado 2024.1
• Frequenza Target: 300 MHz
• Numero di PE:
  • Non-DAE: 1 PE
  • DAE: 3 PE (spawner, executor, access uno ciascuno)

Metriche di Valutazione

1. Tempo di Esecuzione: Tempo necessario per attraversare l'intero grafo
2. Utilizzo delle Risorse:
   • LUT (Look-Up Tables)
   • FF (Flip-Flops)
   • BRAM (Block RAM)

Risultati Sperimentali

Risultati Principali di Prestazioni

• Riduzione del Tempo di Esecuzione: L'ottimizzazione DAE realizza un miglioramento delle prestazioni del 26,5%
• Tramite il disaccoppiamento di accesso alla memoria ed esecuzione, migliora la sovrapposizione memoria-calcolo

Analisi dell'Utilizzo delle Risorse

Overhead di Risorse:

• Aumento LUT del 47% (2.657 → 3.896)
• Aumento FF del 50% (2.305 → 3.464)
• BRAM raddoppiato (2 → 4)

Scoperte Sperimentali

1. Compromesso Prestazioni-Risorse: Il miglioramento delle prestazioni del 26,5% comporta un overhead di risorse di circa il 50%, il che rappresenta un compromesso ragionevole per applicazioni intensive in memoria
2. Analisi della Dimensione del PE:
   • Spawner + Executor ≈ dimensione del singolo PE Non-DAE
   • Il compito di accesso consuma risorse aggiuntive
   • Raccomandazione: l'utilizzo di PE di parallelismo dati implementati in RTL può ammortizzare il costo del compito di accesso
3. Potenziale di Ottimizzazione: L'articolo indica che in futuro il compito di accesso potrebbe essere integrato come primitiva black-box, piuttosto che generato utilizzando HLS

Lavori Correlati

Framework Software TLP

1. Intel Thread Building Blocks (TBB): Libreria di parallelismo a livello di compiti ampiamente utilizzata nell'industria
2. Cilk Plus: Estensione Cilk di Intel
3. OpenCilk: Framework Cilk più recente, con prestazioni superiori ai framework precedenti

Framework Hardware TLP

1. ParallelXL: Framework architetturale TLP iniziale su FPGA
2. HardCilk: Piattaforma target di Bombyx, sistema TLP FPGA open source che fornisce uno scheduler di work-stealing hardware

Evoluzione di Cilk

1. Cilk-1: Versione iniziale che adotta il modello di trasmissione di continuazioni esplicito
2. Versioni Successive: Passaggio al modello fork-join implicito (più adatto alla programmazione software)
3. Fondamenti Teorici: È stato provato che qualsiasi programma implicito può essere convertito a forma esplicita

Vantaggi di Questo Articolo

• Primo Strumento Automatizzato: Processo completamente automatizzato da OpenCilk a PE FPGA
• Conversione Esplicita: Sfrutta lo stile Cilk-1 per evitare la commutazione di contesto hardware
• Supporto per Ottimizzazioni: Integra ottimizzazioni specifiche dell'hardware come DAE

Conclusioni e Discussione

Conclusioni Principali

1. Bombyx realizza con successo un processo di compilazione automatizzato da OpenCilk a hardware FPGA
2. Il modello di trasmissione di continuazioni esplicito è adatto alle caratteristiche di streaming dell'FPGA, evitando la commutazione di contesto costosa
3. L'ottimizzazione DAE realizza un miglioramento delle prestazioni del 26,5% nei benchmark di attraversamento di grafi
4. Lo strumento è estensibile ad altri framework hardware TLP

Limitazioni

1. L'Ottimizzazione DAE Richiede Guida Manuale: Attualmente richiede ai programmatori di inserire pragma, senza implementare un'automazione completa
2. Valutazione Limitata:
   • Valutazione su un singolo benchmark (attraversamento di grafi)
   • Mancanza di confronti con altri metodi (come codice scritto manualmente, altri compilatori)
   • Mancanza di test su scenari di applicazione più diversificati
3. Overhead di Risorse: L'ottimizzazione DAE comporta un aumento di risorse di circa il 50%, che potrebbe limitare sistemi su larga scala
4. Implementazione del Compito di Accesso: L'utilizzo di HLS per generare PE di accesso non è efficiente; si consiglia RTL ma non è stato implementato
5. Maturità dello Strumento: Come prototipo di ricerca, manca di gestione completa degli errori e supporto per casi limite

Direzioni Future

1. Identificazione Automatica di DAE: Sviluppare analisi del compilatore per identificare automaticamente modelli di codice adatti all'ottimizzazione DAE
2. Unità di Accesso RTL: Integrare unità di accesso alla memoria di parallelismo dati implementate in RTL ad alta efficienza
3. Più Ottimizzazioni: Esplorare ulteriori ottimizzazioni specifiche dell'hardware (come riutilizzo di dati, ottimizzazione della località)
4. Estensione dei Target: Supportare più framework hardware TLP e strumenti HLS
5. Valutazione Completa: Valutare su più benchmark, incluse diverse tipologie di applicazioni TLP

Valutazione Approfondita

Punti di Forza

1. Innovazione del Metodo

• Strategia di Conversione Unica: Sfrutta ingegnosamente il modello di trasmissione di continuazioni esplicito di Cilk-1 per risolvere il difficile problema della commutazione di contesto hardware
• Valore dell'Automazione: Realizza per la prima volta una toolchain completamente automatizzata da OpenCilk a FPGA, colmando un importante vuoto
• Progettazione dell'IR Ragionevole: La progettazione dell'IR che preserva la struttura del codice originale rende il codice HLS generato più leggibile

2. Contributi di Ingegneria

• Forte Praticità: Automatizza la gestione di dettagli tediosi come allineamento di chiusure, interfacce di buffer di scrittura, generazione di file di configurazione
• Verificabilità: Fornisce un livello di simulazione Cilk-1 per verificare la correttezza della conversione, aumentando l'affidabilità dello strumento
• Favorevole all'Open Source: Il target HardCilk è un sistema open source, favorendo la diffusione dello strumento

3. Intuizioni Tecniche

• Cooperazione Hardware-Software: Comprensione profonda dei problemi di adattamento tra modelli TLP software e implementazione hardware
• Ottimizzazione DAE: Combina l'ottimizzazione hardware classica con TLP, dimostrando il potenziale dell'ottimizzazione guidata dal compilatore

4. Chiarezza della Presentazione

• Dimostra chiaramente la conversione da implicito a esplicito tramite l'esempio di Fibonacci
• Il confronto dell'IR nella Figura 4 è intuitivo e facile da comprendere
• Il diagramma del flusso di compilazione è chiaro

Insufficienze

1. Esperimenti Insufficienti

• Benchmark Singolo: Valutazione solo su attraversamento di grafi, impossibile verificare completamente l'universalità dello strumento
• Mancanza di Confronti: Nessun confronto con codice scritto manualmente, altri metodi di compilazione
• Scala Limitata: Grafi di test relativamente piccoli (massimo 87K nodi)
• Analisi delle Prestazioni Non Approfondita: Non analizza le fonti specifiche del miglioramento delle prestazioni (utilizzo della larghezza di banda, efficienza della pianificazione dei compiti, ecc.)

2. Limitazioni del Metodo

• DAE Semi-Automatica: Richiede pragma manuale, limitando l'usabilità
• Spazio di Ottimizzazione Limitato: Dimostra solo un'ottimizzazione (DAE), senza esplorare altre ottimizzazioni hardware
• Overhead di Risorse Significativo: L'aumento di risorse del 50% potrebbe limitare le applicazioni pratiche

3. Dettagli Tecnici Mancanti

• Algoritmo di Conversione Incompleto: Non spiega in dettaglio algoritmi critici come analisi delle dipendenze, selezione dei campi di chiusura
• Garanzie di Correttezza: Nessuna prova formale o metodo di verifica sistematica
• Casi Limite: Non discute la gestione di ricorsione, puntatori, strutture dati complesse

4. Profondità della Valutazione

• Scalabilità Sconosciuta: Nessun test su applicazioni su larga scala o flussi di controllo complessi
• Universalità Dubbia: L'attraversamento di grafi rappresenta applicazioni TLP tipiche?
• Divario dalla Teoria: Il miglioramento del 26,5% è vicino al limite teorico?

Impatto

1. Contributo al Campo

• Colma il Vuoto della Toolchain: Fornisce infrastruttura importante per l'applicazione di TLP su FPGA
• Ispira Ricerche Successive: L'approccio di conversione esplicita può essere applicato ad altri modelli di parallelismo
• Promuove TLP Hardware: Riduce le barriere di ingresso, aiutando la diffusione di TLP nell'accelerazione FPGA

2. Valore Pratico

• Praticità Media: Ha valore diretto per gli utenti di HardCilk, ma richiede ulteriore maturazione
• Costo di Apprendimento: Richiede ancora la comprensione dei concetti TLP e dei vincoli hardware
• Prontezza per la Produzione: Come prototipo di ricerca, è lontano dall'uso in produzione

3. Riproducibilità

• Media: Dipende da una toolchain di strumenti (OpenCilk, HardCilk, Vitis HLS, ecc.)
• Codice Non Open Source: L'articolo non menziona piani di open source del codice
• Dettagli Sperimentali Sufficienti: Fornisce dettagli di implementazione e sperimentazione adeguati

Scenari Applicabili

Scenari Adatti

1. Applicazioni di Parallelismo Dinamico di Compiti: Algoritmi su grafi, attraversamento di alberi, programmazione dinamica
2. Calcolo Intensivo in Memoria: L'ottimizzazione DAE è particolarmente adatta ad applicazioni con collo di bottiglia di accesso alla memoria
3. Utenti di HardCilk: Sviluppatori che già utilizzano o pianificano di utilizzare HardCilk
4. Prototipazione Rapida: Necessità di portare rapidamente codice TLP da CPU a FPGA

Scenari Non Adatti

1. Parallelismo Regolare: Parallelismo dati, pipeline e altri scenari che non richiedono pianificazione dinamica
2. Risorse Limitate: L'overhead di risorse del 50% potrebbe non essere accettabile
3. Prestazioni Estreme: Il codice RTL ottimizzato manualmente potrebbe comunque essere superiore
4. Modelli di Memoria Complessi: Il supporto dello strumento per puntatori complessi e memoria dinamica è sconosciuto

Raccomandazioni di Miglioramento

1. Estendere la Valutazione: Aggiungere più benchmark (ordinamento, ricerca, calcolo scientifico, ecc.)
2. Confronti di Prestazioni: Confrontare con codice HLS scritto manualmente, implementazioni CPU, implementazioni GPU
3. Automazione DAE: Sviluppare analisi del compilatore per identificare automaticamente opportunità di DAE
4. Diversità di Ottimizzazioni: Esplorare più ottimizzazioni hardware (riutilizzo di dati, cache locale, ecc.)
5. Verifica Formale: Fornire garanzie formali sulla correttezza della conversione
6. Rilascio Open Source: Rilasciare lo strumento come open source per promuovere il contributo della comunità e la verifica

Bibliografia

Letteratura chiave citata in questo articolo:

1. 2 OpenCilk (PPoPP'23): Framework Cilk più recente, linguaggio di input di Bombyx
2. 4 HardCilk (FCCM'24): Piattaforma target di Bombyx, lavoro precedente degli autori
3. 5 Cilk-1 (SIGPLAN'95): Sistema TLP classico di trasmissione di continuazioni esplicita, fondamento teorico di Bombyx
4. 6 Tesi di Dottorato di Joerg (1996): Prova la fattibilità teorica della conversione da implicito a esplicito

Valutazione Complessiva: Bombyx è un lavoro di ricerca di valore, che colma il vuoto di una toolchain automatizzata da OpenCilk a accelerazione hardware FPGA. La sua innovazione centrale consiste nello sfruttare il modello di trasmissione di continuazioni esplicito di Cilk-1 per evitare la commutazione di contesto hardware, fornendo un processo di compilazione completo. Tuttavia, come lavoro iniziale, l'articolo presenta evidenti insufficienze nella larghezza e profondità della valutazione sperimentale, e la semi-automazione dell'ottimizzazione DAE limita l'usabilità. Lo strumento ha valore diretto per gli utenti di HardCilk e i ricercatori di TLP, ma richiede ulteriore maturazione per un'applicazione diffusa. Si raccomanda che i lavori successivi si concentrino sull'identificazione automatica di ottimizzazioni, sull'estensione della valutazione dei benchmark e sul rilascio open source per promuovere la verifica e il miglioramento della comunità.