High-speed String and Regular Expression Matching on FPGA
In recent FPGA researches, there has been much attention to dynamically reconfigurable algorithms that can modify their configuration on-the-fly. In this paper, we report recent progress on dynamically reconfigurable hardwares on FPGA for high-speed string and regular expression matching, which have been developed by our group since 2008. In particular, we describe the architecture, algorithms, and implementations of our pattern matching hardwares. We propose a pattern matching architecture, called dynamically reconfigurable bit-parallel NFA architecture which is the first dynamically reconfigurable hardware based on bit-parallel simulation of non-deterministic finite automata (NFA). This architecture enables fast dynamic reconfiguration of the patterns as well as high-throughput pattern matching for complex subclasses of regular expressions such as extended patterns, network expressions, and extended network expressions. 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 arithmeticoperations on these bit-masks consuming one input letter per clock. Experimental results show that our architecture has advantages over the previously proposed architectures in the terms of reconfiguration and running times.
Yusaku Kaneta Shingo Yoshizawa Shin-ichi Minato Hiroki Arimura
Graduate School of Information Science and Technology, Hokkaido University,N14 W9, Sapporo 060-0814, Graduate School of Information Science and Technology, Hokkaido University, N14 W9, Sapporo 060-0814
国际会议
2011亚太信号与信息处理协会年度峰会(APSIPAASC 2011)
西安
英文
1-7
2011-10-18（万方平台首次上网日期，不代表论文的发表时间）