Public Research Seminar by Microelectronics Thrust - Accelerating Automata Applications on Domain-specific and General-purpose Accelerators

We focus on a fundamental computation model, automaton, used widely in applications from various domains such as network intrusion detection, machine learning, and parsing. Large-scale automata processing is challenging for traditional von Neumann architectures. To this end, many accelerators are proposed---Micron's Automata Processor (AP) is an example. However, as a spatial architecture, AP cannot handle large automata programs without repeated reconfiguration and re-execution, limiting its performance severely.

We observed that many automata states are never-enabled in the execution but still configured on AP chips. Such ``cold'' states underutilize AP. To address this issue, we propose a lightweight offline profiling technique to predict which states are cold and partition the cold states out of AP. We develop SparseAP, with minimal hardware changes, to handle the misprediction efficiently. Our software and hardware co-optimization obtains a 2.1x speedup over baseline AP execution across evaluated applications.

While AP is performant, it is not easily available. By contrast, GPUs serve as general-purpose accelerators in lots of computer systems but execute automata applications slowly. Can we reduce the performance gap between GPU and AP? We identify excessive data movement in the GPU memory hierarchy and propose optimization techniques to reduce the data movement. Although our optimization techniques significantly alleviate these memory-related bottlenecks, a side effect is the static work assignment to cores. This leads to poor compute utilization since GPU cores are wasted on idle automata states. Therefore, we propose a novel dynamic scheme that effectively balances compute utilization with reduced memory usage. Our combined optimizations provide a significant improvement over the previous state-of-the-art GPU implementations of automata. Moreover, they enable current GPUs to outperform Automata Processor across several applications while performing within an order of magnitude for the rest of the applications.