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.