GTaP: A GPU-Resident Fork-Join Task-Parallel System with a Pragma-Based Interface

Abstract

Graphics Processing Units (GPUs) excel at regular data-parallel workloads. In contrast, many irregular workloads are naturally expressed using fork-join task parallelism, which is well supported on CPUs but remains difficult to execute efficiently on GPUs. We present GTaP, a task-parallel programming system that executes fine-grained fork-join entirely within a persistent GPU kernel. Programmers annotate fork and join points in task functions with OpenMP-like pragmas, and a Clang extension generates the suspension and resumption logic required at joins. GTaP exposes a block mode, which maps each task to one thread block for cooperative parallel execution within the task, and a thread mode, which maps each task to one GPU thread for finer-grained parallelism. Scheduling is fully GPU-resident via work stealing; Divergence-Aware Queueing (DAQ) optionally partitions task queues using user-defined criteria to reduce warp divergence from heterogeneous control flow. Across microbenchmarks, GTaP outperforms a prior GPU implementation of fine-grained fork-join by up to two orders of magnitude, and matches or exceeds OpenMP and OpenCilk on 72 CPU cores for compute-intensive workloads. On real-world workloads, GTaP's pragma-annotated recursive implementations run up to $1.6\times$ faster than a hand-written GPU traversal for FMM dual-tree traversal, and outperform a state-of-the-art specialized kernel for $k$-clique counting by up to $5.2\times$ when search-tree skew causes load imbalance under static work assignment.

12 pages, 8 figures. Substantially revised version with an updated programming interface, runtime design, and expanded evaluation