FPGA-based Machine for Regular expression matching

Abstract

String matching and regular expression matching has seen growing use in several areas like bio-medics, data mining, network processing, information security. This growing use has been accompanied with large numbers of expressions that need to be evaluated at a reasonable time. This problem has been tackled in software forms, which, do provide fast matching for a small number of rules which can be very complex but struggle when the number of current expressions being evaluated at the same time increases. Hardware solutions aim to provide increased parallelism in order to satisfy this increase in concurrent expression evaluations. Field programmable gate arrays (FPGA) in particular, provide a reprogrammable hardware configuration to evaluate these expressions. This flexibility allows for not only reconfigurations of the expressions being evaluated at the time but for improvements to the configuration to be deployed within a reasonable time without the production of more hardware. Powerful compilers developed by FPGA vendors have resulted in new ways of creating hardware mapping implementations, high-level synthesis (HLS) that simplify the design process while providing performant solutions. This research aims to provide and evaluate a software toolchain, supporting a wide range of regular expression features, to generate performance competent hardware mappings for FPGAs from a series of input regular expressions. This software will take the expressions, create deterministic finite automata (DFA) representing these expressions and generate C/C++ code that will be inputted on an HLS tool that will then generate the hardware configuration. The research will evaluate the generated hardware implementation while analysing the code structure and directives given to the HLS tool.