CRII: SHF: GPU-accelerated FSM computations with advanced speculation

Finite State Machine (FSM)-based computations have played critical roles in a variety of important applications, ranging from cyber security and data analytics to software engineering and hardware design. Due to the growing data volumes and limitations on computer processing power, nowadays FSM efficiency is greatly constrained, and a new dimension of efficiency optimization is desired.

This project proposes a novel framework to enhance the computing efficiency of FSM-based computations on GPUs. The combination of GPU acceleration and speculative parallelization developed in the proposed framework shows promise for boosting performance of FSM computations and presents the potential to optimize even more general non-FSM computations.

This research investigates how to build up the synergy between highly-parallel GPU architectures and FSM computations. The key idea is exploring multiple dimensions of parallelism for increasing compute utilization as well as reducing data-movement overheads. Additionally, this research designs and integrates advanced speculative parallelization into FSM computations.

The advanced speculative parallelization not only enables more effective predictors on different FSMs, it also provides efficient speculative-thread scheduling. All these optimizations will be built into a framework that further explores the trade-offs between different objectives and automatically optimizes application configurations based on the given objectives.

Finally, this research seeks to enlarge the applicability of the envisioned results, and it brings the preliminary exploration about a new dimension of computing efficiency for irregular computations as well as applications associated with speculative parallelization.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.