基于预过滤结构的正则表达式硬件专用匹配引擎  

A hardware-specific matching engine for regular expressions based on pre-filtering structure

作　　者：李俊儒 张伟[1,2] 陈昆明[1] 徐涛 LI Junru;ZHANG Wei;CHEN Kunming;XU Tao(Computer School,Beijing Information Science&Technology University,Beijing 100101,China;Beijing Advanced Innovation Center for Materials Genome Engineering,Beijing Information Science&Technology University,Beijing 100101,China;Research Center for Microprocessor and System-on-Chip Technology,Tsinghua University,Beijing 100084,China)

机构地区：[1]北京信息科技大学计算机学院,北京100101 [2]北京信息科技大学北京材料基因工程高精尖创新中心,北京100101 [3]清华大学微处理器与片上系统技术研究中心,北京100084

出　　处：《北京信息科技大学学报（自然科学版）》2022年第1期50-57,共8页Journal of Beijing Information Science and Technology University

基　　金：北京材料基因工程高精尖创新中心项目。

摘　　要：为了提升正则表达式匹配性能,在网络数据激增的环境下实现数据同步过滤,提出了一种基于预过滤结构的正则表达式硬件专用匹配引擎。在现场可编程门阵列(FPGA)平台上以存储为中心,设计了基于共享内存的预过滤并行存储结构。使用布隆过滤器(Bloom filter, BF)作为预过滤结构;使用k路并行多组向量表用来存储BF中的哈希计算结果,提高初始化与查询的并行度;使用共享内存的过滤器组解决多长度模式串空间利用率低的问题;使用流水线提升预过滤器性能。面向不同字符串类型设计了匹配流程,保证了匹配功能的正确性,提升了正则表达式匹配性能。实验结果表明该匹配引擎在200 MHz的时钟频率下,单核吞吐量达39 Gbit/s,多核吞吐量达722 Gbit/s。In order to improve the regular expression matching performance and realize data synchronization filtering under the environment of the rapid increase of network data, a hardware-specific regular expression matching engine was proposed based on pre-filtering structure.Taking storage as the center, a pre-filtered parallel storage structure based on shared memory was designed on the FPGA platform.Bloom filter(BF) was used as the pre-filter structure, and the k-way parallel multi-G vector tables were used to store the Hash calculation results in BF to improve the parallelism of initialization and query;the shared memory filter groups were used to solve the problem of low space utilization of multi-length pattern strings;the pipeline was used to improve the performance of the pre-filter.The matching process was designed for different string types to ensure the correctness of the matching function and improve the regular expression matching performance.Experimental results show that the matching engine has a single-core throughput of 39 Gbit/s and a multi-core throughput of 722 Gbit/s at a clock frequency of 200 MHz.

关 键 词：正则表达式匹配 预过滤 FPGA 布隆过滤器 存储 

分 类 号：TP303[自动化与计算机技术—计算机系统结构]