Machine Learning-Based Graph Simplification for Symbolic Accelerators

Resumo Técnico: Simplificação de Grafos Baseada em Aprendizado de Máquina para Aceleradores Simbólicos

Declaração do Problema
Aceleradores baseados em grafos, particularmente aqueles que utilizam Autômatos Finitos Não Determinísticos (NFA) para processamento de dados simbólicos (por exemplo, genômica, cibersegurança, PNL), enfrentam gargalos significativos de escalabilidade e eficiência. Sistemas como o NAPOLY+, que mapeiam autômatos diretamente para hardware FPGA, sofrem com consumo excessivo de memória, congestionamento de roteamento e computação redundante ao lidar com grafos grandes e complexos. A otimização de hardware tradicional frequentemente assume um grafo de entrada fixo, falhando em abordar a redundância inerente encontrada em cargas de trabalho simbólicas do mundo real, como estados inacessíveis, destinos lógicos duplicados e transições de baixo impacto. Além disso, técnicas existentes de redução de grafos frequentemente dependem de heurísticas estáticas que ignoram a natureza probabilística das cargas de trabalho e as semânticas de pontuação específicas exigidas por aceleradores modernos.

Metodologia: O Framework AutoSlim
Os autores propõem o AutoSlim, um framework baseado em aprendizado de máquina projetado para podar grafos de autômatos durante a etapa de pré-processamento, antes da implantação no hardware. A metodologia opera através do seguinte pipeline:

1. Geração e Anotação de Dados: Um gerador de conjuntos de dados de grafos simbólicos cria grafos de autômatos compatíveis com o formato de sobreposição do NAPOLY+. Esses grafos são anotados com métricas de pontuação (frequência de aresta, custo de transição, centralidade de nó) e codificados em XML, depois convertidos para CSV para extração de características.
2. Extração de Características e Classificação: O AutoSlim extrai características estruturais e comportamentais do grafo, utilizando principalmente pontuações de aresta. Emprega um classificador Random Forest para prever a utilidade de cada transição.
3. Pipeline de Poda: O classificador identifica e remove nós e arestas de baixo impacto (por exemplo, estados inacessíveis ou caminhos redundantes semanticamente equivalentes) enquanto preserva as semânticas funcionais do autômato. Crucialmente, o framework é projetado para manter as propriedades "conscientes de pontuação" do NAPOLY+, garantindo que a lógica de caminho de custo mínimo necessária para aplicações baseadas em classificação permaneça intacta.
4. Verificação e Implantação: Uma etapa de verificação garante a equivalência funcional após a poda. Os grafos simplificados resultantes são convertidos em vetores de configuração compatíveis com hardware e implantados em arquiteturas FPGA (especificamente Xilinx Zynq UltraScale+).

Principais Contribuições

• Poda Orientada por Dados: Diferentemente de métodos tradicionais baseados em regras estáticas, o AutoSlim utiliza uma abordagem de aprendizado supervisionado (Random Forest) para generalizar entre domínios e cargas de trabalho, identificando redundância com base em significância estatística em vez de regras estruturais fixas.
• Otimização Consciente de Hardware: O framework é explicitamente projetado para integrar-se ao modelo de correspondência baseado em pontuação do NAPOLY+, abordando as restrições específicas de recursos (BRAM, roteamento, elementos lógicos) de sobreposições FPGA.
• Escalabilidade: A ferramenta é projetada para lidar com grafos com dezenas de milhares de nós, abordando a lacuna de escalabilidade deixada por estudos anteriores que se concentraram em benchmarks sintéticos menores.
• Dupla Utilidade: O artigo postula que as capacidades de detecção de anomalias do modelo de ML poderiam ser estendidas para aplicações de segurança, como a identificação de lógica Trojan ou transições malformadas.

Resultados Experimentais
Os autores avaliaram o AutoSlim usando conjuntos de dados sintéticos variando de 1K a 64K nós e benchmarks biológicos, implantados em uma plataforma Xilinx Zynq UltraScale+ ZCU104. As principais descobertas incluem:

• Redução de Recursos: O AutoSlim reduziu o uso de recursos FPGA em até 40%. Para um conjunto de dados de 64K nós, o uso de Tabela de Pesquisa (LUT) caiu de mais de 47.000 para menos de 7.000, e o uso de registradores caiu de 30.000 para 2.000.
• Vazão e Eficiência: O framework alcançou um aumento de 18% na vazão e melhorou a eficiência energética ao eliminar lógica redundante e reduzir o congestionamento de roteamento.
• Esparsidade do Grafo: O número médio de transições por nó foi significativamente reduzido (por exemplo, de ~180 para ~100 para 1K nós, e abaixo de 5 para 64K nós), demonstrando simplificação eficaz sem perda de utilidade de classificação.
• Tempo de Execução: O tempo de execução da poda permaneceu baixo e consistente entre os tamanhos dos conjuntos de dados, com a ferramenta convergindo rapidamente em grafos maiores e mais esparsos.

Significado e Afirmações
O artigo afirma que o AutoSlim introduz uma "metodologia principial e consciente de hardware" que aborda diretamente os gargalos dos aceleradores simbólicos baseados em FPGA. Ao reduzir o tamanho e a complexidade do grafo enquanto preserva a correção semântica, o framework permite uma implantação mais eficiente de aplicações de correspondência de padrões em grande escala. Os autores enfatizam que essa abordagem estabelece as bases para pesquisas futuras em processamento de autômatos robusto e confiável, potencialmente integrando análise de segurança para detectar componentes de grafo adversariais. O trabalho é apresentado como um passo em direção a implantações FPGA escaláveis, seguras e eficientes para processamento de dados simbólicos.