Kokkos::Graph: A Performance-Portable Abstraction for Directed Acyclic Graphs of Asynchronous Operations

Workloads structured as directed acyclic graphs (DAGs) of asynchronous operations arise in many high-performance computing applications. This paper presents Kokkos::Graph, the graph abstraction of the Kokkos performance portability library for expressing and orchestrating the execution of such DAG-structured workloads. It represents a static DAG defined ahead of submission and maps to corresponding vendor graph implementations on the CUDA, HIP and SYCL backends. Although their definition and instantiation incur an upfront cost, these backend graphs are designed so that they may be repeatedly submitted for execution with lower scheduling overhead than enqueueing the operations individually onto streams or queues, thus allowing the one-time costs to be amortised over multiple submissions. After contrasting the graph abstraction with the well-established execution space abstraction, this paper describes recent improvements and extensions to Kokkos::Graph that resolve underspecification issues in its execution and data-lifetime semantics and broaden its feature set. Then, the performance is compared across backends using two metrics: the asymptotic speedup in the limit as the one-time costs are fully amortised, and the break-even number of submissions. The asymptotic speedup is consistently greater than one across the full set of benchmarks only on the CUDA backend, although multiple submissions are still needed to reach the break-even point. On CUDA, HIP and SYCL alike, the asymptotic speedup tends to one as the work per operation grows and the scheduling overhead thus becomes negligible relative to the operation execution time. Finally, a concrete application to finite element assembly highlights several code-design benefits of adopting Kokkos::Graph.