We present and evaluate an architecture for high-throughput pattern matching of regular expressions. Our approach matches multiple patterns concurrently, responds rapidly to changes in the pattern set, and is well suited for synthesis in an ASIC or FPGA. Our approach is based on a new and easily pipelined state-machine representation that uses encoding and compression techniques to improve density. We have written a compiler that translates a set of regular expressions and optimizes their deployment in the structures used by our architecture. We analyze our approach in terms of its throughput, density, and efficiency. We present experimental results from an implementation in a commodity FPGA, showing better throughput and density than the best known approaches.

Joint work with Benjamin Brodie and David Taylor of Exegy, Inc.

BIOGRAPHY

Ron K. Cytron is a professor of computer science and engineering at Washington University. His research interests include optimized middleware for embedded and real-time systems, fast searching of unstructured data, hardware/runtime support for object-oriented languages, and computational political science. Ron also serves as a technology advisor and has worked as a software engineer at Exegy, Inc., a startup company in St. Louis that is commercializing applications accelerated in reconfigurable logic.