Predictable GPUs for Safety-critical Systems

@article{klashtorny_25_tecs,
  author = {Artem Klashtorny and Mahesh Tripunitara and Hiren Patel},
  journal = {ACM Transactions on Embedded Computing Systems},
  volume = {24},
  number = {6},
  pages = {1--25},
  publisher = {ACM},
  month = {oct},
  doi = {10.1145/3769118},
  title = {{Optimal Split Point Placement for Predictable GPU Wavefront Splitting}},
  year = {2025}
}

Predictable wavefront splitting (PWS) is an optimization technique for graphics processing units (GPUs) to address the performance and worst-case execution time (WCET) impacts of branch divergence. PWS relies on manual annotation by the GPU programmer; these choices affect the resulting WCET. This work automates this process with two key approaches. First, we formulate the optimal annotation as an integer quadratic programming (IQP) problem such that the solution guarantees the lowest WCET. Second, we show that the problem can be solved with an optimal polynomial-time dynamic programming algorithm that achieves the same solutions as the IQP. We implement our algorithm in a compiler flow for an AMD GPU, and we deploy the annotated executable on a gem5 micro-architectural implementation of the AMD GCN3 GPU. We evaluate our implementation on a benchmark suite provided by AMD and supplement it with an extensive set of synthetic benchmarks. Our evaluation shows that these two approaches are able to reduce the WCET by between 13% and 31% compared to five baseline algorithms.

@inproceedings{klashtorny_24_optpws,
  author = {Artem Klashtorny and Mahesh Tripunitara and Hiren Patel},
  booktitle = {{proceedings of IEEE Design Automation and Test in Europe (DATE)}},
  pages = {1–-6},
  numpages = {6},
  publisher = {IEEE},
  month = {mar},
  doi = {10.23919/DATE58400.2024.10546600},
  title = {{A Compiler Phase to Optimally Split GPU Wavefronts for
           Safety-critical Systems}},
  year = {2024}
}

We present a compiler phase for GPUs enabled with predictable wavefront splitting (PWSG) that implements an optimal algorithm to split diverging GPU wavefronts into separate scheduleable entities. This algorithm selects branches in the GPU kernel that guarantee the lowest worst-case execution time (WCET) for the kernel. We implement our algorithm in a compiler flow for an AMD GPU, and we deploy the resulting binary on a gem5 micro-architectural implementation of the AMD GCN3 GPU. We evaluate our implementation on an extensive set of synthetic benchmarks. Our experiments show that by automatically selecting points in the GPU kernel to split wavefronts, we are able to reduce the WCET ranging from 34% to 52% reduction compared to five alternative approaches.

@article{klashtorny_23_pws,
  author = {Klashtorny, Artem and Wu, Zhuanhao and Kaushik, Anirudh Mohan and
            Patel, Hiren},
  title = {Predictable GPU Wavefront Splitting for Safety-Critical Systems},
  year = {2023},
  issue_date = {October 2023},
  publisher = {Association for Computing Machinery},
  address = {New York, NY, USA},
  pages = {1--25},
  volume = {22},
  number = {5s},
  issn = {1539-9087},
  url = {https://doi.org/10.1145/3609102},
  doi = {10.1145/3609102},
  journal = {ACM Trans. Embed. Comput. Syst.},
  month = {sep},
  articleno = {107},
  numpages = {25},
  keywords = {safety-critical systems, GPU}
}

We present a predictable wavefront splitting (PWS) technique for graphics processing units (GPUs). PWS improves the performance of GPU applications by reducing the impact of branch divergence while ensuring that worst-case execution time (WCET) estimates can be computed. This makes PWS an appropriate technique to use in safety-critical applications, such as autonomous driving systems, avionics, and space, that require strict temporal guarantees. In developing PWS on an AMD-based GPU, we propose microarchitectural enhancements to the GPU, and a compiler pass that eliminates branch serializations to reduce the WCET of a wavefront. Our analysis of PWS exhibits a performance improvement of 11% over existing architectures with a lower WCET than prior works in wavefront splitting.