Enabling Scalability-Sensitive Speculative Parallelization for FSM Computations

Abstract

In this work, we conduct a systematic scalability analysis for speculative FSM parallelization. Unlike many other parallelizations which can be modeled by the classic Amdahl’s law or its simple extensions, the scalability of speculative FSM parallelization is challenging to analyze due to the non-deterministic nature of speculation and the cost variations of misspeculation. To address these challenges, this work introduces a spectrum of scalability models that are customized to the properties of specific FSMs and the underlying architecture. ŒThe models, for the first time, precisely capture the scalability of speculative parallelization for different FSM computations, and clearly show the existence of a “sweet spot” in terms of the number of cores.