DC: Small: Accelerating Large-Scale Pattern Matching for Data Intensive Applications

模式匹配是许多数据密集型计算应用的关键功能，从深度包检测、文本处理到基因组研究。以网页、XML文档、网络流量和科学数据为形式的数字信息的爆炸式增长，给大规模模式匹配的性能要求带来了巨大的压力。本研究将研究在ASIC/FPGA和多核平台上使用创新算法和架构，以加速网络安全，数据挖掘和过滤应用的大规模模式匹配。将考虑各种类型的模式匹配，包括正则表达式匹配、基于字典的字符串匹配和扩展正则表达式匹配。该建议的智力优点包括在算法和架构上的创新，用于匹配大模式集与高带宽数据输入。本文将从两个方面进行研究：(1)大规模模式匹配的新算法和数据结构；如有限自动机，动态搜索树，形式语言和图论。(2)基于asic / fpga、多核处理器和通用图形处理器（gpgpu）的并行架构的流水线、分区、可扩展和模块化设计的实用优化技术。与其产生针对特定输入或模式集的启发式方法，本文提出的研究旨在提高对大规模模式匹配的基本理解，并将这种理解应用于算法和架构创新。这允许探索在最先进的计算平台上使用实际优化的设计限制和权衡。这些设计将被映射到基于FPGA和多核技术的并行架构上，包括CPU-FPGA和CPU-GPU异构架构。

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 will be 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.