Title: Automata Processing: from Application Acceleration to Hardware Design
Abstract: Inexact pattern matching is widely used in many fields, such as machine learning, network intrusion detection, bioinformatics, and many other applications. Inexact pattern matching is usually the most time-consuming phase in such applications because of the complexity of inexact matching between the input string and a large number of reference patterns, thus, reducing inexact matching time is key to accelerate such applications. Automata processing is a computational model that is widely used for matching regular expressions and can be used for inexact pattern matching. However, because of the memory bottleneck due to the random memory behavior of automata processing on von-Neumann architectures, the performance is not satisfying, especially for large-scale applications, which requires hardware acceleration. This dissertation studies the potential benefits of spatial architectures, which can process certain computation using reconfigurable processing elements.
To understand better how automata processing could be used to accelerate inexact pattern matching, we use Entity Resolution and searching for potential gRNA off-targets for CRISPR/Cas9 as two case studies. We solve the two problems using automata-based approaches, and evaluate the performance on both von-Neumann architectures (CPUs and GPUs) and spatial architectures (Micron's Automata Processor and FPGAs). We find that automata engines on spatial architectures show a clear advantage over methods on von-Neumann architectures. Therefore, we propose an automated automata processing framework using FPGAs on cloud-based platforms, and propose several novel features to better utilize FPGA resource, such as symbol-only reconfiguration, processing multiple symbols per cycles, etc. To further improve the performance for large-scale applications, we propose an automata overlay (a pre-configured virtual automata processing architecture that overlays on top of the physical FPGA configurable fabric) to reduce the high overhead for FPGA reconfiguration.
Committee Members: Mircea Stan (Chair), Kevin Skadron (Advisor), Ashish Venkat, Samira Khan, Ashish Sirasao (Xilinx)