The Algorithm and Framework Designs and Optimizations for Scalable Automata Processing on HPC Platforms

Student: Xiaodong Yu (Virginia Tech)
Advisor: Danfeng Yao (Virginia Tech)

Abstract: Automata processing could perform as the core of many applications in the areas such as network security, text mining, and bioinformatics. Achieving high-speed and scalable automata processing is exceptionally challenging. For one thing, the classic DFA representation is memory-bandwidth efficient but suffer from the state explosion problem in the presence of large datasets with complex patterns. And for another, the automata processing is inherently difficult to be parallelized due to the strong dependencies and unstructured memory-access pattern.

  In this thesis, we provide a comprehensive scheme for improving automata processing efficiency. At the algorithm level, we propose JFA that uses state variables to avoid state explosion. We also propose O3FA to handle out-of-order packets in NIDS. At the implementation level, we propose a comprehensive GPU-based automata processing framework and a code-generation framework for Automata Processors. Moreover, we provide a toolchain to conduct the apple-to-apple automata processing accelerators comparison.

Summary: pdf
Thesis Canvas: pdf

Presentation: pdf



Back to Doctoral Showcase Archive Listing