License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.WCET.2023.1
URN: urn:nbn:de:0030-drops-184303
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18430/
Go to the corresponding OASIcs Volume Portal

Jeanmougin, Louison ; Sotin, Pascal ; Rochange, Christine ; Carle, Thomas

Warp-Level CFG Construction for GPU Kernel WCET Analysis

pdf-format:
OASIcs-WCET-2023-1.pdf (0.6 MB)

Abstract

We present an abstract interpretation technique to automatically build a Control Flow Graph (CFG) representation of the execution of a GPU kernel. GPUs implement an inherently parallel execution model, in which threads are grouped within so-called warps that execute in lockstep. This execution model enables the representation of the execution of the threads of a warp as a single CFG. However, thread divergence may appear within a warp and its effect must be captured explicitly within the CFG. Our method builds the CFG of a warp by applying abstract interpretation on the assembly (Nvidia SASS) code of a kernel, and by maintaining an abstract representation of which threads within the warp agree on which values. This allows the method to detect precisely the points in the program where thread divergence may occur, and avoid spurious reactivation edges in the CFG. We apply our technique on benchmark kernels as a proof-of-concept, and generate IPET systems using the resulting CFGs.

BibTeX - Entry

@InProceedings{jeanmougin_et_al:OASIcs.WCET.2023.1,
  author =	{Jeanmougin, Louison and Sotin, Pascal and Rochange, Christine and Carle, Thomas},
  title =	{{Warp-Level CFG Construction for GPU Kernel WCET Analysis}},
  booktitle =	{21th International Workshop on Worst-Case Execution Time Analysis (WCET 2023)},
  pages =	{1:1--1:13},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-293-8},
  ISSN =	{2190-6807},
  year =	{2023},
  volume =	{114},
  editor =	{W\"{a}gemann, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/18430},
  URN =		{urn:nbn:de:0030-drops-184303},
  doi =		{10.4230/OASIcs.WCET.2023.1},
  annote =	{Keywords: Graphical Processing Unit (GPU), Control Flow Graphs (CFG), Worst-Case Execution Time (WCET), Program analysis}
}

Keywords: Graphical Processing Unit (GPU), Control Flow Graphs (CFG), Worst-Case Execution Time (WCET), Program analysis
Collection: 21th International Workshop on Worst-Case Execution Time Analysis (WCET 2023)
Issue Date: 2023
Date of publication: 26.07.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI