Machine Learning-Based Graph Simplification for Symbolic Accelerators

Technische Samenvatting: Machine Learning-gebaseerde Grafische Vereenvoudiging voor Symbolische Acceleratoren

Probleemstelling
Grafische acceleratoren, met name die welke Non-deterministische Eindige Automaten (NFA) gebruiken voor symbolische gegevensverwerking (bijvoorbeeld genomica, cyberveiligheid, NLP), staan voor aanzienlijke schaalbaarheids- en efficiëntieflessenhals. Systemen zoals NAPOLY+, die automaten direct toewijzen aan FPGA-hardware, lijden onder overmatige geheugengebruik, routeringscongestie en redundante berekening bij het verwerken van grote, complexe grafen. Traditionele hardware-optimalisatie gaat vaak uit van een vaste invoergraf, waardoor de inherente redundantie in real-world symbolische werklasten niet wordt aangepakt, zoals onbereikbare toestanden, gedupliceerde logische bestemmingen en transities met weinig impact. Bovendien vertrouwen bestaande grafische reductietechnieken vaak op statische heuristieken die de probabilistische aard van werklasten en de specifieke scoringsemantiek vereist door moderne acceleratoren negeren.

Methodologie: Het AutoSlim-kader
De auteurs stellen AutoSlim voor, een machine learning-gebaseerd kader dat is ontworpen om automaagrafen te snoeien tijdens de voorverwerkingsfase, voordat de hardware wordt ingezet. De methodologie werkt via de volgende pijplijn:

1. Gegevensgeneratie en Annotatie: Een generator voor symbolische grafische datasets creëert automaagrafen die compatibel zijn met het NAPOLY+-overlayformaat. Deze grafen worden geannoteerd met scoringmetrieken (edge-frequentie, transitiekost, node-centraliteit) en gecodeerd in XML, waarna ze worden geconverteerd naar CSV voor kenmerkextractie.
2. Kenmerkextractie en Classificatie: AutoSlim haalt structurele en gedragsmatige kenmerken uit de graf, voornamelijk gebruikmakend van edgescores. Het maakt gebruik van een Random Forest-classificator om de bruikbaarheid van elke transitie te voorspellen.
3. Snoeipijplijn: De classificator identificeert en verwijdert nodes en edges met weinig impact (bijvoorbeeld onbereikbare toestanden of semantisch equivalente redundante paden) terwijl de functionele semantiek van de automaat behouden blijft. Cruciaal is dat het kader is ontworpen om de "score-bewuste" eigenschappen van NAPOLY+ te handhaven, zodat de logica voor paden met minimale kosten die nodig is voor op ranking gebaseerde toepassingen intact blijft.
4. Verificatie en Inzet: Een verificatiestap zorgt voor functionele equivalentie na het snoeien. De resulterende vereenvoudigde grafen worden omgezet in hardware-compatibele configuratievectoren en ingezet op FPGA-architecturen (specifiek Xilinx Zynq UltraScale+).

Belangrijkste Bijdragen

• Data-gedreven Snoeien: In tegenstelling tot traditionele statische regelgebaseerde methoden, maakt AutoSlim gebruik van een supervised learning-aanpak (Random Forest) om te generaliseren over domeinen en werklasten, waarbij redundantie wordt geïdentificeerd op basis van statistische significantie in plaats van vaste structurele regels.
• Hardware-bewuste Optimalisatie: Het kader is expliciet ontworpen om te integreren met het op scoring gebaseerde matching-model van NAPOLY+, waarbij de specifieke resourcebeperkingen (BRAM, routering, logische elementen) van FPGA-overlays worden aangepakt.
• Schaalbaarheid: De tool is ontworpen om grafen met tienduizenden nodes te verwerken, waarmee de schaalbaarheidskloof wordt gedicht die door eerdere studies is achtergelaten, die zich richtten op kleinere synthetische benchmarks.
• Dubbele Bruikbaarheid: Het artikel stelt dat de anomaliedetectiecapaciteiten van het ML-model kunnen worden uitgebreid naar beveiligingstoepassingen, zoals het identificeren van Trojan-logica of misvormde transities.

Experimentele Resultaten
De auteurs hebben AutoSlim geëvalueerd met behulp van synthetische datasets variërend van 1K tot 64K nodes en biologische benchmarks, ingezet op een Xilinx Zynq UltraScale+ ZCU104-platform. Belangrijkste bevindingen zijn:

• Resource-reductie: AutoSlim verlaagde het FPGA-resourcegebruik met maximaal 40%. Voor een dataset van 64K nodes daalde het Look-Up Table (LUT)-gebruik van meer dan 47.000 naar minder dan 7.000, en daalde het registergebruik van 30.000 naar 2.000.
• Doorvoer en Efficiëntie: Het kader bereikte een toename van 18% in doorvoer en verbeterde de energie-efficiëntie door redundante logica te elimineren en routeringscongestie te verminderen.
• Grafische Sparsiteit: Het gemiddelde aantal transities per node werd aanzienlijk verminderd (bijvoorbeeld van ~180 naar ~100 voor 1K nodes, en onder de 5 voor 64K nodes), wat een effectieve vereenvoudiging aantoont zonder verlies van classificatiebruikbaarheid.
• Uitvoeringstijd: De uitvoeringstijd voor snoeien bleef laag en consistent over datasetgroottes, waarbij de tool snel convergeerde op grotere, sparser grafen.

Betekenis en Claims
Het artikel stelt dat AutoSlim een "geprincipieerde en hardware-bewuste methodologie" introduceert die direct de bottlenecks van op FPGA gebaseerde symbolische acceleratoren aanpakt. Door de grootte en complexiteit van grafen te verminderen terwijl de semantische correctheid behouden blijft, maakt het kader een efficiëntere inzet van op schaalbare patronenherkenning gebaseerde toepassingen mogelijk. De auteurs benadrukken dat deze aanpak de grondslag legt voor toekomstig onderzoek in robuuste en betrouwbare automatenverwerking, met potentiële integratie van beveiligingsanalyse om adversariële grafcomponenten te detecteren. Het werk wordt gepresenteerd als een stap naar schaalbare, veilige en efficiënte FPGA-inzetten voor symbolische gegevensverwerking.