Performance Evaluation of Regular Expression Engines Across Different Computer Architectures
This project focuses on regular expression matching which is playing an important role in a variety of applications, like genome sequence analysis, data mining, network inspection, etc. Different kinds of architectures such as CPU, XeonPhi, GPU, FPGA can perform regular expression matching. However, it is difficult on Von-Neumann architectures since it requires high irregular parallelism, high memory bandwidth as well as low latency.
Micron’s Automata Processor (AP) is designed for this kind of problem, using DRAM as a highly parallel reconfigurable fabric to implement NFAs. In this work we investigate for a fair comparison of best effort regular expression processing engines across all these aforementioned architectures which involves analyzing their performances with different types of regular expressions and exploring the design spaces of each of these architectures.
Our preliminary results indicate that CPU, XeonPhi and GPU are most likely bottlenecked by memory latency for rule lookup and AP and FPGA outperform other architectures due to their high capacity, their massively parallel execution and their capabilities of processing new input symbol every clock cycle. Furthermore, unlike FPGA, AP’s throughput is immune to complexity of NFA topologies and rulesets (i.e. large number of transitions, active states).
In the future work, we continue to explore the performance evaluation on more dimensions: “complexity” of regular expressions, the number of regular expressions, and multiple packets (streams) processing capability. We also extend the work to other benchmark suites that are not natural fits for regular expression, such as association rule mining, Markov chains, String kernel etc.
By Tommy Tracy