Events Calendar

Pd.D. Defense

Speaker: Yi-Hua Edward Yang, USC EE-Systems

Talk Title: Large-Scale and High-Throughput Pattern Matching on Parallel Architectures

Abstract: Large-scale pattern matching has many applications ranging from text processing to deep packet inspection (DPI) where hundreds or thousands of pre-defined strings or regular expressions (regexes) are matched concurrently and continuously against high-bandwidth input data. The large number of patterns and the high matching throughput make large-scale pattern matching both compute and memory intensive. In this thesis, we propose novel algorithms, constructions, and optimizations to accelerate large-scale pattern matching on two prominent classes of parallel architectures: Field Programmable Gate Arrays (FPGA) and general-purpose multi-core processors. We focus our studies on large-scale string pattern matching (SPM) and regular expression matching (REM) in the context of DPI for network intrusion detection.

For SPM, we propose a head-body partitioning to efficiently handle large dictionary. Specifically, we design a pipelined affix-search relay for accelerating the dictionary "head" on FPGA, as well as a body branch data structure with branch grafting for accelerating the dictionary "body" on processor core with single-instruction multiple-data (SIMD) operations. For REM, we propose a modified McNaughton-Yamada algorithm to convert an arbitrary regex into a modular NFA with uniform structure, which can be (1) mapped onto FPGA with spatial stacking and parallel SRL for scalable throughput and efficient resource utilization; (2) further partitioned into a segmented regex-NFA for efficient implementation in word-based operations on general-purpose processor core. We also develop software framework to automatically optimize our REM solutions. Overall, our designs achieve better memory efficiency, higher per-stream throughput, faster construction and better attack resilience over previous state-of-the-art solutions.

Finally, we formalize a novel semi-deterministic finite automaton for REM, offering space-time tradeoff between the compute-intensive NFA and the memory-intensive DFA. We propose the convolvement analysis and compatible state grouping algorithms to convert any NFA into a minimal SFA, whose space efficiency can then be traded off for lower time complexity.


Biography: Yi-Hua Edward Yang received the B.Sc. degree in Electrical Engineering from National Taiwan University, Taipei, Taiwan in 1997, and the M.Sc. degree in Electrical & Computer Engineering from University of Maryland, College Park, Maryland in 1999. He was a research assistant at the Information Sciences Institute, University of Southern California From 2005 to 2007. He is currently a Ph.D. candidate in the Ming Hsieh Department of Electrical Engineering, University of Southern California. His research interests include algorithmic optimization on parallel architectures, high performance architecture designs for network processing, security and cryptography.

Host: Defense Chair, Prof. Viktor K. Prasanna

Location: Hughes Aircraft Electrical Engineering Center (EEB) - 248

Audiences: EES & CS PhD Students & Faculty

Contact: Janice Thompson