Academic
Publications
Time and area efficient pattern matching on FPGAs

Time and area efficient pattern matching on FPGAs,10.1145/968280.968312,Zachary K. Baker,Viktor K. Prasanna

Time and area efficient pattern matching on FPGAs   (Citations: 101)
BibTex | RIS | RefWorks Download
Pattern matching for network security and intrusion detection demands exceptionally high performance. Much work has been done in this field, and yet there is still significant room for improvement in efficiency, flexibility, and throughput. We develop a novel linear-array string matching architecture using a buffered, two-comparator variation on the Knuth-Morris-Pratt(KMP) algorithm. For small (16 or fewer characters) patterns, it competes favorably with the state-of-the-art while providing better scalability and reconfiguration, and more efficient hardware utilization. The area efficiency compared to other approaches improves further still as the pattern size increases because only the tables increase in size.KMP is a well-known, efficient string matching technique using a single comparator and a precomputed transition table. We add a second comparator and an input buffer, allowing the system to accept at least one character in each cycle and terminate after a number of clock cycles at maximum equal to the length of the input string plus the size of the buffer. The system also provides a clean, modular route to reconfiguring the patterns on-the-fly and scaling the system to support more units, using several rows of linear array elements. In this paper, we prove the bound on the buffer size and running time, and provide performance comparisons against other approaches.
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...The first approach makes use of the reconfigurable nature of field programmable gate arrays (FPGA), exploiting the fine grain configurability of the devices to implement a dense pattern matching structure [1-6]...

    Fabien Alibartet al. Hybrid CMOS/nanodevice circuits for high throughput pattern matching a...

    • ...A recent research trend to large-scale regular expression matching hardwares is to simulate finite state automata for a given class of regular expressions on a specially designed hardware ([3], [4], [7], [11], [13], [14], [16], [17], [18])...
    • ...In the dynamic reconfiguration approach ([3], [4], [7], [11]), a universal control logic is statically compiled into FPGA beforehand, a description of regular expressions is loaded to the FPGA as data in preprocessing time, and then simulated in run-time...
    • ...In Table. III, we compared our NFA-based hardware against the previous DFA-based dynamic reconfigurable hardwares [3], [4], [7], where Class indicates the target class, bRAM/char the number of bytes used in block RAMs per letter, and Logic Cells/char the number of logic cells used per letter...
    • ...For the class STR, our Dynamic BP-NFA achieved higher throughput of 2.9 Gbps than Baker et al.’s KMP-based hardware [4] and Jung et al.’s Bitsplit-based hardware [7]...
    • ...<{[SECTION]}>KMP-based hardware [4] STR Virtex-II Pro 1.8 Gbps 4 bytes/char 3.2 3200 NA...

    Yusaku Kanetaet al. Dynamic reconfigurable bit-parallel architecture for large-scale regul...

    • ...However, since the number of failure transitions taken is limited by the number of input characters consumed [13], TAFA will always have an amortized throughput of at least 0.5 characters per clock cycle...

    Yi-Hua Edward Yanget al. High Performance Dictionary-Based String Matching for Deep Packet Insp...

    • ...The well-known Knuth-Morris-Pratt algorithm for string matching which uses a linear array for mapping the state transition, and a Bloom filter based scheme able to scan a large volume of patterns at gigabit rates were also both implemented on an FPGA in [25] [26] ...

    Hao Wanget al. A modular NFA architecture for regular expression matching

    • ...ASIC or FPGAs [5], [6], [7], [8], [9], [4], [10], [11]; and (2) software designs on multi-core systems [12], [13], [14]...

    Yi-Hua E. Yanget al. Head-body partitioned string matching for Deep Packet Inspection with ...

Sort by: