在GPU上推进矩阵运算，以实现高性能和高效利用内存的自动机处理

《ACM Transactions on Architecture and Code Optimization》：Advancing Matrix Operations for High-Performance and Memory-Efficient Automata Processing on GPUs

有限状态自动机（FSA）在高效计算中面临内存与计算瓶颈，本研究提出GPU加速方案：通过矩阵去重、交错重编号和状态缓存优化，实现6.54倍性能提升，内存占用低于2%。

　　

摘要

有限状态自动机在模式匹配和数据分析等众多领域中至关重要，这些领域对高吞吐量有严格要求。最近的研究探索了将自动机执行过程表示为矩阵代数，并利用CPU的BLAS（基本线性代数子程序）库。尽管这种方法具有潜力，但存在内存使用、数据局部性以及冗余计算等方面的瓶颈。本研究系统地识别了这些瓶颈，并针对它们开发了特定的优化措施。

由于GPU具有强大的计算能力和广泛的可用性，我们重点关注GPU。为了解决这些挑战，我们提出了三种关键技术来提高计算和内存效率：（1）通过消除转移矩阵中的重复项来减少内存使用；（2）通过交错重新编号状态来提高GPU线程的利用率；（3）通过缓存状态向量来消除冗余计算。详细评估表明，所提出的解决方案在性能上可与基于GPU的自动机引擎相媲美（最高提速达6.54倍），同时其内存占用量不到后者的2%；在处理自动机相关工作负载时，其性能甚至优于最先进的领域专用加速器（最高提速达965倍）。