MicroSpec: Speculation-centric fine-grained parallelization for FSM computations
MicroSpec: Speculation-centric fine-grained parallelization for FSM computations
复制标题
MicroSpec：用于 FSM 计算的以推测为中心的细粒度并行化
DOI：
10.1145/2967938.2967965
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Bin Ren
中科院分区：
文献类型：
--
作者：
Junqiao Qiu;Zhijia Zhao;Bin Ren
有限状态机器（FSM）是在许多应用程序中扮演重要角色的基本计算模型。启用有效的并行FSM执行对于这些应用程序的性能至关重要。但是，由于它们在计算的每个步骤中发生的固有数据依赖性，因此它们的并行化非常具有挑战性。 FSM并行化的现有努力要么探索粗粒的投机并行性，要么利用并行前缀。前者忽略了现代处理器（例如ILP或SIMD并行性）上普遍存在的细颗粒硬件并行性，而后者则限制了细颗粒并行性的好处，主要是在国家枚举中。这项工作提出了Microspec，这是一组平行化技术，该技术首次将细粒的投机并行性暴露于FSM计算中。基于对三种类型的平行性分析，在细粒度水平上，Microspec包括四种细粒度投机 - 平行化方法的列表以及面向投机的数据转换。大量Realworld FSM基准测试的实验表明，Microspec在最先进的情况下取得了重大的性能提高。
Finite state machines (FSMs) are basic computation models that play essential roles in many applications. Enabling efficient parallel FSM execution is critical to the performance of these applications. However, they are very challenging to parallelize due to their inherent data dependencies that occur at each step of computations. Existing efforts on FSM parallelization either explore coarse-grained speculative parallelism or leverage parallel prefixsum. The former ignores prevalent fine-grained hardware parallelism on modern processors (such as ILP or SIMD parallelism) while the latter limits the benefits of fine-grained parallelism mainly to state enumeration. This work presents MicroSpec, a set of parallelization techniques that, for the first time, expose fine-grained speculative parallelism to FSM computations. Based on a rigorous analysis of three types of parallelism at fine-grained level, MicroSpec consists of a list of four fine-grained speculative parallelization approaches along with a speculation-oriented data transformation. Experiments on a large set of realworld FSM benchmarks show that MicroSpec achieves substantial performance improvement over the state-of-the-art.