Pattern matching is a key function in many data intensive computing applications ranging from deep packet inspection, text processing, to genomic research. The explosive growth of digital information in the form of webpages, XML documents, network traffic and scientific data has put an enormous pressure on the performance requirements of large-scale pattern matching. This research will study the use of innovative algorithms and architectures on ASIC/FPGA and multi-core platforms to accelerate large-scale pattern matching for network security, data mining and filtering applications. Various types of pattern matching will be considered, including regular expression matching, dictionary-based string matching, and extended regular expression matching. The intellectual merit of this proposal includes the innovation in algorithms and architectures for matching large pattern sets against high bandwidth data input.

The proposed research is conducted from two perspectives:

  1. Novel algorithms and data structures for large-scale pattern matching; such as finite automata, dynamic search tree, formal language and graph theory.
  2. Practical optimization techniques for pipelining, partitioning, scalable and modular designs on parallel architectures with ASICs/FPGAs, multi-core processors and general-purpose graphics processors (GPGPUs).

Instead of producing heuristics specific to a particular input or pattern set, the proposed research aims to improve the fundamental understanding of large-scale pattern matching, and apply the understanding to both algorithmic and architectural innovations. This allows exploration of the design limits and tradeoffs in using practical optimizations on state-of-the-art computing platforms. The designs will be mapped onto parallel architectures based on both FPGA and multi-core technologies, including CPU-FPGA and CPU-GPU heterogeneous architectures.

  • Publications
    1. Edward Yang and Viktor K. Prasanna, "High-Performance and Compact Architecture for Regular Expression Matching on FPGA," IEEE Transactions on Computers, 2012.
    2. Hoang Le and Viktor K. Prasanna, "A Memory-Efficient and Modular Approach for Large-Scale String Pattern Matching," IEEE Transactions on Computers, v.62, 2013, p. 844.
    3. Hoang Le and Viktor K. Prasanna, "Scalable Tree-based Architectures for IPv4/v6 Lookup Using Prefix Partitioning," IEEE Transaction on Computers, 2011.
    4. Weirong Jiang and Viktor K. Prasanna, "Scalable Packet Classification on FPGA," IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.20, 2012, p. 1668.
    5. Yinglong Xia and Viktor K. Prasanna, "Distributed Evidence Propagation in Junction Trees on Clusters," IEEE Transactions on Parallel and Distributed Systems (TPDS), v.23, 2012, p. 1169.