ngAP: Non-blocking Large-scale Automata Processing on GPUs

Pattern matching against thousands of rules at once — intrusion detection, virus scanning, gene search — runs on finite automata, and everyone processes them one input character at a time, which puts a synchronisation barrier between every character and leaves a graphics processor around 33 percent busy; ngAP (William and Mary) removes the barrier by writing the character position into each unit of work, so many positions can be in flight together — and then uses the room that creates for three further optimisations, the largest of which replaces the repetitive part of the matching with a precomputed lookup table.

The argument in one glance

Problem

Matching thousands of patterns at once is slow and getting slower

Intrusion detection, virus scanning and gene search all work by running an input stream against a large collection of patterns, each compiled into an automaton. The collections keep growing — one widely used intrusion ruleset grew 71 percent in seven years — and the matching is full of irregular memory access and tight data dependencies.
What people did

Run it on a graphics processor

These machines have enormous parallelism and are available everywhere, unlike the specialised in-memory matching hardware that has been proposed. There is parallelism to exploit at several levels: many input streams, many automata, and many states active at once.
Why it fell short

One character at a time leaves most of the threads idle

Every existing design processes a single input symbol per round and synchronises before the next. Threads with no work finish early and wait. Measured across twenty applications the average thread utilisation is 32.6 percent, and several applications sit below 3 percent, because the number of simultaneously active states is simply small.
This paper's idea

Put the character position into the work item and drop the barrier

If each item in the queue records which input position it belongs to, work from different positions can sit in the same queue and run together. That alone is not faster, but it creates room for three optimisations that are: fill the queue ahead of time, replace the repetitive matching with a lookup table, and let a thread keep its next item in a register.

Why this problem is worth solving

The data structure being processed is less rigid than it looks.

A set of states connected by transitions, where each state accepts a particular set of input symbols and, when it matches, activates its neighbours for the next symbol. Unlike its deterministic cousin, many states can be active at the same time, which is exactly the property that makes it worth putting on a parallel machine. One detail matters enormously here: patterns that may begin anywhere in the input, which is most of them, compile to states that are permanently active and therefore have to be matched against every single symbol that arrives. These always-active states are the source of most of the redundant work in the whole system.

is a graph traversal in disguise, and the traversal is what gets parallelised.

The implementation everyone uses is where the serialisation lives.

A way of running the traversal that keeps a queue of only the states that matched, rather than statically assigning threads to states. Two queues are kept, one holding the current round’s matched states and one collecting the next round’s, and they swap at the end of every round. That swap is a barrier — every thread must finish the current symbol before any thread starts the next — and it is imposed by the implementation rather than required by the automaton, because a state only ever needs to see the symbols it is going to consume, not all the symbols in order.

is the thing this paper takes apart.

What people did before, and where it broke

Assign threads statically to states or transitions. The earliest approach: fix the mapping once and let each thread watch its own piece of the automaton. Where it broke. Most states are idle most of the time, so most threads are idle most of the time. This is why the field moved to queues.
Keep a queue of only the matched states. Far better, and what the state of the art does. Threads pick up entries and push their newly matched neighbours back for the next round. Where it broke. The queue swap at the end of each symbol is a barrier, and the queue is often too short to fill the machine. Average thread utilisation across twenty applications is 32.6 percent, with several under 3 percent.
Split the input and speculate about where each piece starts. A long line of work partitions the stream and guesses which states are active at each split point, recomputing when a guess is wrong. Where it broke. It relies on there being one active state to guess, which is true of deterministic automata and not of the compact non-deterministic ones that suit a parallel machine.
Enumerate every possibility instead of guessing. No mis-speculation to repair, at the price of doing every possible version of the work. Where it broke. The extra work is substantial, and it has the same deterministic-automaton assumption underneath.
Start matching from the always-active states at many positions at once. The closest prior attempt at overlapping different input positions. Where it broke. It performs well when patterns are evenly balanced and badly when they are not, and the paper measures it losing on exactly those cases.
Build dedicated in-memory matching hardware. Orders of magnitude faster than a general processor and a rich research area. Where it broke. Programmability and availability. Not everyone can get one, and adding another special-purpose accelerator to a system has its own costs.
The gap. Everyone had accepted that automata are processed one symbol at a time, which made the per-symbol barrier invisible as a design choice. Nobody had asked what becomes possible if a queue is allowed to hold work belonging to different positions in the input at once.

How dropping a barrier changes what is possible

From one symbol per round to many positions in flight

↓ →
new
↓ →
new
↓ →
new
↓ →
new
↓ →
new

Twenty applications from three benchmark suites, from 2,300 to 2.4 million states, on an RTX 3090 with a Volta-generation check, against three prior GPU engines and the leading CPU engine.

The idea

The barrier was never required by the automaton, only by the way it was written down. The reason everyone processes one symbol per round is that the queue implicitly encodes which round it belongs to — every entry in it is understood to be matched against the same symbol, so the queues have to swap between symbols. Put the symbol index inside each entry and that assumption dissolves: an entry now says what to match and where, so entries from different positions in the input can coexist and run concurrently. The scope of synchronisation collapses from the whole application to a single entry. What makes this an honest paper is that the authors report what this buys on its own, which is almost nothing — thread utilisation rises from 32.6 to 33.2 percent and throughput actually falls about 10 percent from the extra bookkeeping. Its value is as an enabler. Looking past the parallelism everyone is already exploiting to find a finer axis hidden inside the work is the same move the graph-mining accelerator covered elsewhere on this site makes when it stops handing each unit a whole separate search tree.

The largest win is deleting work rather than parallelising it. Because most patterns can start anywhere, their opening states are permanently active and must be matched against every symbol that ever arrives. That is a lot of computation, and crucially it is the same computation over and over — the set of always-active states never changes, so the outcome depends only on the symbols. Since the number of distinct short symbol sequences is finite, every outcome can be computed once, offline, and stored in a table. Measurement says that tabulating sequences of length one through five removes between 59.7 and 88.6 percent of the total work, with most of the benefit arriving by length three. In the breakdown this single optimisation carries the throughput from 1.9 times the baseline to 7.0. Refusing to materialise the repetitive part of an automaton and storing it compactly instead is the same instinct as the bounded-repetition work covered elsewhere on this site, which represents a pattern like “any eight thousand characters” as a counter rather than eight thousand copies of a circuit.

The last optimisation deliberately gives up parallelism to buy locality. In the queue-based design a thread loads a state, finds its neighbours, writes them out, and is then handed something unrelated next round — so the neighbour it just held in a register is fetched again from memory by a different thread. The fix is for the thread to keep going on what it already has, privately, instead of publishing it. That is strictly less parallel, and on a machine where threads run in lockstep groups it is worse than that: if only a few threads in a group want to continue, the rest stall. So the decision is made per group, by measuring what fraction of its threads still have work and stopping when that falls below a threshold, with the depth capped at a single step because going further serialises badly. The effect shows up where you would expect, with the cache hit rate rising from 0.23 in the baseline to 0.71. Rescheduling work so that memory accesses line up rather than scatter, and accepting a cost elsewhere to get it, is the same trade the concurrent graph traversal work covered elsewhere on this site makes when it aligns many queries onto the same vertex at the same time.

Following one work item through a thread

What a single thread does, once

The queue holds pairs of a matched state and the input position it should be matched at next. Everything below happens for one such pair.

Step 1 of 5

Claim a slice of the queue

Threads take a window of entries by atomically advancing a head and a tail pointer. There is no swap and no round — the window simply moves forward through a queue that other threads are appending to at the same time.

A larger window amortises the cost of moving the pointers, and the measurements show throughput is not very sensitive above a few thousand entries. The window is one of four parameters the best-case configuration tunes per application.

Why it works

Removing the barrier does not create parallelism, it removes a ceiling on it. With a barrier, the only work available at any instant is whatever matched the current symbol, which is often a handful of states → without it, work from many positions can coexist in one queue → so an optimisation that manufactures work from other positions suddenly has somewhere to put it, which is why the prefetching lifts utilisation from 33.2 to 83.6 percent rather than doing nothing.
The permanently active states are both the biggest cost and the easiest thing to precompute. They must be matched against every symbol, so they generate work proportional to the input length regardless of what matches → but the set never changes, so the result depends only on the symbols themselves → and since the number of short symbol sequences is finite, every possible answer can be enumerated once and looked up thereafter.
Tabulating short sequences captures most of the benefit for a fraction of the cost. Extending the tabulated sequence length from one to three raises the eliminated work from 59.7 to 81.9 percent → going on to five adds only another 6.7 points → while the table size grows with the alphabet raised to that length, which is why stopping at three is the right place to stop.
Compressing the table pays twice. Most possible symbol sequences never leave any state active, so their table rows are empty → indexing by the sequences that actually occur, with a search to find them, removes those rows entirely → which for several applications shrinks a table from over a hundred megabytes to a few kilobytes and improves throughput by around 5 percent through the smaller memory footprint alone.
Locality and parallelism trade against each other, so the trade is made per thread group. Keeping the next item in a register avoids writing it out and reading it back → but threads run in lockstep groups, so one thread continuing while its neighbours cannot is worse than none continuing → measuring the fraction of the group with remaining work and deciding collectively keeps the benefit while avoiding the divergence.

What it costs (trade-offs and scope)

The headline idea is a slowdown by itself. Non-blocking processing alone runs about 10 percent slower than the blocking baseline, raises thread utilisation by barely half a percentage point, and increases memory requests by 40 percent. The paper reports this plainly. Its role is to make the other three optimisations expressible, and the authors state that none of them can be applied without it.
The dominant contribution is the table, and the table is large. Going from prefetching to memoisation takes throughput from 1.9 to 7.0 times the baseline. Tables for sequences of length three run from hundreds of megabytes to 67.2 gigabytes for one application, on which compression achieves nothing. Two applications had to fall back to length two because length three exceeded the memory of the GPUs used, and length four or more is described as taking hours to build and being very expensive to store.
It is slower than the baseline on several applications. Reading the absolute throughput table rather than the geometric mean, the best configuration is roughly 2.7 times slower than the prior state of the art on one application, about 1.7 times slower on another, and slower on a third, while losing to a different prior system on two more. Two of the twenty applications have no permanently active states at all, which disables both the prefetching and the memoisation.
The distribution behind the average is extremely skewed. The maximum speedup of 901.9 times is one application, and the paper reports that 8 of 15 exceed ten times. The geometric mean of 7.9 is the number to hold on to, and the authors do lead with it.
Roughly a third of the headline is per-application tuning. With one set of parameters for everything the speedup is 5.5 times; sweeping four parameters per application brings it to 7.9.
The tuning does not travel between GPU generations. On an older architecture the untuned configuration drops from 5.5 to 3.4 times, and the authors say directly that the default parameters may not be portable enough across architectures.
On a single input stream the CPU engine often wins. Latency is measured by processing one stream, and there the mature CPU engine is substantially faster on applications with few automata — by roughly nine times on one of them. The authors report this and suggest speculation as future work rather than claiming the gap away.
Some throughput figures for slow configurations are estimated rather than measured. Runs that could not finish within an hour are assigned an upper-bound throughput derived from the time limit.
The comparison drops a few automata to accommodate the baselines. Two prior systems require a transformation limiting how many outgoing transitions a state may have, and a handful of automata cannot be transformed, so two were removed from one application and five from another. This design needs no such transformation, which is a genuine advantage, but the head-to-head numbers on those two applications are on a trimmed benchmark.
The throughput setting is generous with input-level parallelism. Measurements use a one megabyte stream replicated 600 times, which supplies abundant stream parallelism. The single-stream latency results are where that assumption is removed, and they are noticeably less favourable.

The evaluation

What each layer of the design actually contributes

Property	Blocking, one symbol per round	Non-blocking, on its own	Non-blocking plus all three optimisations
Thread utilisation
Throughput relative to blocking	Baseline
Cache hit rate
Memory requests	Baseline
What it costs to deploy	Nothing beyond the automaton

Compared against three prior GPU engines and a mature CPU engine across twenty applications, with a sensitivity study on an older GPU generation.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

The honest reading of this paper is in its own breakdown table. Non-blocking processing, the idea in the title, is a 10 percent slowdown on its own and lifts thread utilisation by half a percentage point; the throughput comes overwhelmingly from the memoisation table, which takes the result from 1.9 to 7.0 times the baseline. That table is not free — hundreds of megabytes to 67.2 gigabytes depending on the application, with compression achieving nothing in the worst case, and two applications forced down to shorter sequences because they did not fit in GPU memory. The geometric mean of 7.9 hides a very skewed distribution with a maximum of 901.9 on a single application, and it also hides several applications where this design is slower than the state of the art it is compared against, including one where it is roughly 2.7 times slower. Two applications have no permanently active states and therefore gain nothing from two of the three optimisations. About a third of the headline comes from sweeping four parameters per application, and those parameters do not transfer well to an older GPU, where the untuned speedup falls from 5.5 to 3.4 times. On a single input stream the mature CPU engine is often faster, sometimes by nearly an order of magnitude, which the authors report and address as future work. Some figures for very slow configurations are upper bounds derived from a one-hour time limit rather than measurements. And two of the baselines required an automaton transformation that a handful of automata could not undergo, so those were excluded from the comparison.

Background

When is a serial dependency real?

The interesting general question this raises is how to tell a genuine ordering constraint from one that is an artefact of how the code was written. Automata matching has been called embarrassingly sequential, and the label feels earned: each symbol determines which states are active for the next, so surely they must be processed in order. What this paper shows is that the sequencing belongs to individual states, not to the system. A given state only needs to see the symbols it will actually consume, in order, relative to itself. Because the queue implicitly encoded which round it belonged to, the implementation was enforcing something much stronger than that — a global agreement about the current symbol — and once each entry carries its own position, the global agreement is simply unnecessary. The contrast worth drawing is with cases where the dependency is real and the temptation is to ignore it. In training a large network of overlapping sub-networks that share weights, the algorithm genuinely requires a later sub-network to observe an earlier one’s update, and the pipeline-parallel supernet work covered elsewhere on this site exists precisely because parallelising it naively either serialises everything or silently produces wrong results. Same surface appearance, opposite conclusion. The engineering question is always which dependency the algorithm actually has, rather than which one the data structure happens to imply.

If you remember only three things

1. Automata matching is universally implemented one input symbol per round, with a queue swap acting as a barrier between symbols — but that barrier is imposed by the data structure rather than required by the automaton, since a state only needs to see the symbols it will consume, and writing the symbol position into each queue entry lets work from many positions run concurrently.
2. Removing the barrier is worth nothing by itself, and the paper says so — thread utilisation moves from 32.6 to 33.2 percent and throughput falls about 10 percent — but it makes three optimisations possible that were not expressible before: prefetching the matches against permanently active states in batches, replacing those matches entirely with an offline lookup table, and letting a thread keep its next item in a register when enough of its lockstep group can also continue.
3. The result is a geometric mean of 7.9 times the previous best GPU engine across twenty applications, with the memoisation table contributing most of it by deleting between 60 and 88 percent of the work outright — at the cost of a table that can reach tens of gigabytes, four parameters that need tuning per application and do not transfer across GPU generations, and several applications where this design is actually slower than what it replaces.

Check yourself

Check your understanding

1. Why is the barrier between symbols an implementation artefact rather than a requirement?
2. Why do permanently active states dominate the redundant work, and how is that work removed?
3. Why is keeping the next work item in a register done conditionally rather than always?
4. What does the paper own breakdown reveal about where the speedup comes from?

Sources

The paper is “ngAP: Non-blocking Large-scale Automata Processing on GPUs” by Tianao Ge, Tong Zhang and Hongyuan Liu, published at ASPLOS 2024, pages 268-285, DOI 10.1145/3617232.3624848. It is open access and includes an artifact appendix.

This explainer is written from the full 18-page text. Everything above comes from the paper’s own sections: the background on non-deterministic automata, homogeneous representations, always-active versus start-of-data starting states, and the worked example of matching a pattern against the word banana; the motivation section quantifying thread utilisation at 32.6 percent on average with several applications under 3 percent, analysing why the queue is often too short, measuring the fraction of work attributable to pattern prefixes at lengths one through five, and explaining why the changing thread-to-state mapping destroys locality; the design section covering the state-index pair representation, the sliding window with its atomic head and tail pointers, the handling of always-active states, the batched prefetching with its measured jump in utilisation to 83.6 percent, the offline memoisation table with its construction procedure, its three-stage balanced loading, its memory and time costs per application, the reasoning behind stopping at length three, and the compressed indexing scheme with its measured effect; the work privatisation mechanism with its active-thread-ratio threshold and its single-step depth limit; the evaluation methodology covering the two GPUs, the twenty applications and their state counts, the replicated input stream, the time limit and its estimated upper bound, and the validation against a serial reference implementation; and the results, covering normalised and absolute throughput against three GPU baselines and the CPU engine, the incremental breakdown of each optimisation, the cache and memory request profiling, the sensitivity studies for window size, batch size and divergence threshold, the older-architecture comparison with its roofline analysis and occupancy figures, and the single-stream latency measurements.