Extension of ACETONE C code generator for multi-core architectures

Questo lavoro presenta un'estensione del generatore di codice C ACETONE, originariamente limitato all'esecuzione sequenziale, per abilitare la generazione di codice parallelo ottimizzato per architetture multi-core, definendo formalmente il problema dell'assegnazione dei processori e pianificando l'implementazione di euristiche di scheduling e meccanismi di sincronizzazione.

L'essenziale

Ecco una spiegazione semplice e creativa del paper, pensata per chiunque, anche senza conoscenze tecniche di informatica.

🚀 Il Problema: Un Solo Chef in una Cucina Affollata

Immagina di dover preparare un pasto complesso (un'intelligenza artificiale) per un aereo. Questo pasto deve essere cucinato in modo perfetto e prevedibile: non puoi permetterti che il cibo arrivi in ritardo o che la ricetta cambi da un giorno all'altro, perché la sicurezza dei passeggeri dipende da questo.

Fino a poco tempo fa, il sistema ACETONE (il "cuoco" del progetto) era bravissimo a scrivere le ricette per cucinare questo pasto su un unico fornello (un processore singolo). Funzionava bene, ma era lento. Se il pasto era troppo grande, il fornello singolo non faceva in tempo a cucinarlo prima che l'aereo avesse bisogno di prendere una decisione (ad esempio, atterrare).

Ora, però, le cucine moderne (i computer degli aerei) hanno molti fornelli (processori multi-core). Il problema? Se provi a usare tutti i fornelli con una ricetta pensata per uno solo, i cuochi si urtano, si passano gli ingredienti a caso e il caos regna sovrano.

💡 La Soluzione: Dividere il Lavoro in Squadre

Gli autori di questo studio hanno detto: "E se trasformassimo questa ricetta in un piano di lavoro per una squadra?".

Hanno esteso ACETONE per generare codice che può essere eseguito su più processori contemporaneamente. Ma come fanno a non creare confusione?

1. La Mappa del Tesoro (Il DAG)

Immagina che la ricetta non sia una lista di istruzioni, ma una mappa del tesoro con frecce che indicano l'ordine.

• Alcuni passaggi devono essere fatti prima (es. sbucciare le patate).
• Altri possono essere fatti in parallelo (es. mentre uno sbuccia, un altro taglia la carne).
• Alcuni passaggi dipendono da altri (non puoi cuocere la pasta se non hai prima bollito l'acqua).

Il sistema trasforma la rete neurale in questa mappa. Il compito principale è decidere chi fa cosa e quando, in modo che tutto finisca nel minor tempo possibile.

2. Il Capo Cantiere (L'Algoritmo di Scheduling)

Per organizzare i lavori, usano un "capo cantiere" intelligente. Questo capo deve:

• Assegnare i compiti ai vari fornelli (core).
• Evitare che due fornelli cerchino di usare lo stesso ingrediente nello stesso momento.
• Decidere se è utile duplicare un compito (es. se un fornello è libero, gli fai preparare due volte lo stesso ingrediente per non fargli aspettare l'altro fornello).

Hanno testato due metodi per trovare il miglior piano:

• Metodo "Fai presto" (ISH): Assegna i compiti al primo fornello libero. È velocissimo da calcolare, ma a volte non è il piano perfetto.
• Metodo "Fai perfetto" (DSH): Cerca di ottimizzare ogni singolo minuto, duplicando i compiti se serve per evitare attese. È più lento da calcolare, ma spesso dà risultati migliori.

3. Il Sistema di Segnalazione (Sincronizzazione)

Questa è la parte più delicata. Quando il Fornello A finisce un compito e deve passare un ingrediente al Fornello B, come fanno a sapere che è pronto?
Non possono urlare o correre. Usano un sistema di bandierine e cassette postali nella memoria condivisa:

• Il Fornello A scrive il dato in una "cassetta" comune e alza una bandierina rossa.
• Il Fornello B guarda la bandierina. Se è rossa, sa che può prendere il dato, lo copia nella sua ciotola e abbassa la bandierina.
• Se la bandierina è verde, il Fornello B aspetta pazientemente.

Questo garantisce che nessuno prenda un ingrediente non ancora pronto o che due cuochi scrivano sulla stessa lavagna contemporaneamente.

📊 I Risultati: Funziona davvero?

Hanno provato tutto su un vero computer (un chip Texas Instruments) e hanno scoperto che:

1. Risparmio di tempo: Usare più fornelli ha ridotto il tempo totale di esecuzione di circa l'8%. Non sembra tantissimo, ma in un aereo ogni millisecondo conta.
2. La parte difficile: Il guadagno maggiore (fino al 31-46%) si ottiene nella parte centrale della ricetta, dove i compiti sono più facili da dividere. La parte iniziale e finale (come "accendere il forno" o "servire il piatto") deve essere fatta da un solo cuoco, quindi limita il risparmio totale.
3. Sicurezza: Il sistema è stato testato per garantire che il tempo massimo di esecuzione (WCET) sia sempre prevedibile. Questo è fondamentale per la certificazione aeronautica: devi sapere esattamente quanto tempo ci vorrà, anche nel caso peggiore.

🎯 In Sintesi

Hanno preso un sistema che cucinava su un solo fornello e l'hanno trasformato in un orchestra di cuochi coordinati.

• Prima: Un solo chef lavorava di fretta su un unico piano.
• Ora: Molti chef lavorano insieme, si passano gli ingredienti con delle bandierine colorate e seguono una mappa precisa.

Il risultato? Un'intelligenza artificiale più veloce, sicura e pronta per i futuri aerei, senza bisogno di costose macchine speciali, ma sfruttando al meglio i computer che abbiamo già. È come trasformare una gara di corsa in solitaria in una staffetta perfetta: il team arriva prima, ma solo se si passa il testimone al momento giusto! 🏁✈️

Sommario tecnico

Ecco una sintesi tecnica dettagliata del paper in italiano, strutturata secondo le sezioni richieste.

Titolo: Estensione del generatore di codice C ACETONE per architetture multi-core

1. Problema

L'integrazione di Reti Neurali Profonde (DNN) in sistemi aerospaziali critici per la sicurezza presenta sfide significative, principalmente legate alla necessità di alta prevedibilità e al rispetto di rigorosi standard di certificazione (es. linee guida EASA, bozza ED-324).
Il framework esistente ACETONE è in grado di generare codice C certificabile e prevedibile per sistemi a singolo core, preservando la semantica del modello e permettendo l'analisi del Worst-Case Execution Time (WCET). Tuttavia, l'industria aerospaziale sta migrando verso architetture multi-core per gestire modelli più complessi o vincoli temporali più stretti, senza ancora disporre di acceleratori dedicati.
Il problema centrale affrontato è come estendere ACETONE per generare codice C parallelo ed efficiente su CPU multi-core, mantenendo le proprietà di prevedibilità e certificazione, senza introdurre complessità di sincronizzazione ingestibili o tempi di esecuzione non deterministici.

2. Metodologia

Gli autori propongono un'estensione di ACETONE che tratta l'inferenza della DNN come un problema di scheduling su grafo aciclico diretto (DAG). La metodologia si articola in tre fasi principali:

• Modellazione:

  • Piattaforma: CPU multi-core omogenea con memoria condivisa (UMA). Si assume che il WCET di un task sia indipendente dal core su cui viene eseguito, ma si introduce un margine per gestire le interferenze sulla memoria.
  • Applicazione: La DNN è modellata come un DAG dove i nodi sono i layer della rete e gli archi rappresentano le dipendenze dei dati. Ogni nodo ha un WCET stimato e ogni arco ha un costo di latenza di comunicazione.
  • Vincoli: Lo scheduling è statico (offline), non preemptive e deve rispettare le dipendenze dei dati. È consentita la duplicazione dei task (esecuzione dello stesso layer su più core) per eliminare i tempi di comunicazione, ma solo se vantaggiosa.

• Algoritmi di Scheduling:

  • Programmazione a Vincoli (ILP): Gli autori hanno riformulato il problema di ottimizzazione lineare intera (ILP) proposto da Tang et al., riducendo drasticamente il numero di variabili decisionali e semplificando i vincoli di comunicazione. Questa nuova codifica permette di trovare soluzioni ottimali per grafi di dimensioni gestibili.
  • Euristiche: Per grafi più grandi o per tempi di calcolo ridotti, vengono implementate due euristiche basate su "Critical Path":
    1. ISH (Insertion Scheduling Heuristic): Assegna i task al core che minimizza il tempo di inizio, cercando di riempire i tempi morti (idle time) con task pronti.
    2. DSH (Duplication Scheduling Heuristic): Oltre a ISH, tenta di duplicare i task genitori (o i loro genitori) sui core di destinazione per ridurre la latenza di comunicazione, migliorando il makespan (tempo totale di completamento).

• Generazione del Codice e Sincronizzazione:

  • ACETONE viene esteso per generare funzioni di inferenza separate per ogni core.
  • Per la comunicazione tra core (bare-metal), viene implementato un meccanismo di sincronizzazione basato su flag e array condivisi in memoria.
  • Vengono introdotti operatori di Scrittura (Writing) e Lettura (Reading) che gestiscono l'attesa dei flag, la copia dei dati e l'aggiornamento degli indicatori di stato, garantendo la coerenza dei dati e l'ordine di esecuzione.

3. Contributi Chiave

1. Formalizzazione del problema: Definizione dello scheduling offline per DNN su sistemi multi-core omogenei come un problema di scheduling DAG con duplicazione di task.
2. Ottimizzazione dell'ILP: Sviluppo di una codifica più efficiente rispetto allo stato dell'arte (Tang et al.), riducendo la complessità computazionale e permettendo la risoluzione di istanze più grandi.
3. Estensione di ACETONE: Integrazione completa nel framework ACETONE che include:
   • Il mappaggio dei layer sui core.
   • La generazione automatica di codice C parallelo con operatori di sincronizzazione specifici per la piattaforma target.
4. Validazione Rigorosa: Valutazione sia tramite analisi statica del WCET (strumento OTAWA) che tramite misurazioni sperimentali su hardware reale.

4. Risultati

• Valutazione degli Algoritmi:
  • Le euristiche DSH offrono uno speedup superiore (più vicino all'ottimo) rispetto a ISH, ma richiedono tempi di calcolo significativamente più lunghi (fino a 2 minuti per grafi complessi).
  • ISH è molto più veloce e stabile, offrendo soluzioni sub-ottimali ma pratiche.
  • L'approccio ILP ottimizzato riesce a trovare soluzioni dove la versione originale di Tang fallisce per timeout, ma rimane computazionalmente costoso per grafi molto grandi (>50 nodi).
• Performance di Sincronizzazione:
  • Il meccanismo di sincronizzazione basato su flag richiede un numero di variabili proporzionale a $m(m-1)$ (dove $m$ è il numero di core). Per configurazioni industriali tipiche (4 core), l'overhead è gestibile (24 variabili).
• Risultati Sperimentali (Hardware TI Keystone II):
  • Sull'architettura GoogLeNet testata su 4 core ARM Cortex-A15, si è ottenuto un guadagno globale del 8% nel tempo di esecuzione totale (da 2.90 a 2.68 miliardi di cicli).
  • Il guadagno è limitato dalla presenza di layer sequenziali critici (es. conv_1 e conv_2).
  • Tuttavia, nelle sezioni altamente parallelizzabili del modello (da maxpool_2 a inception_2/concat), il guadagno è stato del 46% in simulazione e del 31% nell'esperimento reale.
  • L'analisi del WCET mostra che l'interferenza sulla memoria condivisa è il principale fattore limitante, specialmente per i layer di input.

5. Significato e Impatto

Questo lavoro rappresenta un passo fondamentale verso l'adozione di DNN in sistemi aerospaziali critici su hardware multi-core. Dimostra che è possibile generare codice C certificabile e prevedibile per architetture parallele senza ricorrere ad acceleratori hardware dedicati (che spesso mancano di supporto per la certificazione).
La soluzione proposta bilancia efficacemente la complessità computazionale dello scheduling con le esigenze di prevedibilità temporale, fornendo un framework pratico per l'industria. I risultati confermano che, sebbene il parallelismo non elimini completamente i colli di bottiglia sequenziali, offre miglioramenti significativi per le parti parallele dei modelli, rendendo fattibile l'uso di reti più grandi o vincoli temporali più stretti.
Il lavoro apre la strada a future ricerche su architetture eterogenee (core diversi, acceleratori) e su metodi di parallelizzazione più avanzati.