一句话：提出路径融合与高阶推测，以提升不利 FSM 及输入条件下的并行化可扩展性。
有限状态机（FSM）是许多应用的基础计算模型，但其转移间存在状态依赖，常被视为“令人尴尬的串行”负载。现有枚举式或推测式并行化方案的效果高度依赖 FSM 及其输入的性质：前者需维护多条执行路径而产生开销，后者在误推测情况下需串行重处理，均可严重损害可扩展性。针对该问题，论文提出路径融合（path fusion）与高阶推测（higher-order speculation）两种技术，旨在突破不利 FSM/输入下的并行化瓶颈。摘要未报告具体实验与加速数据，但核心贡献是给出可扩展的 FSM 并行化新路径。
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.
@inproceedings{paperbot6150,
title = {Scalable FSM parallelization via path fusion and higher-order speculation},
author = {Junqiao Qiu and Xiaofan Sun and Amir Hossein Nodehi Sabet and Zhijia Zhao},
booktitle = {ASPLOS},
year = {2021},
doi = {10.1145/3445814.3446705}
}