Machine Learning-Based Graph Simplification for Symbolic Accelerators

Technical Summary: Machine Learning-Based Graph Simplification for Symbolic Accelerators

Problem Statement
Graph-based accelerators, particularly those utilizing Non-deterministic Finite Automata (NFA) for symbolic data processing (e.g., genomics, cybersecurity, NLP), face significant scalability and efficiency bottlenecks. Systems like NAPOLY+, which map automata directly to FPGA hardware, suffer from excessive memory consumption, routing congestion, and redundant computation when handling large, complex graphs. Traditional hardware optimization often assumes a fixed input graph, failing to address the inherent redundancy found in real-world symbolic workloads, such as unreachable states, duplicated logical destinations, and low-impact transitions. Furthermore, existing graph reduction techniques often rely on static heuristics that ignore the probabilistic nature of workloads and the specific scoring semantics required by modern accelerators.

Methodology: The AutoSlim Framework
The authors propose AutoSlim, a machine learning-based framework designed to prune automata graphs during the preprocessing stage, prior to hardware deployment. The methodology operates through the following pipeline:

1. Data Generation and Annotation: A symbolic graph dataset generator creates automata graphs compatible with the NAPOLY+ overlay format. These graphs are annotated with scoring metrics (edge frequency, transition cost, node centrality) and encoded in XML, then converted to CSV for feature extraction.
2. Feature Extraction and Classification: AutoSlim extracts structural and behavioral features from the graph, primarily utilizing edge scores. It employs a Random Forest classifier to predict the utility of each transition.
3. Pruning Pipeline: The classifier identifies and removes low-impact nodes and edges (e.g., unreachable states or semantically equivalent redundant paths) while preserving the automaton's functional semantics. Crucially, the framework is designed to maintain the "score-aware" properties of NAPOLY+, ensuring that the minimal-cost path logic required for ranking-based applications remains intact.
4. Verification and Deployment: A verification step ensures functional equivalence after pruning. The resulting simplified graphs are converted into hardware-compatible configuration vectors and deployed onto FPGA architectures (specifically Xilinx Zynq UltraScale+).

Key Contributions

• Data-Driven Pruning: Unlike traditional static rule-based methods, AutoSlim utilizes a supervised learning approach (Random Forest) to generalize across domains and workloads, identifying redundancy based on statistical significance rather than fixed structural rules.
• Hardware-Aware Optimization: The framework is explicitly designed to integrate with the NAPOLY+ scoring-based matching model, addressing the specific resource constraints (BRAM, routing, logic elements) of FPGA overlays.
• Scalability: The tool is designed to handle graphs with tens of thousands of nodes, addressing the scalability gap left by previous studies that focused on smaller synthetic benchmarks.
• Dual Utility: The paper posits that the anomaly detection capabilities of the ML model could be extended to security applications, such as identifying Trojan logic or malformed transitions.

Experimental Results
The authors evaluated AutoSlim using synthetic datasets ranging from 1K to 64K nodes and biological benchmarks, deployed on a Xilinx Zynq UltraScale+ ZCU104 platform. Key findings include:

• Resource Reduction: AutoSlim reduced FPGA resource usage by up to 40%. For a 64K node dataset, Look-Up Table (LUT) usage dropped from over 47,000 to less than 7,000, and register usage fell from 30,000 to 2,000.
• Throughput and Efficiency: The framework achieved an 18% increase in throughput and improved power efficiency by eliminating redundant logic and reducing routing congestion.
• Graph Sparsity: The average number of transitions per node was significantly reduced (e.g., from ~180 to ~100 for 1K nodes, and below 5 for 64K nodes), demonstrating effective simplification without loss of classification utility.
• Execution Time: Pruning execution time remained low and consistent across dataset sizes, with the tool converging quickly on larger, sparser graphs.

Significance and Claims
The paper claims that AutoSlim introduces a "principled and hardware-aware methodology" that directly addresses the bottlenecks of FPGA-based symbolic accelerators. By reducing graph size and complexity while preserving semantic correctness, the framework enables more efficient deployment of large-scale pattern matching applications. The authors emphasize that this approach lays the groundwork for future research in robust and trustworthy automata processing, potentially integrating security analysis to detect adversarial graph components. The work is presented as a step toward scalable, secure, and efficient FPGA deployments for symbolic data processing.