利用ngAP在GPU上实现可扩展且非阻塞的自动机处理

《ACM Transactions on Computer Systems》：Towards Scalable and Non-blocking Automata Processing on GPUs with ngAP

有限自动机在GPU上的并行处理面临线程利用率低、重复计算和时空局部性不足三大挑战。本文提出非阻塞自动机处理方法，通过预取计算、记忆化查询、私有化计算和去重编码四项优化，实验表明在20个应用中平均性能提升9.5倍，最高达1613倍。

　　

摘要

有限自动机在各种应用中充当计算核心。尽管GPU提供了强大的并行处理能力，但由于三个挑战，其在自动机处理方面的潜力仍未得到充分利用：(1) 并行性不足导致线程利用率低下；(2) 由于许多状态对应相同的符号，从而产生重复计算；(3) 由于线程和状态之间的频繁重新映射以及不规则的内存访问，时间和空间局部性未能得到有效利用。我们发现，逐个符号地处理自动机会使执行过程串行化，从而限制了系统的可扩展性。为了解决这个问题，我们提出了非阻塞自动机处理方法（Non-blocking Automata Processing），该方法支持不同输入符号的并行处理，并包含以下几种优化措施：(1) 预取计算结果，通过允许多个符号同时被处理来提高线程利用率；(2) 通过查找表消除重复计算；(3) 将计算过程私有化，以保持线程状态映射并提升时间局部性；(4) 去重匹配集并编码常见的自动机模式，以减少内存使用并提高空间局部性。我们在20个应用中的实验评估表明，我们的方法相比现有的GPU自动机处理引擎平均性能提升了9.5倍，最高可达1,613倍。