BVAP: Energy and Memory Efficient Automata Processing for Regular Expressions with Bounded Repetitions

Regex accelerators handle a pattern like "any 8000 characters" by making 8000 copies of a circuit element — BVAP stores the repetition count as a bit vector instead, needing 270 elements where the old design needed 8004.

Why this problem is worth solving

Regular expression matching sits underneath network intrusion detection, virus scanning, spam filtering and protein motif search, and in all of those settings the rule sets are large and the input streams are fast. That is why specialised hardware exists: in-memory automata processors place a

The trouble is a construct these machines were never designed for.

What people did before, and where it broke

• Deterministic automata. Convert to a DFA and match in constant time per symbol. The state space explodes even without counting, which is why hardware accelerators use non-deterministic automata in the first place.
• In-memory automata processors. AP put states in memory rows and beat CPU and GPU implementations by more than tenfold. CA introduced a fully connected crossbar for routing and OR-aggregating active states; eAP shrank it by exploiting sparsity; Impala and CAMA improved the encoding, with CAMA using content-addressable memory to cut energy and memory further. All of them handle bounded repetition by unfolding.
• Just unfold it. Rewrite a bounded repetition as m copies of the pattern followed by n minus m optional copies. Correct, simple, and it multiplies the pattern size by roughly the bound — states linear in n, switch network quadratic in n.
• Add hardware counters. Extend the automaton with counter registers, as counter automata do in theory. This works until a regex is counter-ambiguous, meaning one control state may need to hold several different counter values at the same time. The paper implements this variant on top of CAMA to test it fairly, and finds the ambiguous parts still have to be unfolded.
• Software counting automata. A line of theoretical work converts counting automata into deterministic counting-set automata or separates ambiguous from unambiguous counting. Valuable models, but not hardware designs.
• The gap. The compact way to write counting and the compact way to build hardware had never been reconciled. Either the automaton stayed small and the hardware could not run it, or the hardware stayed simple and the automaton exploded.

How BVAP replaces unfolding with a bit vector

The idea

A set of counts is a bit vector, and a bit vector is what memory is good at. The starting observation is that a counting automaton needs to track not one count but a set of them, because non-determinism means the same control state may be reachable having consumed different numbers of symbols. Representing that set explicitly is expensive; representing it as a characteristic function is not. Bit i of the vector is one exactly when count i is currently possible, so incrementing all of them is one shift, and merging two sets of possibilities is one bitwise OR. The automaton then has one state per character class in the regex — linear in the size of the regex, not in the repetition bound — and the counting has moved from the topology into the contents of a memory word. The pattern of refusing to flatten a compact high-level construct into a low-level representation that destroys what made it compact, and instead teaching the backend to handle the construct directly, is the same discipline followed by compilers that carry tensor and privacy types down into proof circuits rather than lowering to scalar gates, covered elsewhere on this site.

Normalise the automaton so the hardware only needs one case. The engineering contribution is a transformation the authors call action-homogeneity. In general, different transitions entering the same state might need different bit vector operations, which would force each state to host something like a small programmable processor. The paper shows any such automaton can be rewritten so that every transition entering a state carries the same operation, at the cost of a constant number of extra states. That is a direct echo of what the Glushkov construction already does for predicates — and existing hardware already relies on that, since it is why a state can be a single memory row testing one character class. Extending the same normalisation to actions means each state carries one instruction from a five-entry table rather than an execution unit. Buying a large hardware simplification by paying a small, bounded cost in the representation is the same bargain struck when a mathematical normal form is co-designed with a minimal hardware primitive so no general-purpose unit is needed, covered elsewhere on this site.

Linearity is what makes the cheap ordering legal. There is a subtlety in when the action runs. The naive design applies each transition’s operation and then merges the results; BVAP merges first and applies the operation once. These agree only because every permitted operation is linear with respect to bitwise OR — applying it to a union gives the union of the applications — which mirrors the fact that the corresponding counter operation commutes with set union. That single algebraic property is what collapses a per-transition action unit into a per-state one, and it is why the set of allowed operations is deliberately small. From there the remaining costs are all about moving bits: reads are performed at the source so only their one-bit outputs travel through the crossbar rather than whole vectors, and vectors are routed a word at a time to balance area against latency. Designing around the observation that data movement rather than computation dominates the energy budget is the animating principle of in-memory and near-memory architectures generally, covered elsewhere on this site.

Following one repetition through the hardware

Each element holds a predicate and fires if the current input satisfies it. Activations are routed through the crossbar and OR-aggregated per row to decide who is available next cycle. For a bound of n this needs states proportional to n and a network proportional to n squared.

Why it works

• State count follows the regex, not the bound. One state per character class instead of one per repetition → a bound of 8000 costs bits in a vector rather than rows in an array → 270 elements against 8004, and patterns with bounds near 9000 become runnable at all.
• The crossbar shrinks quadratically with the states it connects. Unfolding grows the switch network as the square of the bound → removing the chain removes the network that connected it → which is where much of the area and routing energy saving comes from, since routing dominates this class of design.
• Action-homogeneity replaces an engine with an instruction. Every transition entering a state carries the same operation after the transformation → each state stores one entry from a five-operation table → so the per-state hardware is an instruction buffer and some peripheral logic rather than a processor.
• Linearity over bitwise OR permits aggregating before acting. Applying an action to a union equals the union of applications → one action unit serves all incoming transitions → collapsing what would otherwise be per-transition hardware into per-state hardware.
• Only one bit needs to travel for a read. Read actions execute at the source and emit a single bit → the crossbar carries one bit rather than a 64-bit vector → cutting routing energy in the phase that runs every cycle.

What it costs (trade-offs and scope)

• Throughput drops. BVAP is 11.2% slower than CAMA. The bit vector phase adds work per symbol, and although it runs on a faster clock and overlaps with the other phases, tiles with long bit-vector latency stall the input broadcast.
• Compute density is only on par with CAMA on average, and worse on some workloads. It is better on Snort by 64%, Suricata by 65%, ClamAV by 34% and YARA by 18%, but lower on Prosite, where the repetition bounds are mostly small, and on SpamAssassin, where only about 5% of states are counting states. The technique pays off in proportion to how much counting a workload actually does.
• A BVAP tile is 1.5 times larger than a CAMA tile. That pushes global wire delay from 26.1 to 39.1 picoseconds, and the area saving comes from needing far fewer tiles rather than from cheaper tiles.
• Bit vectors cannot cross tile boundaries. With 48 bit vectors of 64 bits per tile, the maximum supported repetition bound is 3072. The authors report this covers over 99% of regexes in their datasets, and anything larger falls back to partial unfolding.
• Two parameters need per-dataset tuning. The bit vector size and the threshold below which repetitions are unfolded anyway both trade area, energy and throughput, and the best settings differ by dataset. The design space exploration samples over 300 regexes per dataset rather than using all of them.
• Everything is simulated. A custom cycle-accurate simulator drives circuit models derived from SPICE simulations of custom SRAM and CAM arrays in TSMC 28nm. There is no fabricated chip, though the same simulator and models are used for all the compared designs.
• The streaming mode trades a lot of throughput. BVAP-S saves 39% energy and 79% power by lowering supply voltage, at the cost of 67% less throughput — useful for a sensor feed, not for line-rate scanning.

The evaluation

Check yourself

Sources

The paper is “BVAP: Energy and Memory Efficient Automata Processing for Regular Expressions with Bounded Repetitions” by Ziyuan Wen, Lingkun Kong, Alexis Le Glaunec, Konstantinos Mamouras and Kaiyuan Yang, published at ASPLOS 2024 Volume 2, pages 151-166, DOI 10.1145/3620665.3640412. The authors are at Rice University.

The ACM version is not open access. This explainer is written from the full text of the first author’s Rice University thesis of the same title, deposited in the Rice Digital Scholarship Archive, which presents the same work in expanded form. All figures above come from that text: the 37% and 85% statistics on bounded repetition prevalence, the 8004 against 270 state counts for the Snort pattern, the 67%, 95% and 94% energy reductions against CAMA, CA and eAP, the compute density comparisons including the per-dataset breakdown, the 11.2% throughput reduction against CAMA, the 1.5 times tile size ratio and 39.1 picosecond wire delay, the 48 bit vectors of 64 bits per tile giving a 3072 bound ceiling, and the BVAP-S trade of 39% energy for 67% throughput. Readers comparing the two versions should note one discrepancy: the conference abstract states 42 to 68% lower area, while the thesis text states more than 30% saved, both over the same benchmark set.