HybridSA: GPU Acceleration of Multi-Pattern Regex Matching using Bit Parallelism
summary
HybridSA is a heterogeneous CPU–GPU engine that compiles regexes (Glushkov NFAs) into bit masks and runs bit-parallel shift-and extensions as many small CUDA kernels while dispatching irregular patterns to Hyperscan on CPU cores. A compiler chooses among ~80 specialized kernels and applies distributivity and bounded-repetition rewrites to shrink maximum transition distance and fit registers. About 80% of real-world regexes move to the GPU; measured throughput is 4–60× over a top CPU engine and 4–233× over prior GPU work.
AI-written summary · about
chapters (9)
- 0:00HybridSA introduction
- 1:45GPU programming model
- 5:14Shift-and algorithm
- 8:23Extending shift-and
- 9:29Kernel selection strategy
- 11:14Rewrite rules
- 12:39Experimental results
- 14:47Summary
- 15:33Q&A
related talks
01h 11mMachine Learning Acceleration in an Embedded World
01h 03mOLD VERSION: Building Abstractions at the Hardware-software Boundary
21mGraphitron: A Domain Specific Language for FPGA-Based Graph Processing Accelerator(…)
19mSSFFT: Energy-Efficient Selective Scaling for Fast Fourier Transform in Embedded GPUs
39mHella-Parallel Compute with RenderScript
22mAdvancing AI Computing With Optimized Matrix Multiplication Techniques With RISC-V CPU
23mRunning an Open Source LLM on Open Source Hardware
21mA Functional Approach to Synthesizing Routable Programmable Accelerators for Neural(…)