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.
From: Yuki Maeda [view email]
[v1]
Tue, 7 Apr 2026 15:11:30 UTC (1,200 KB)
[v2]
Mon, 24 Aug 2026 02:41:43 UTC (523 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。