Accelerating Regular Expression Matching over Compressed Data via Decoupled Speculative Execution on FPGA

Abstract

The common practice of compressing network traffic to enhance transmission efficiency poses a significant challenge to achieving high-speed regular expression matching. Since matching compression data relies on prior decompressed data and earlier matching outcomes, the conventional approach usually scans fully decompressed data, which suffers from bottlenecks caused by data inflation. Existing approaches accelerate compressed data matching by eliminating duplicate scanning, yet this speedup incurs unavoidable overhead on general-purpose CPU architectures. This paper introduces STRIDE, an FPGA-based accelerator that resolves the aforementioned constraints via decoupled speculative execution. Specifically, by decoupling the matching of compressed encodings from both the matching of uncompressed literals and the resolution of prior decompressed data, STRIDE leverages speculative results to enable uninterrupted scanning that does not depend on earlier outputs. Then, an asynchronous verification process validates these speculations and performs necessary corrections to ensure correctness. We implement STRIDE on a Xilinx Kintex-7 XC7K325T FPGA platform. Evaluations on real-world compressed datasets show that STRIDE achieves a throughput of 2.97 Gbps at 200 MHz and can reach a theoretical throughput of 3.33 to 5.64 Gbps, delivering a 4.16–7.05x speedup over the baseline. STRIDE demonstrates that speculative, decoupled execution is an effective paradigm for overcoming the performance limitations of compressed data matching.