A Programmable Controller Architecture for Regular Expression String Matching
The expressive power of regular expressions has been often adopted in network intrusion detection systems, virus scanners, and spam filtering applications. However in the CPU based systems, pattern matching is one of the most computation intensive parts. In this paper, we present the design, implementation and evaluation of a regular expression string matching programmable controller (SMPC). This special purpose controller is a parallel and pipelined processor architecture which can deal with the regular expression semantics. Two hardware stacks are implemented in SMPC to support fast branches when the non-matching occurs. Our implementation processes 4 characters per clock cycle (maximum performance of state of the art solutions) and occupies only O(n) memory (where n is the length of the regular expression). Via synthesizing the verilog description and analyzing area/time constraints, SMPC can achieve 200～400 times speedup over traditional CPU implementations and up to 7.9Gbps in processing throughput. Besides it outperforms the counterparts greatly as the complexity of regular expressions increases.
regular expression string matching special purpose controller fast branch
CHU Zhong LI Qiyue LI Jie WANG Jianping
Department of Electronic Information and Electric Engineering, Hefei University, Hefei, Anhui 230601 School of Electric Engineering and Automation, Hefei University of Technology, Hefei, Anhui 230009,
国际会议
The 31st Chinese Control Conference(第三十一届中国控制会议)
合肥
英文
5814-5819
2012-07-01（万方平台首次上网日期，不代表论文的发表时间）