Machine Learning-Based Graph Simplification for Symbolic Accelerators

Riepilogo Tecnico: Semplificazione di Grafi Basata su Machine Learning per Acceleratori Simbolici

Enunciato del Problema
Gli acceleratori basati su grafi, in particolare quelli che utilizzano Automi Finiti Non Deterministici (NFA) per l'elaborazione di dati simbolici (ad esempio, genomica, cybersecurity, NLP), affrontano significativi colli di bottiglia in termini di scalabilità ed efficienza. Sistemi come NAPOLY+, che mappano automi direttamente sull'hardware FPGA, soffrono di un eccessivo consumo di memoria, congestione del routing e calcolo ridondante quando gestiscono grafi grandi e complessi. L'ottimizzazione hardware tradizionale spesso assume un grafo di input fisso, non riuscendo ad affrontare la ridondanza intrinseca presente nei carichi di lavoro simbolici reali, come stati irraggiungibili, destinazioni logiche duplicate e transizioni a basso impatto. Inoltre, le tecniche esistenti di riduzione dei grafi si basano spesso su euristiche statiche che ignorano la natura probabilistica dei carichi di lavoro e le specifiche semantica di punteggio richieste dagli acceleratori moderni.

Metodologia: Il Framework AutoSlim
Gli autori propongono AutoSlim, un framework basato su machine learning progettato per potare i grafi degli automi durante la fase di pre-elaborazione, prima del dispiegamento hardware. La metodologia opera attraverso la seguente pipeline:

1. Generazione e Annotazione dei Dati: Un generatore di dataset di grafi simbolici crea grafi di automi compatibili con il formato di overlay NAPOLY+. Questi grafi sono annotati con metriche di punteggio (frequenza degli archi, costo di transizione, centralità dei nodi) e codificati in XML, quindi convertiti in CSV per l'estrazione delle caratteristiche.
2. Estrazione delle Caratteristiche e Classificazione: AutoSlim estrae caratteristiche strutturali e comportamentali dal grafo, utilizzando principalmente i punteggi degli archi. Impiega un classificatore Random Forest per prevedere l'utilità di ogni transizione.
3. Pipeline di Potatura: Il classificatore identifica e rimuove nodi e archi a basso impatto (ad esempio, stati irraggiungibili o percorsi ridondanti semanticamente equivalenti) preservando al contempo le semantica funzionali dell'automato. Crucialmente, il framework è progettato per mantenere le proprietà "consapevoli del punteggio" di NAPOLY+, garantendo che la logica del percorso a costo minimo richiesta per le applicazioni basate sul ranking rimanga intatta.
4. Verifica e Dispersione: Una fase di verifica garantisce l'equivalenza funzionale dopo la potatura. I grafi semplificati risultanti vengono convertiti in vettori di configurazione compatibili con l'hardware e dispiegati su architetture FPGA (specificamente Xilinx Zynq UltraScale+).

Contributi Chiave

• Potatura Guidata dai Dati: A differenza dei metodi tradizionali basati su regole statiche, AutoSlim utilizza un approccio di apprendimento supervisionato (Random Forest) per generalizzare attraverso domini e carichi di lavoro, identificando la ridondanza basata sulla significatività statistica piuttosto che su regole strutturali fisse.
• Ottimizzazione Consapevole dell'Hardware: Il framework è esplicitamente progettato per integrarsi con il modello di matching basato sul punteggio di NAPOLY+, affrontando i vincoli specifici delle risorse (BRAM, routing, elementi logici) degli overlay FPGA.
• Scalabilità: Lo strumento è progettato per gestire grafi con decine di migliaia di nodi, colmando il divario di scalabilità lasciato da studi precedenti che si concentravano su benchmark sintetici più piccoli.
• Doppia Utilità: Il documento ipotizza che le capacità di rilevamento delle anomalie del modello ML possano essere estese ad applicazioni di sicurezza, come l'identificazione di logica Trojan o transizioni malformate.

Risultati Sperimentali
Gli autori hanno valutato AutoSlim utilizzando dataset sintetici che vanno da 1K a 64K nodi e benchmark biologici, dispiegati su una piattaforma Xilinx Zynq UltraScale+ ZCU104. Le scoperte chiave includono:

• Riduzione delle Risorse: AutoSlim ha ridotto l'utilizzo delle risorse FPGA fino al 40%. Per un dataset di 64K nodi, l'utilizzo delle Tabelle di Ricerca (LUT) è sceso da oltre 47.000 a meno di 7.000, e l'utilizzo dei registri è diminuito da 30.000 a 2.000.
• Throughput ed Efficienza: Il framework ha raggiunto un aumento del throughput dell'18% e ha migliorato l'efficienza energetica eliminando la logica ridondante e riducendo la congestione del routing.
• Sparsità del Grafo: Il numero medio di transizioni per nodo è stato significativamente ridotto (ad esempio, da ~180 a ~100 per 1K nodi, e sotto 5 per 64K nodi), dimostrando una semplificazione efficace senza perdita di utilità di classificazione.
• Tempo di Esecuzione: Il tempo di esecuzione della potatura è rimasto basso e coerente attraverso le dimensioni dei dataset, con lo strumento che converge rapidamente su grafi più grandi e più sparsi.

Significato e Affermazioni
Il documento afferma che AutoSlim introduce una "metodologia fondata e consapevole dell'hardware" che affronta direttamente i colli di bottiglia degli acceleratori simbolici basati su FPGA. Riducendo le dimensioni e la complessità del grafo preservando al contempo la correttezza semantica, il framework consente un dispiegamento più efficiente di applicazioni di matching di pattern su larga scala. Gli autori sottolineano che questo approccio getta le basi per ricerche future nell'elaborazione di automi robusta e affidabile, integrando potenzialmente l'analisi di sicurezza per rilevare componenti di grafo avversari. Il lavoro è presentato come un passo verso dispiegamenti FPGA scalabili, sicuri ed efficienti per l'elaborazione di dati simbolici.