FSM-Centric Speculative Parallelization for Scalable Data Processing

Parallelism is key for designing and implementing high-performance data analytics on modern processors. However, many data processing routines cannot be executed in parallel, due to the sequential nature of their underlying computation models. This dissertation focuses on an important class of sequential data processing routines that are driven by or can be modeled as finite-state machines (FSMs). It proposes a series of speculation-based parallelization and modeling techniques to improve the parallelism and scalability of FSM-based computations. Moreover, it successfully applies the FSM-based speculative parallelization to non-FSM computations, significantly expanding the applicability of the proposed techniques. More specifically, we first introduce multi-level speculation by integrating the instruction-level and SIMD-level parallelism into the existing multicore-level speculative parallelization. We then systematically model the scalability of speculative FSM parallelization and point out its limitations. To address them, we design two novel optimizations: path fusion and higher-order speculation, which together bring the scalability to another level for FSMs that are conventionally hard to parallelize effectively. Finally, we demonstrate that, with rigorous static analysis, we can precisely model bitstream computations with FSMs, hence solve their parallelization with existing FSM parallelization techniques