Asynchronous Automata Processing on GPUs
Asynchronous Automata Processing on GPUs
复制标题
DOI：
10.1145/3579453
复制
发表时间：
2023-02
期刊：
影响因子：
--
通讯作者：
Hongyuan Liu;Sreepathi Pai;Adwait Jog
中科院分区：
文献类型：
--
作者：
Hongyuan Liu;Sreepathi Pai;Adwait Jog
在模式匹配和数据分析等许多应用领域中，状态自动机都是计算核心。GPU上的现有方法在自动机处理任务中利用三个级别的并行性：1）~输入流级别，2）~自动机级别和3）~状态级别。其中，只有状态级的并行性是固有的自动机，而其他两个层次的并行性依赖于自动机和输入流的数量进行处理。随着GPU资源的增加，并行性受限的自动机处理任务可能未充分利用GPU计算资源。为此，我们提出AsyncAP，一个低开销的方法，优化可扩展性和吞吐量。我们的见解是，大多数自动机处理任务有一个额外的来源，并行性起源于输入符号，这是以前没有利用。使与自动机任务相关联的匹配过程异步，即，并行GPU线程开始处理来自不同输入位置的输入流，而不是串行处理它，显著提高吞吐量并随输入长度而扩展。当任务没有足够的并行性来利用所有GPU内核时，对12个评估应用程序的详细评估表明，AsyncAP平均比最先进的GPU自动机处理引擎实现了高达58倍的加速比。当任务有足够的并行性来利用GPU内核时，AsyncAP仍然可以实现2.4倍的加速比。
Finite-state automata serve as compute kernels for many application domains such as pattern matching and data analytics. Existing approaches on GPUs exploit three levels of parallelism in automata processing tasks: 1)~input stream level, 2)~automaton-level and 3)~state-level. Among these, only state-level parallelism is intrinsic to automata while the other two levels of parallelism depend on the number of automata and input streams to be processed. As GPU resources increase, a parallelism-limited automata processing task can underutilize GPU compute resources. To this end, we propose AsyncAP, a low-overhead approach that optimizes for both scalability and throughput. Our insight is that most automata processing tasks have an additional source of parallelism originating from the input symbols which has not been leveraged before. Making the matching process associated with the automata tasks asynchronous, i.e., parallel GPU threads start processing an input stream from different input locations instead of processing it serially, improves throughput significantly and scales with input length. When the task does not have enough parallelism to utilize all the GPU cores, detailed evaluation across 12 evaluated applications shows that AsyncAP achieves up to 58× speedup on average over the state-of-the-art GPU automata processing engine. When the tasks have enough parallelism to utilize GPU cores, AsyncAP still achieves 2.4× speedup.