A Reconfigurable System Based on a Parallel and Pipelined Solution for Regular Expression Matching

We present a reconfigurable architecture that can perform highly parallel regular expression matching. The system can be configured on programmable devices such as FPGAs as a set of instances of a predefined core called REMA. Each core addresses one of the subtasks into which the regular expression matching problem can be partitioned. These cores work in parallel on the same string analyzing different possible matchings. Since the system can exploit dynamic partial reconfigurations, it can adapt the number of cores configured on the device at run-time, according to the complexity of the regular expression, which is proportional to the number of different ways in which the reference string can be mapped on pattern. Making it possible to parallelize the matching process with a multiple core architecture drastically improves temporal efficiency (up to one order of magnitude with respect to software solutions and up to a speedup factor of 25 with respect to hardware solutions). Most important, the run-time reconfigurability feature allows to implement a just in time logic usage strategy, thus reducing the mean amount of resources required.