Large pattern-matching workloads can exceed the state capacity of an automata processor (AP), forcing an application to be split into batches that each process the same input. This repeated configuration and execution can reduce throughput. A proposed approach combines NFA state prediction with a sparse execution mode to reduce the resources occupied by states that are unlikely to activate, while preserving a path for handling prediction errors.
Why large automata workloads strain spatial architectures
An AP is a spatial architecture designed to execute non-deterministic finite automata (NFAs) directly. NFA states are mapped to state transition elements, or STEs, and can be evaluated in parallel. Because transitions are handled within the memory-based structure, the AP can avoid the irregular transition-table data movement associated with executing NFAs on conventional processors.
The trade-off is that the application’s configured state must fit within the available AP capacity to run as a whole. A half-core can hold up to 24,000 states. When an application exceeds capacity, its NFAs are typically divided into batches. Each batch must process the input stream, so the input is effectively scanned again for subsequent batches. As NFA workloads grow in size or use state-increasing techniques to improve parallelism, these repeated passes can become a significant performance cost.
Automata processor efficiency and the cold-state opportunity
Not every state configured for an NFA is necessarily activated during a particular execution. A state becomes enabled through the NFA’s transition process, which depends on the input symbols. If a preceding state does not match, downstream states may never become enabled. The study calls states that are never enabled during execution cold; states that are enabled are hot.
Across 26 applications examined in the evaluation, an average of 59% of states were cold, with the proportion reaching as high as 99% in one workload. These states still occupy configuration capacity despite not contributing to the observed matching activity. Removing accurately identified cold states from the configured set can therefore allow more useful work to fit on the AP at once and may reduce the number of input re-executions.
Using NFA structure to predict hot and cold states
Identifying cold states perfectly is generally not possible in advance because NFA behavior depends on the input. However, state position in the automaton provides a useful prediction signal. States closer to starting states are more likely to be reached; deeper states require a sequence of preceding matches and are more likely to remain inactive.
To apply this idea to NFAs containing cycles, the method first identifies strongly connected components (SCCs). Each SCC is treated as a unit, producing a directed acyclic graph that can be topologically ordered. State depth is then normalized relative to the maximum depth of its NFA, allowing automata of different sizes to be compared. In the evaluated workloads, hot states generally appeared closer to the start of the NFA, while cold states tended to be deeper.
A profiling input is used to simulate the automata before execution. For each NFA, the partition boundary is placed after the deepest state observed as hot during profiling. States up to that boundary are predicted hot; deeper states are predicted cold. The predicted-hot portion is then divided into batches that fit the AP. The approach also accounts for constraints from SCCs and topological ordering: some states that are cold may still need to be included in the predicted-hot portion to preserve the partition structure.
How SparseAP handles prediction errors
Profiling cannot guarantee that every state classified as cold will remain inactive during the actual workload. If execution reaches a state that was left off the AP, the system needs a way to continue matching without losing correctness. The proposed design adds an intermediate reporting state for each transition that crosses the partition boundary.
When the AP encounters such a transition, the intermediate state generates a report identifying the input position and the state that must be enabled. Execution then proceeds in a second mode called SparseAP, or SpAP. The AP is configured with the predicted-cold states, and the intermediate reports direct it to the appropriate states and input positions.
Enable and jump operations
SparseAP uses two operations to process these reports:
- Enable: Activates the required state in the predicted-cold set based on the state identifier in an intermediate report.
- Jump: Advances to the input position associated with the next report when no state is enabled, avoiding unnecessary processing of intervening symbols.
Because the partition follows topological order, transitions across the boundary proceed in one direction—from the predicted-hot portion to the predicted-cold portion. This avoids repeatedly switching between execution modes. The intermediate reports are stored off chip, with a portion loaded into an on-chip queue for processing. When multiple reports require state enables at the same input position, input processing may stall until those enables are completed.
Reported performance and practical considerations
In detailed simulations across 26 applications, the BaseAP/SparseAP execution model achieved a 2.1× geometric mean speedup over baseline AP execution using 1% of the input for profiling; the reported maximum speedup was 47×. Results varied by workload. Applications that generated many simultaneous intermediate reports could incur enable stalls, while large SCCs could limit the benefit of partitioning. The work also reports that, on average, its approach improved performance per STE by 32.1% for an AP half-core using 1% profiling input.
These results are simulation findings, not a guarantee for every deployment. The practical benefit depends on how much of an application is cold, how representative the profiling input is, how the NFA’s SCC structure constrains partitioning, and how many intermediate reports arise during execution. System designers should account for report handling and configuration costs alongside the potential reduction in repeated input passes.
Conclusion: matching workload structure to AP capacity
For large NFA applications, the central challenge is not only total state count but also how much configured state is actually used. Profiling-based cold-state prediction can make more AP capacity available for likely active states, while SparseAP provides a mechanism to recover when a predicted-cold state is needed. Together, these techniques offer an architectural approach to reducing batch re-execution and improving utilization. For engineers and system architects, the key consideration is whether the workload’s state activity and automaton structure provide enough predictable sparsity to outweigh the overhead of profiling and intermediate-report handling.