As a fundamental computation model, finite-state machine (FSM) has been used in a wide range of data-intensive applications, including malware detection, bioinformatics, semi-structured data analytics, natural language processing and even machine learning. However, FSM execution is known to be “embarrassingly sequential” due to the state dependences among transitions. Current studies find that speculation is a promising solution to address the inherent dependencies in FSM computations and thus enables scalable FSM parallelization.
This talk will firstly introduce the fundamental scalability bottleneck in the current FSM parallelization, and then an aggressive speculation, a generalized speculation model that allows a speculated state to be validated against the result from another speculation, is proposed to address the scalability limitations. Finally, this talk will discuss the possibility to enlarge the applicability of the proposed approach and go beyond the FSM-based computations.