Dynamic reconfigurable bit-parallel architecture for large-scale regular expression matching
Dynamic reconfigurable bit-parallel architecture for large-scale regular expression matching
复制标题
DOI：
10.1109/fpt.2010.5681536
复制
发表时间：
2010-12
期刊：
影响因子：
--
通讯作者：
Yusaku Kaneta;S. Yoshizawa;S. Minato;Hiroki Arimura;Y. Miyanaga
中科院分区：
文献类型：
--
作者：
Yusaku Kaneta;S. Yoshizawa;S. Minato;Hiroki Arimura;Y. Miyanaga
在本文中，我们提出了一种新的基于FPGA的大规模正则表达式匹配的架构，称为动态可重构位并行NFA架构（动态BP-NFA），允许使用位并行NFA模拟的模式的动态重新配置。这是第一个动态可重构的基于FPGA的硬件，具有扩展模式类的保证性能，其中扩展模式是线性形式的受限正则表达式，包括字母、字母类、不关心、可选字母、有界和无界长度间隙和可重复字母。我们的架构的关键是使用位并行模式匹配的方法，已经在字符串匹配社区开发了几十年。在这种方法中，输入NFA的信息被压缩编码在存储在寄存器和块RAM的集合中的位掩码中。然后，NFA被有效地模拟由一个固定的电路使用这些位掩码上的位和算术运算的组合，每个时钟消耗一个输入字母。实验结果表明，与已有的基于DFA的动态可重构结构相比，该结构对精确串模式类具有更高的吞吐量，对扩展模式类具有相当的吞吐量.
In this paper, we propose a novel FPGA-based architecture for large-scale regular expression matching, called dynamic reconfigurable bit-parallel NFA architecture (Dynamic BP-NFA) that allows dynamic reconfiguration of the patterns using bit-parallel NFA-simulation. This is the first dynamic reconfigurable FPGA-based hardware with guaranteed performance for the class of extended patterns, where an extended pattern is a restricted regular expression in linear form consisting of letters, classes of letters, don't cares, optional letters, bounded and unbounded length gaps and repeatable letters. The key to our architecture is the use of bit-parallel pattern matching approach that has been developed in string matching communities for the decades. In this approach, the information of an input NFA is compactly encoded in bit-masks stored in a collection of registers and block RAMs. Then, the NFA is efficiently simulated by a fixed circuitry using a combination of bit- and arithmetic-operations on these bit-masks consuming one input letter per clock. As compared with the previous approaches of DFA-based dynamic reconfigurable architectures, experimental results show that the proposed architecture achieves higher throughput for the class of exact string patterns and comparable for the class of extended patterns.