Lune

OOPSLA2024Top-tier venue

HybridSA: GPU Acceleration of Multi-pattern Regex Matching using Bit Parallelism

Alexis Le Glaunec, Lingkun Kong, Konstantinos Mamouras

Abstract

Multi-pattern matching is widely used in modern software for applications requiring high throughput such as protein search, network traffic inspection, virus or spam detection. Graphics Processor Units (GPUs) excel at executing massively parallel workloads. Regular expression (regex) matching is typically performed by simulating the execution of deterministic finite automata (DFAs) or nondeterministic finite automata (NFAs). The natural implementations of these automata simulation algorithms on GPUs are highly inefficient because they give rise to irregular memory access patterns.

This paper presents HybridSA, a heterogeneous CPU-GPU parallel engine for multi-pattern matching. HybridSA uses bit parallelism to efficiently simulate NFAs on GPUs, thus reducing the number of memory accesses and increasing the throughput. Our bit-parallel algorithms extend the classical shift-and algorithm for string matching to a large class of regular expressions and reduce automata simulation to a small number of bitwise operations. We have developed a compiler to translate regular expressions into bit masks, perform optimizations, and choose the best algorithms to run on the GPU. The majority of the regular expressions are accelerated on the GPU, while the patterns that exhibit random memory accesses are executed on the CPU in parallel. We evaluate HybridSA against state-of-the-art CPU and GPU engines, as well as a hybrid combination of the two. HybridSA achieves between 4 and 60 times higher throughput than the state-of-the-art CPU engine and between 4 and 233 times better than the state-of-the-art GPU engine across a collection of real-world benchmarks.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

4 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Static Analysis for Efficient Streaming Tokenization cites Software-hardware codesign for efficient in-memory regular pattern matching
  • Static Analysis for Efficient Streaming Tokenization cites RAP: Reconfigurable Automata Processor
  • Static Analysis for Efficient Streaming Tokenization cites Interleaved Bitstream Execution for Multi-Pattern Regex Matching on GPUs
  • Static Analysis for Efficient Streaming Tokenization cites Regular Expression Matching using Bit Vector Automata
  • Static Analysis for Efficient Streaming Tokenization cites Efficient Matching of Regular Expressions with Lookaround Assertions
  • Software-hardware codesign for efficient in-memory regular pattern matching cites CAMA: Energy and Memory Efficient Automata Processing in Content-Addressable Memories
  • Software-hardware codesign for efficient in-memory regular pattern matching cites Why GPUs are Slow at Executing NFAs and How to Make them Faster
  • RAP: Reconfigurable Automata Processor cites Software-hardware codesign for efficient in-memory regular pattern matching
  • RAP: Reconfigurable Automata Processor cites CAMA: Energy and Memory Efficient Automata Processing in Content-Addressable Memories
  • RAP: Reconfigurable Automata Processor cites Why GPUs are Slow at Executing NFAs and How to Make them Faster
  • RAP: Reconfigurable Automata Processor cites Regular Expression Matching using Bit Vector Automata
  • Interleaved Bitstream Execution for Multi-Pattern Regex Matching on GPUs cites Software-hardware codesign for efficient in-memory regular pattern matching
  • Interleaved Bitstream Execution for Multi-Pattern Regex Matching on GPUs cites Why GPUs are Slow at Executing NFAs and How to Make them Faster
  • Interleaved Bitstream Execution for Multi-Pattern Regex Matching on GPUs cites Regular Expression Matching using Bit Vector Automata
  • Regular Expression Matching using Bit Vector Automata cites Software-hardware codesign for efficient in-memory regular pattern matching
  • Efficient Matching of Regular Expressions with Lookaround Assertions cites Software-hardware codesign for efficient in-memory regular pattern matching
  • Efficient Matching of Regular Expressions with Lookaround Assertions cites Regular Expression Matching using Bit Vector Automata
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers4

  1. Interleaved Bitstream Execution for Multi-Pattern Regex Matching on GPUsTianao Ge, Xiaowen Chu, Hongyuan LiuMICRO 2025 · 4 citations
  2. Analyzing Near-Network Hardware Acceleration with Co-Processing on DPUsDimitrios Giouroukis, Dwi P. A. Nugroho, Varun Pandey, Steffen Zeuch et al.VLDB 2025 · 3 citations
  3. RAP: Reconfigurable Automata ProcessorZiyuan Wen, Alexis Le Glaunec, Konstantinos Mamouras, Kaiyuan YangISCA 2025 · 2 citations
  4. Static Analysis for Efficient Streaming TokenizationAngela W. Li, Yudi Yang, Konstantinos MamourasASPLOS 2026 · 1 citation

Builds on8

  1. Why GPUs are Slow at Executing NFAs and How to Make them FasterHongyuan Liu, Sreepathi Pai, Adwait JogASPLOS 2020 · 31 citations
  2. Software-hardware codesign for efficient in-memory regular pattern matchingLingkun Kong, Qixuan Yu, Agnishom Chattopadhyay, Alexis Le Glaunec et al.PLDI 2022 · 23 citations
  3. Regular Expression Matching using Bit Vector AutomataAlexis Le Glaunec, Lingkun Kong, Konstantinos MamourasOOPSLA 2023 · 22 citations
  4. Efficient Matching of Regular Expressions with Lookaround AssertionsKonstantinos Mamouras, Agnishom ChattopadhyayPOPL 2024 · 19 citations
  5. CAMA: Energy and Memory Efficient Automata Processing in Content-Addressable MemoriesYi Huang, Zhiyu Chen, Dai Li, Kaiyuan YangHPCA 2022 · 12 citations

Related papers

  1. Impala: Algorithm/Architecture Co-Design for In-Memory Multi-Stride Pattern MatchingElaheh Sadredini, Reza Rahimi, Marzieh Lenjani, Mircea Stan et al.HPCA 2020 · 43 citations
  2. ngAP: Non-blocking Large-scale Automata Processing on GPUsTianao Ge, Tong Zhang, Hongyuan LiuASPLOS 2024 · 11 citations
  3. BVAP: Energy and Memory Efficient Automata Processing for Regular Expressions with Bounded RepetitionsZiyuan Wen, Lingkun Kong, Alexis Le Glaunec, Konstantinos Mamouras et al.ASPLOS 2024 · 11 citations
  4. Cognitive Correlative Encoding for Genome Sequence Matching in Hyperdimensional SystemPrathyush Poduval, Zhuowen Zou, Xunzhao Yin, Elaheh Sadredini et al.DAC 2021 · 39 citations
  5. FlexAmata: A Universal and Efficient Adaption of Applications to Spatial Automata Processing AcceleratorsElaheh Sadredini, Reza Rahimi, Marzieh Lenjani, Mircea Stan et al.ASPLOS 2020 · 23 citations
Dusk over the sea between two cliffs drawn in fine vertical lines