MicroSpec: Speculation-Centric Fine-Grained Parallelization for FSM Computations

摘要: 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 However, they very challenging parallelize due their inherent data dependencies occur at each step computations.Existing efforts on parallelization either explore coarse-grained speculative parallelism or leverage prefix- sum. The former ignores prevalent fine-grained hardware modern processors (such as ILP SIMD parallelism) while latter limits benefits mainly enumeration.This work presents MicroSpec, a set techniques that, for first time, expose computations. Based rigorous analysis three types level, MicroSpec consists list four approaches along with speculation-oriented transformation. Experiments large real- world benchmarks show achieves substantial improvement over state-of-the-art.