GTaP: A GPU-Resident Fork-Join Task-Parallel Runtime with a Pragma-Based Interface
This work addresses the problem of enabling irregular applications with fork-join control structures to run efficiently on GPUs, offering a novel runtime solution for developers in high-performance computing, though it is incremental in building on existing task-parallel concepts.
The paper tackles the challenge of efficiently supporting fork-join task parallelism on GPUs, which are typically optimized for regular data-parallel workloads, by proposing GTaP, a GPU-resident runtime that outperforms OpenMP on a 72-core CPU in many cases, especially for large problem sizes, and achieves up to a 1.8x speedup on Fibonacci with its Execution-Path-Aware Queueing feature.
Graphics Processing Units (GPUs) excel at regular data-parallel workloads where massive hardware parallelism can be readily exploited. In contrast, many important irregular applications are naturally expressed as task parallelism with a fork-join control structure. While CPU runtimes for fork-join task parallelism are mature, it remains challenging to efficiently support it on GPUs. We propose GTaP, a GPU-resident runtime that supports fork-join task parallelism. GTaP is based on the persistent kernel model, and supports two worker granularities: thread blocks and individual threads. To realize fork-join on GPUs, GTaP represents joins as continuations and executes each task as a state machine that can be split into multiple execution segments. We also extend Clang's frontend with a pragma-based programming model that enables programmers to express fork-join without exposing low-level mechanisms. GTaP employs work stealing for load balancing, providing better scalability than a global-queue approach. For thread-level workers, we further introduce Execution-Path-Aware Queueing (EPAQ), which allows programmers to partition task queues using user-defined criteria, reducing warp divergence caused by mixing heterogeneous control flows within a warp. Across representative irregular applications, GTaP outperforms OpenMP task-parallel execution on a 72-core CPU in many cases, especially for large problem sizes with compute-intensive tasks. We also show that GTaP's design choices outperform naive GPU alternatives. The benefit of EPAQ is workload-dependent: it can improve performance for some benchmarks while having little effect on others; on Fibonacci, EPAQ achieves up to a 1.8$\times$ speedup.