NetMagic平台上正则表达式匹配技术实现

A Regular Expression Matching Technology Based on Net Magic Platform

在基于有限状态自动机的正则表达式匹配技术中,存储需求和匹配性能是一对相互制约的因素.统计分析发现,对于给定的自动机,状态的访问概率分布呈Zipf规律.为解决存储和性能的矛盾,设计并实现了基于Net Magic的两级存储的匹配引擎;根据状态的访问概率特性,将访问概率较高的状态配置在小容量的高速存储器中,访问概率较低的状态配置在大容量的低速存储器中,从而达到存储与性能的平衡.同时利用FPGA内部多RAM块特性,实例化多个匹配引擎,进一步使匹配速度线性提升.在资源充裕的条件下,理论上可达到65Gbps的吞吐量.实验表明单位存储代价大幅降低,但受限于Net Magic存储资源、频率及端口速率,实际性能为2.1Gbps.

In the field of regular expression matching based on finite state machine,storage requirement and matching performance con- dition each other. Statistics shows that for a given automata,the access probabilities of states follow the Zipf distribution. To solve the contradiction between space and performance,this paper designs a matching engine with two-level memory on the basis of NetMagic platform, and the state transition table is deployed according to the access probabilities. The states with high access probabilities are stored in high-speed memory with small capacity, and states with low access probabilities are stored in low-speed memory with large capacity, thus achieving a balance between storage and performance. Furthermore, the multi-block RAM in FPGA is configured as multi-engine. As a result,the matching speed is accelerated multiple times. Under the condition of abundant resources,the throughput can reach 65 Gbps in theory. The result shows that,the storage cost reduces significantly. As limited by the storage resources, frequency and port rate of NetMagic, the actual performance is 2.1Gbps.