Hopps: Leveraging Sparsity to Accelerate Automata Processing

Automata processing runs thousands of tiny finite-state machines over a stream of symbols at once — the engine behind network intrusion detection, DNA search, and data mining — and the fastest accelerators store each machine's transition graph as an uncompressed bit matrix in a memory crossbar, which is efficient only when the graph is dense; but these graphs are extremely sparse (each state has one or two neighbors), so the crossbars waste almost all their space on zeros; this paper (MIT and NVIDIA — Xingran Du, Joel Emer, Daniel Sanchez) builds Hopps, which pairs fast uncompressed "Hare" units for the frequently-used states with compact compressed-sparse "Tortoise" units for the rare ones, letting the Hares speculatively race ahead and roll back only on the rare Tortoise interruption, beating prior accelerators by 2.5 and 2.2 times at equal area.

The argument in one glance

Problem

Matching a stream against thousands of patterns at once is slow, so we build chips for it

Automata processing is the engine behind pattern matching at scale: it reads a stream of input symbols and checks it against many patterns at the same time, where each pattern is a small finite-state machine whose transition diagram is a graph. This is how a network intrusion detector scans traffic against thousands of malicious signatures, how bioinformatics searches DNA, and how data-mining tools find motifs. Each automaton is tiny — from under ten to a few thousand states — but a workload uses thousands of them, so the real task is traversing thousands of small graphs concurrently over the same symbol stream. CPUs and GPUs are bad at this: a state-of-the-art GPU processes most benchmarks at under 200 megabytes per second, and the Snort intrusion detector at only 115 megabytes per second, far below the hundreds of gigabits per second a modern network card delivers. So the field has turned to specialized accelerators.
What people did

Store each automaton as a bit matrix in a fast memory crossbar

The fastest automata accelerators store each automaton's adjacency matrix — which state can transition to which — as an uncompressed bitset, one bit per possible transition, inside a memory crossbar built from DRAM or SRAM. Crossbars are wonderful for this when graphs are dense: they read a whole row of transitions in parallel, giving very high throughput and efficiency for the bit matrix they hold.
Why it fell short

The graphs are almost all zeros, so the crossbars are almost all wasted

The catch is that automata graphs are extremely sparse. Patterns are typically chains of subpatterns, so each state transitions to only one or two others — the adjacency matrix is overwhelmingly zeros. A crossbar storing an uncompressed bitset pays for every entry whether it is a one or a zero, so as sparsity grows the crossbar wastes almost all of its space holding zeros. A 200-state automaton with two neighbors per state needs a 200-by-200 bit matrix uncompressed but only about 400 nonzero entries — a hundredfold difference. That wasted space means fewer patterns fit on a chip of a given area, which forces the accelerator to process the automata in more batches, taking more slow passes over the whole input stream. Prior crossbar accelerators exploit little or none of this sparsity.
This paper's idea

Pair fast dense units with compact sparse units, and speculate across them

Hopps is the first automata accelerator to exploit compressed sparse data representations. It combines two kinds of unit: Hare units store states uncompressed for high throughput but poor space efficiency, and Tortoise units store states in a compressed-sparse format for high space efficiency but lower, more variable throughput. A novel partitioning algorithm — using each automaton's graph topology, how likely each state is to match input, and a small profiling run — puts the frequently-used states in the fast Hare units and keeps a large fraction of the state, the rarely-used part, in the compact Tortoise units. The Hare units speculatively run ahead and only roll back on the rare occasion a Tortoise unit hits a frequently-needed state. Offloading the infrequent work makes the Hare units so much cheaper (smaller crossbars) that the common case runs even faster. On the AutomataZoo benchmarks Hopps beats prior accelerators Impala and SpAP by 2.5 and 2.2 times at equal area.

Why this problem is worth solving

The workload is both important and a near-perfect fit for hardware, if the hardware uses its space well.

An automaton is a finite-state machine: as each input symbol arrives, the machine moves from its current active states to their successors according to a transition graph, and a pattern is reported when the machine reaches an accepting state. Automata processing runs many such machines against one symbol stream simultaneously — thousands of them, each small (from under ten to a few thousand states), so the workload is fundamentally the concurrent traversal of thousands of small graphs. This structure is why specialized hardware helps so much: there is enormous parallelism to exploit, since every automaton advances on the same symbol independently, and the per-automaton work is regular graph following. The applications are ones where throughput is critical — scanning network traffic for intrusion signatures, searching genomes, mining data for patterns — and where general-purpose processors fall far short of line rate. The performance a good accelerator can reach is bounded by how many automata it can keep resident and active per unit of chip area, because a workload with more automata than fit must be split into batches, each requiring a separate pass over the entire input. So the whole game is packing as much active automaton state as possible onto the chip, which makes the data representation, not just the compute, the thing that decides performance.

That is exactly where the crossbar approach leaves performance on the table.

Memory crossbars are the reason prior automata accelerators are fast: a crossbar stores an automaton’s adjacency matrix as a grid of bits, and in one operation it can read out, in parallel, all the transitions enabled from the currently active states. This dense, parallel read is ideal when the matrix is full. But an automaton’s adjacency matrix is almost never full. Because patterns are built as chains of subpatterns, each state leads to only one or two others, so the matrix is dominated by zeros — a state with two out of two hundred possible successors leaves the other 198 entries empty. A crossbar cannot tell a meaningful zero from a stored one cheaply; it allocates a bit cell for every entry regardless, so it spends the overwhelming majority of its silicon storing zeros that carry no information. The consequence is quadratic storage — space proportional to the number of states squared — when the actual information is linear in the number of transitions. Compressed representations from other domains, like Compressed Sparse Row format used in sparse linear algebra, store only the nonzeros and so need space proportional to the transitions, which for these graphs can be a hundred times less. Bringing that compression to automata processing is what lets far more patterns fit on a chip, and that is the opportunity crossbar designs, by construction, cannot take.

What people did before, and where it broke

CPU and GPU automata processing. Traverse the automata in software with general-purpose parallelism. Where it broke. Far too slow: a state-of-the-art GPU runs most benchmarks under 200 megabytes per second and Snort at 115 megabytes per second, orders of magnitude below network line rate and below dedicated accelerators.
Crossbar accelerators storing uncompressed bitsets (Impala, eAP). Store each adjacency matrix as a dense bit grid in a memory crossbar and read enabled transitions in parallel. Where it broke. Automata graphs are highly sparse, so the crossbar wastes most of its area on zeros; efficiency is high only for dense graphs, and few sparse patterns fit per chip.
Coarse-grained structural sparsity in crossbars. Pack the adjacency matrix into blocks across multiple crossbars to skip some empty regions. Where it broke. It exploits only coarse block-level structure, not the fine-grained one-or-two-neighbors sparsity, so it still stores large uncompressed bitsets and leaves most of the sparsity unused.
Frequency-aware execution without compression (SpAP). Separate frequent and infrequent states to raise throughput, tracking timestamps so infrequent states can be re-synchronized. Where it broke. It still stores adjacency matrices uncompressed in crossbars, so it improves throughput handling but does not fix the fundamental space waste that limits how many automata fit.
The gap. No accelerator brought the compressed-sparse data representations that transformed sparse linear algebra, graph analytics, and deep learning to automata processing, so none turned the graphs’ extreme sparsity into more patterns per chip and thus higher performance.

How Hopps works

Splitting automaton state between fast dense units and compact sparse units

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

The idea

Bring the machinery of sparse accelerators to a domain that never used it. The central move is to notice that automata processing has exactly the property that sparse accelerators in other fields were built to exploit — an overwhelmingly zero data structure — and yet no automata accelerator had ever used a compressed representation. In sparse linear algebra, graph analytics, and deep learning, the winning idea is the same: store only the nonzeros, so memory footprint drops from quadratic to linear and you never spend compute or storage on entries that are zero. Hopps imports that idea, representing an automaton’s adjacency matrix in a compressed-sparse format so that a graph whose information is a few hundred transitions no longer occupies tens of thousands of bit cells. The direct benefit is space: for a given chip area, dramatically more patterns fit resident, which is precisely what determines automata-processing performance because it decides how many passes over the input the workload needs. Recognizing that a workload’s data is sparse enough to warrant compressed representations, and building the hardware to store only the nonzeros, is the same foundational insight the sparse-matrix-multiplication accelerator work covered elsewhere on this site is built on, turning the absence of data into savings rather than paying to store it. Hopps is the first to apply that insight to automata.

Make the common case fast and the uncommon case cheap, with two complementary unit types. A pure compressed design would be space-efficient but slow, because decompressing sparse data is inherently lower and more variable in throughput than a crossbar’s parallel read; a pure crossbar design is fast but wasteful. Hopps refuses to choose, splitting the work by frequency. Its Hare units keep the frequently-used states uncompressed and run them at one symbol per cycle, while its Tortoise units keep the rarely-used states — the large majority — compressed and pay their slowness only on the rare accesses. The elegant twist is that this is not merely averaging two designs: because the infrequent states are offloaded to the compact Tortoise units, the Hare units have to hold much less, so they can be built from smaller, cheaper crossbars, which makes the common-case path faster than a monolithic fast design could afford to be. Splitting a workload into a hot path that is optimized for speed and a cold path that is optimized for compactness, so that relieving the hot path of the cold work makes the hot path itself cheaper, is the same efficiency philosophy the energy-and-memory-efficient automata-processing work covered elsewhere on this site pursues, right-sizing the hardware to where the work actually is rather than provisioning uniformly for the worst case.

Speculate that the cold path stays cold, and only pay when it does not. Splitting fast and slow units raises a coordination problem: the slow Tortoise units could stall the fast Hare units every time state has to cross between them, erasing the benefit. Hopps solves this with speculation. The Hare units do not wait for the Tortoises; they run ahead through the symbol stream on the assumption that the infrequent states will stay quiet, and the Tortoise units process asynchronously behind them. The bet almost always holds, because the infrequent states are, by construction, rarely activated. Only when a Tortoise unit actually finds an infrequent state that activates a frequent one — the uncommon event — does it interrupt the Hares to re-synchronize, rolling back the speculative work that assumed otherwise. Because rollbacks are rare, the amortized cost is low and throughput stays close to running everything in the fast units. Running ahead optimistically on the assumption that a rare event will not occur, and paying a rollback only on the exceptional case, is the same non-blocking, speculative discipline the non-blocking automata-processing work covered elsewhere on this site relies on, keeping the fast path moving rather than stalling it on every possible dependence.

Following a symbol stream through Hopps

Processing input against automata split into Hare and Tortoise units

A trace, drawn from the paper's design, of how Hopps advances thousands of automata on a symbol stream while exploiting sparsity.

Step 1 of 5

Automata are partitioned and placed before the run

Offline, Hopps runs its partitioning algorithm on each automaton, using graph topology, per-state match likelihood, and a small profiling input to mark states frequent or infrequent. Frequent states are mapped to Hare units, the large infrequent majority to compressed Tortoise units, so far more automata fit on the chip.

A match-set compression scheme reduces the storage that maps input symbols to the states they can match, saving further area.

Why it works

Compression turns quadratic storage into linear, fitting more patterns. An uncompressed adjacency matrix costs space proportional to states squared, mostly zeros → but a compressed-sparse form stores only the transitions, proportional to nonzeros → so far more automata fit per chip, cutting the batches and passes that bound performance.
Offloading cold state makes the hot units cheaper, not just balanced. A monolithic fast design must size crossbars to hold everything → but moving infrequent state to compact Tortoise units lets the Hare units use smaller crossbars → so the common-case path is faster than a fast-everything design could afford.
Frequency partitioning puts the slowness where it rarely bites. Compressed access is inherently slower and more variable → but the compressed Tortoise units hold only rarely-activated states → so their slowness is paid seldom, keeping average throughput high.
Speculation avoids stalling the fast path on the slow one. Coordinating fast and slow units could stall the Hares on every crossing → but the Hares run ahead assuming the cold path stays cold and roll back only on rare interrupts → so throughput stays close to running everything in the fast units.
A domain-fit representation beats a general dense one. Crossbars are efficient only for dense matrices, which automata are not → but matching the representation to the graphs’ real one-or-two-neighbor sparsity → so Hopps beats prior crossbar accelerators by 2.5 and 2.2 times at equal area, and a GPU by over 10 times.

What it costs (trade-offs and scope)

The partition depends on a profile that must predict behavior. Hopps decides which states are frequent using topology, match likelihood, and a small profiling input; if the real input stream behaves very differently from the profile, more infrequent states will activate, raising the rollback rate and eroding the speedup, so the gains rest on the profile being representative.
Speculation adds rollback machinery and cost. Running the Hares ahead requires the ability to detect a mis-speculation and roll back, which is hardware and time spent whenever an infrequent state does activate a frequent one; the design is efficient because such events are rare, but a workload where they are not would pay more.
The Tortoise units are genuinely slower. Compressed-sparse access is lower and more variable in throughput than a crossbar read, so any work that lands on the Tortoise path is slow; correctness and performance both depend on the partition keeping that path lightly traveled.
It is a specialized accelerator, not a general processor. Hopps targets automata processing specifically; realizing its benefit means expressing a workload as automata and mapping them through Hopps’s partitioning and placement, and the numbers come from an ASIC design evaluation, not a drop-in software library.
Results are on a benchmark suite against specific baselines. The 2.5-times and 2.2-times equal-area gains are geometric means over the AutomataZoo suite versus Impala and SpAP, and the more-than-10-times figure is against a particular GPU implementation; other automata, sparsity levels, or baselines could shift the margins.

The evaluation

Accelerating sparse automata processing

Property	Crossbar (Impala)	Frequency-aware crossbar (SpAP)	Hopps
Data representation
Exploits fine-grained sparsity
Handles frequent vs infrequent states
Patterns resident per unit area
Reported performance per area

A comparison drawn from the paper. Hopps is evaluated on the AutomataZoo benchmark suite against prior accelerators Impala and SpAP at equal area; the 2.5-times and 2.2-times figures are the paper's reported geometric-mean performance-per-area gains, and Hopps also exceeds a state-of-the-art GPU implementation by more than 10 times in throughput.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

The full paper text was available (an open-access copy from the MIT institutional repository), so this account of the mechanism — automata processing as concurrent sparse-graph traversal, the crossbar accelerators’ waste of space on sparse adjacency matrices, Hopps’s hybrid of uncompressed Hare units and compressed-sparse Tortoise units, the frequent/infrequent partitioning algorithm using topology, match likelihood, and profiling, the speculative run-ahead with rare rollback on Tortoise interrupts, the match-set compression, and the doomed-node handling — follows the paper’s own description. The headline numbers are the paper’s reported results: 2.5 and 2.2 times better geometric-mean performance-per-area than Impala and SpAP at equal area on AutomataZoo, and more than 10 times higher throughput than a state-of-the-art GPU implementation (with a very large performance-per-area advantage given Hopps’s small ASIC area). Those figures are for the AutomataZoo suite and specific baselines; results depend on the automata, their sparsity, and how representative the profiling input is. Exact per-benchmark numbers, the microarchitecture, and the partitioning heuristics should be read from the paper itself.

Background

Why sparsity keeps reshaping accelerators

It helps to see Hopps as part of a broad arc in computer architecture. Over the last decade, one of the most productive ideas in accelerator design has been to stop treating data as uniformly dense and to build hardware that skips the zeros. In sparse linear algebra, in graph analytics, and above all in deep learning — where pruned neural networks are mostly zeros — accelerators that store only nonzero values and avoid computing on zeros have delivered large gains in memory footprint, energy, and speed. The reason the idea travels so well is that sparsity is not a niche accident but a pervasive property of real data structures: matrices, graphs, and now automata are far emptier than their dimensions suggest. Each new domain that adopts compressed representations gets the same twofold win — less storage and less wasted work — and the engineering challenge is always to keep the irregular access to compressed data from destroying the parallelism that made the dense design fast. Hopps extends this arc into automata processing, a domain whose crossbar-based accelerators had, ironically, doubled down on dense storage for the sake of parallel reads. This recurring recognition that exploiting the emptiness of data is where large efficiency gains hide is the same driving idea behind the graph-processing accelerator work covered elsewhere on this site, which likewise turns the sparse, irregular structure of its data into a source of parallelism rather than a liability. Hopps shows the automata domain had been leaving that win untaken.

If you remember only three things

1. Automata processing runs thousands of small finite-state machines over a symbol stream at once (network intrusion detection, DNA search, data mining), and is too slow on CPUs and GPUs, so specialized accelerators are used; the fastest store each automaton's adjacency matrix uncompressed as a bitset in a memory crossbar, which is efficient only when the graph is dense — but automata graphs are extremely sparse (each state has one or two neighbors, since patterns are chains of subpatterns), so the crossbars waste most of their area storing zeros, fitting fewer patterns per chip and forcing more slow passes over the input.
2. Hopps is the first automata accelerator to use compressed sparse representations, combining fast uncompressed Hare units (for the frequently-used states, one symbol per cycle) with compact compressed-sparse Tortoise units (for the rarely-used majority). A novel partitioning algorithm assigns states using graph topology, match likelihood, and a small profiling run; the Hare units speculatively run ahead and roll back only on the rare Tortoise interrupt when an infrequent state activates a frequent one. Offloading the cold state lets the Hare units use smaller crossbars, making the common case even faster, and a match-set compression scheme saves further area.
3. On the AutomataZoo benchmark suite, Hopps beats prior accelerators Impala and SpAP by geometric-mean 2.5 and 2.2 times at equal area, and exceeds a state-of-the-art GPU by more than 10 times in throughput (with a far larger performance-per-area advantage given its small ASIC area). Its gains depend on the frequency partition being accurate (a bad profile raises rollbacks), the Tortoise path being lightly traveled, and the workload being expressible as automata; it is a specialized accelerator evaluated in ASIC design, not a general processor.

Check yourself

Check your understanding

1. Why are crossbar-based automata accelerators inefficient despite being fast?
2. What is the core idea behind Hopps's Hare and Tortoise units?
3. How does Hopps keep the slow Tortoise units from stalling the fast Hare units?
4. What are Hopps's main results and the conditions its gains depend on?

Sources

The paper is “Hopps: Leveraging Sparsity to Accelerate Automata Processing” by Xingran Du and Daniel Sanchez (Massachusetts Institute of Technology) and Joel S. Emer (MIT and NVIDIA), published at ASPLOS 2025 (Volume 3), DOI 10.1145/3676642.3736126. It is licensed CC BY-NC-SA.

This explainer is based on the paper’s full text, obtained from an open-access copy in the MIT institutional repository (DSpace). The account of the mechanism — automata processing as the concurrent traversal of many small, highly sparse finite-state-machine graphs; the prior crossbar accelerators (Impala, eAP, SpAP) that store adjacency matrices as uncompressed bitsets and waste area on sparse graphs; Hopps’s hybrid of high-throughput uncompressed Hare units and space-efficient compressed-sparse Tortoise units; the compressed-sparse representation that reduces storage from quadratic in states to linear in transitions; the novel frequent/infrequent partitioning algorithm using graph topology, per-state match likelihood, and a small profiling input; the speculative execution in which Hare units run ahead and roll back on rare Tortoise interrupts; the match-set compression scheme; and the doomed-node handling combined with SpAP-style batching — follows the paper’s own description. The reported results cited here are the paper’s own: geometric-mean 2.5 and 2.2 times better performance-per-area than Impala and SpAP at equal area on the AutomataZoo benchmark suite, and more than 10 times higher throughput than the state-of-the-art GPU implementation ngAP on Snort (Hopps reaching 0.90 symbols per cycle, about 1.8 gigabytes per second at 2 gigahertz), with Hopps’s small ASIC area yielding a very large performance-per-area advantage. Exact per-benchmark numbers, the microarchitecture, the interconnect, and the partitioning heuristics should be read from the paper itself.