TCS-TR-A-10-45Date: Tue Jun 29 00:45:57 2010 Title: Dynamic Reconfigurable Bit-Parallel Architecture for Large-Scale Regular Expression Matching Authors: Yusaku Kaneta, Shingo Yoshizawa, Shin-ichi Minato, Hiroki Arimura, and Yoshikazu Miyanaga Contact:
Abstract. 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 approach. This is the first dynamic reconfigurable FPGA-based hardware with guaranteed performance for the class of extended patterns, where a 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 of our architecture is the use of bit-parallel pattern matching approach that have 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 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. ©Copyright 2010 Authors |