Machine Learning-Based Graph Simplification for Symbolic Accelerators

Resumen Técnico: Simplificación de Grafos Basada en Aprendizaje Automático para Aceleradores Simbólicos

Enunciado del Problema
Los aceleradores basados en grafos, particularmente aquellos que utilizan Autómatas Finitos No Deterministas (AFN) para el procesamiento de datos simbólicos (por ejemplo, genómica, ciberseguridad, PLN), enfrentan cuellos de botella significativos en escalabilidad y eficiencia. Sistemas como NAPOLY+, que mapean autómatas directamente al hardware FPGA, sufren un consumo excesivo de memoria, congestión de enrutamiento y computación redundante al manejar grafos grandes y complejos. La optimización de hardware tradicional a menudo asume un grafo de entrada fijo, sin abordar la redundancia inherente encontrada en cargas de trabajo simbólicas del mundo real, como estados inalcanzables, destinos lógicos duplicados y transiciones de bajo impacto. Además, las técnicas existentes de reducción de grafos a menudo dependen de heurísticas estáticas que ignoran la naturaleza probabilística de las cargas de trabajo y las semánticas de puntuación específicas requeridas por los aceleradores modernos.

Metodología: El Marco de Trabajo AutoSlim
Los autores proponen AutoSlim, un marco de trabajo basado en aprendizaje automático diseñado para podar grafos de autómatas durante la etapa de preprocesamiento, antes del despliegue en hardware. La metodología opera a través de la siguiente tubería:

1. Generación y Anotación de Datos: Un generador de conjuntos de datos de grafos simbólicos crea grafos de autómatas compatibles con el formato de superposición de NAPOLY+. Estos grafos se anotan con métricas de puntuación (frecuencia de aristas, costo de transición, centralidad de nodos) y se codifican en XML, luego se convierten a CSV para la extracción de características.
2. Extracción de Características y Clasificación: AutoSlim extrae características estructurales y conductuales del grafo, utilizando principalmente puntuaciones de aristas. Emplea un clasificador de Bosque Aleatorio para predecir la utilidad de cada transición.
3. Tubería de Poda: El clasificador identifica y elimina nodos y aristas de bajo impacto (por ejemplo, estados inalcanzables o rutas redundantes semánticamente equivalentes) mientras preserva las semánticas funcionales del autómata. Crucialmente, el marco de trabajo está diseñado para mantener las propiedades "conscientes de la puntuación" de NAPOLY+, asegurando que la lógica de ruta de costo mínimo requerida para aplicaciones basadas en clasificación permanezca intacta.
4. Verificación y Despliegue: Un paso de verificación asegura la equivalencia funcional después de la poda. Los grafos simplificados resultantes se convierten en vectores de configuración compatibles con hardware y se despliegan en arquitecturas FPGA (específicamente Xilinx Zynq UltraScale+).

Contribuciones Clave

• Poda Basada en Datos: A diferencia de los métodos tradicionales basados en reglas estáticas, AutoSlim utiliza un enfoque de aprendizaje supervisado (Bosque Aleatorio) para generalizar a través de dominios y cargas de trabajo, identificando redundancia basada en significancia estadística en lugar de reglas estructurales fijas.
• Optimización Consciente del Hardware: El marco de trabajo está diseñado explícitamente para integrarse con el modelo de coincidencia basado en puntuación de NAPOLY+, abordando las restricciones específicas de recursos (BRAM, enrutamiento, elementos lógicos) de las superposiciones FPGA.
• Escalabilidad: La herramienta está diseñada para manejar grafos con decenas de miles de nodos, abordando la brecha de escalabilidad dejada por estudios anteriores que se centraron en benchmarks sintéticos más pequeños.
• Utilidad Dual: El artículo postula que las capacidades de detección de anomalías del modelo de ML podrían extenderse a aplicaciones de seguridad, como la identificación de lógica de Troyanos o transiciones malformadas.

Resultados Experimentales
Los autores evaluaron AutoSlim utilizando conjuntos de datos sintéticos que van desde 1K hasta 64K nodos y benchmarks biológicos, desplegados en una plataforma Xilinx Zynq UltraScale+ ZCU104. Los hallazgos clave incluyen:

• Reducción de Recursos: AutoSlim redujo el uso de recursos FPGA hasta en un 40%. Para un conjunto de datos de 64K nodos, el uso de Tablas de Búsqueda (LUT) disminuyó de más de 47,000 a menos de 7,000, y el uso de registros cayó de 30,000 a 2,000.
• Rendimiento y Eficiencia: El marco de trabajo logró un aumento del 18% en el rendimiento y mejoró la eficiencia energética al eliminar lógica redundante y reducir la congestión de enrutamiento.
• Dispersión del Grafo: El número promedio de transiciones por nodo se redujo significativamente (por ejemplo, de ~180 a ~100 para 1K nodos, y por debajo de 5 para 64K nodos), demostrando una simplificación efectiva sin pérdida de utilidad de clasificación.
• Tiempo de Ejecución: El tiempo de ejecución de la poda se mantuvo bajo y consistente a través de los tamaños de conjuntos de datos, con la herramienta convergiendo rápidamente en grafos más grandes y dispersos.

Significado y Afirmaciones
El artículo afirma que AutoSlim introduce una "metodología principista y consciente del hardware" que aborda directamente los cuellos de botella de los aceleradores simbólicos basados en FPGA. Al reducir el tamaño y la complejidad del grafo mientras se preserva la corrección semántica, el marco de trabajo permite un despliegue más eficiente de aplicaciones de coincidencia de patrones a gran escala. Los autores enfatizan que este enfoque sienta las bases para futuras investigaciones en el procesamiento robusto y confiable de autómatas, integrando potencialmente el análisis de seguridad para detectar componentes de grafos adversarios. El trabajo se presenta como un paso hacia despliegues FPGA escalables, seguros y eficientes para el procesamiento de datos simbólicos.