Scaling out speculative execution of finite-state machines with parallel merge
Scaling out speculative execution of finite-state machines with parallel merge
复制标题
通过并行合并横向扩展有限状态机的推测执行
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
G. Agrawal
中科院分区：
文献类型：
--
作者：
Yang Xia;Peng Jiang;G. Agrawal
有限状态机（FSM）是许多重要应用的关键组件，如霍夫曼解码、正则表达式匹配和HTML标记化。由于其固有的依赖性和不可预测的内存访问模式，FSM计算被认为是极其难以并行化的。因此，已经进行了大量的研究工作来加速FSM的计算。尽管它们在多核机器上取得了很好的性能结果，但这些方法在新兴的多核架构（如gpu）上是不可扩展的。通过实验，我们指出了这些方法固有的顺序合并是在gpu上实现可扩展性的瓶颈。然而，与简单的缩减循环不同，FSM计算的并行合并实现通常需要运行时检查和重新执行，这也会影响性能。基于这些观察，我们开发了并行合并技术，以选择有效的运行时检查实现并避免不必要的重新执行。此外，基于GPU的架构特征，我们开发了优化技术来提高性能。我们在一组有代表性的算法上评估我们的并行合并实现。实验结果表明，我们的并行合并实现比相应的顺序合并实现效率高2.02-6.74倍，并且在Nvidia V100 GPU上具有更好的可扩展性。
A finite-state machine (FSM) is a key component for many important applications, such as Huffman decoding, regular expression matching and HTML tokenization. Due to its inherent dependencies and unpredictable memory access pattern, FSM computations are considered to be extremely difficult to parallelize. As such, significant research efforts have been made to accelerate FSM computations. Although they achieve promising performance results on multi-core machines, these methods are not scalable for emerging many-core architectures such as the GPUs. Based on our experiments, we point out that the bottleneck of achieving scalability on GPUs is the sequential merge inherent to these methods. However, unlike the case for simple reduction loops, parallel merge implementations for FSM computations typically require runtime checks and re-executions, which can also impede performance. Based on these observations, we develop parallel merge techniques that select efficient runtime check implementations and avoids unnecessary re-executions. Further, based on GPU architectural features, we develop optimization techniques to improve performance. We evaluate our parallel merge implementations on a set of representative algorithms. Experimental results show that our parallel merge implementations are 2.02-6.74 times more efficient than corresponding sequential merge implementations and achieve better scalability on an Nvidia V100 GPU.