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

基于有限状态机（FSM）的计算在各种重要应用中发挥着关键作用，从网络安全和数据分析到软件工程和硬件设计。由于数据量的增长和计算机处理能力的限制，目前FSM的效率受到很大的限制，需要一个新的效率优化维度。本计画提出一种新的架构，以提高gpu上基于fsm的计算效率。在提出的框架中开发的GPU加速和推测并行化的组合显示出提高FSM计算性能的希望，并呈现出优化更一般的非FSM计算的潜力。本研究探讨如何建立高并行GPU架构与FSM计算之间的协同。其关键思想是探索并行性的多个维度，以提高计算利用率并减少数据移动开销。此外，本研究设计并集成了先进的推测并行化到FSM计算中。先进的推测并行化不仅可以在不同的fsm上实现更有效的预测器，还可以提供高效的推测线程调度。所有这些优化都将被构建到一个框架中，该框架进一步探索不同目标之间的权衡，并根据给定的目标自动优化应用程序配置。最后，本研究旨在扩大预期结果的适用性，并对不规则计算的计算效率的新维度以及与推测并行化相关的应用进行了初步探索。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.