Scalable FSM parallelization via path fusion and higher-order speculation
Scalable FSM parallelization via path fusion and higher-order speculation
复制标题
通过路径融合和高阶推测实现可扩展的 FSM 并行化
DOI：
10.1145/3445814.3446705
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Zhao, Zhijia
中科院分区：
文献类型：
--
作者：
Qiu, Junqiao;Sun, Xiaofan;Sabet, Amir Hossein;Zhao, Zhijia
有限状态机（FSM）是许多应用程序使用的基本计算模型。然而，由于转换之间的状态依赖，FSM的执行众所周知是“令人尴尬的顺序”。现有的解决方案利用枚举或推测并行来打破依赖关系。然而，两种并行化方案的效率在很大程度上取决于FSM及其输入的性质。对于那些表现出不利属性的算法，前者需要维护多条执行路径，而后者则需要在错误推测的情况下进行串行重处理，从而成为瓶颈。无论采用哪种方式，FSM的并行化可伸缩性都会受到严重损害。这项工作用两种新技术解决了上述可伸缩性挑战。首先，针对枚举并行化，提出了路径融合方法。受经典的NFA到DFA转换的启发，它将原始FSM中的状态向量映射到一个新的（融合的）状态。通过这种方式，路径融合可以将多个FSM的执行路径简化为一条路径，从而减少了路径维护的开销。其次，对于推测并行化，本工作引入了高阶推测，以避免验证期间的串行再处理。这是一个广义的推测模型，允许推测状态被推测验证。最后，本文将不同的FSM并行化方案集成到一个框架——boostfsm中，该框架根据FSM的相关属性自动选择最佳方案。使用具有不同特征的真实fsm进行评估表明，在64核机器上，BoostFSM可以将现有推测和枚举并行化方案的平均加速分别从3.1倍和15.4倍提高到25.8倍。
Finite-state machine (FSM) is a fundamental computation model used by many applications. However, FSM execution is known to be “embarrassingly sequential” due to the state dependences among transitions. Existing solutions leverage enumerative or speculative parallelization to break the dependences. However, the efficiency of both parallelization schemes highly depends on the properties of the FSM and its inputs. For those exhibiting unfavorable properties, the former suffers from the overhead of maintaining multiple execution paths, while the latter is bottlenecked by the serial reprocessing among the misspeculation cases. Either way, the FSM parallelization scalability is seriously compromised.This work addresses the above scalability challenges with two novel techniques. First, for enumerative parallelization, it proposespath fusion. Inspired by the classic NFA to DFA conversion, it maps a vector of states in the original FSM to a new (fused) state. In this way, path fusion can reduce multiple FSM execution paths into a single path, minimizing the overhead of path maintenance. Second, for speculative parallelization, this work introduceshigher-order speculationto avoid the serial reprocessing during validations. This is a generalized speculation model that allows speculated states to be validated speculatively. Finally, this work integrates different schemes of FSM parallelization into a framework—BoostFSM, which automatically selects the best based on the relevant properties of the FSM. Evaluation using real-world FSMs with diverse characteristics shows that BoostFSM can raise the average speedup from 3.1× and 15.4× of the existing speculative and enumerative parallelization schemes, respectively, to 25.8× on a 64-core machine.
登录
查看更多内容
DOI：
10.1109/isca.1998.694778
发表时间：
1998-04
期刊：
Proceedings. 25th Annual International Symposium on Computer Architecture (Cat. No.98CB36235)
影响因子：
--
作者：
S. Wallace;B. Calder;D. Tullsen
通讯作者：
S. Wallace;B. Calder;D. Tullsen
为 FSM 计算启用可扩展性敏感的推测并行化
DOI：
10.1145/3079079.3079082
发表时间：
2017
期刊：
Proceedings of the International Conference on Supercomputing
影响因子：
--
作者：
Junqiao Qiu;Zhijia Zhao;Bo Wu;Abhinav Vishnu;S. Song
通讯作者：
S. Song
DOI：
10.1109/ipdps.2015.101
发表时间：
2015-05
期刊：
2015 IEEE International Parallel and Distributed Processing Symposium
影响因子：
--
作者：
Ke Wang;Yanjun Qi;J. J. Fox-J.;Mircea R. Stan;K. Skadron
通讯作者：
Ke Wang;Yanjun Qi;J. J. Fox-J.;Mircea R. Stan;K. Skadron
DOI：
--
发表时间：
2011
期刊：
Conference on Object-Oriented Programming Systems, Languages, and Applications
影响因子：
--
作者：
R. Cledat;T. Kumar;S. Pande
通讯作者：
S. Pande
通过并行合并横向扩展有限状态机的推测执行
DOI：
--
发表时间：
2020
期刊：
ACM SIGPLAN Symposium on Principles & Practice of Parallel Programming
影响因子：
--
作者：
Yang Xia;Peng Jiang;G. Agrawal
通讯作者：
G. Agrawal