Exploiting Task-Based Parallelism for the Red-Black Gauss-Seidel Method on 2D Grids

Jul 16, 2026

Gauss–Seidel is an established iterative method for solving linear systems, and multicoloring is commonly used to increase parallelism in iterative solvers. However, multi-color Gauss–Seidel combined with conventional divide-and-conquer parallelization can suffer from global synchronization overheads and load imbalance. This work implements red–black Gauss–Seidel using two task-based programming models and compares them with a classical divide-and-conquer implementation, using the 2D Poisson equation as a benchmark.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages9

Reading Time23 min

Introduction

Background: parallel performance and synchronization

Divide-and-conquer vs task-based models

Motivation: asynchronicity and heterogeneity

Benchmark and evaluation setup

arXiv :2607 .0 1735v 1 [ cs .DC] 2 Jul 2026 Exploiting Task-Based Parallelism for the Red-Black Gauss-Seidel Method on 2D Grids Shiting Long 1, ∗ , Gustavo Ramirez-Hidalgo2,, Andreas Frommer3,, and Dirk Pleiter 1,4, 1 KTH Royal Institute of Technology 2 Forschungszentrum Jülich GmbH 3 Bergische Universität Wuppertal 4 University of Groningen Gauss–Seidel is a well-established iterative method for the solution of linear systems, and multicoloring has been widely used to increase parallelism in iterative solution techniques. Implementing multi-color Gauss–Seidel with conventional divideand-conquer parallelization strategies, however, may be inefficient due to global synchronization requirements and load imbalances. Task-based programming models can mitigate these issues by enabling fine-grained parallelism, removing global barriers and allowing updates of different colors to partially overlap in time. In this work, we implement the red–black Gauss–Seidel method using two task-based programming models and compare them with a classical divide-and-conquer parallel implementation to evaluate the impact of fine-grained parallelism on execution efficiency. The red–black scheme serves as a representative example, as task-based approaches naturally extend to more general multi-color schemes arising from unstructured grids and wider stencils. Using the solve of the 2D Poisson equation as benchmark, our results show that task-based implementations can achieve performance comparable to conventional divide-and-conquer parallelization while providing greater resilience to hardware-level asynchronicity. Copyright line will be provided by the publisher 1 Introduction Contemporary performance improvements are increasingly driven by parallel computing rather than higher CPU clock frequencies. As a result, achieving better performance depends on decomposing workloads into concurrent tasks, enabling efficient utilization of hardware resources and translating computational capacity into measurable speedups. Programmers are therefore required to exploit the performance potential of modern many-core processors through nodelevel and/or thread-level parallelism. Since parallelization cannot be handled entirely by compilers, applications must be adapted to these architectures by explicitly defining task granularity for distributing computation across cores, as well as synchronization mechanisms to ensure data consistency among parallel tasks. The de facto parallelization approach for numerical applications is to decompose or transform the problem into smaller partitions, where solving each partition constitutes a task that can be executed in parallel with the others. This divide-andconquer strategy maps naturally onto the fork-join multithreading programming model, enabling efficient utilization of manycore systems and achieving parallel speedup. The divide-and-conquer strategy is not suitable for all algorithms. One example is block LU factorization, where the number of concurrently executable block updates varies throughout execution. When using a fork-join model, threads may spend significant time waiting at synchronization barriers, resulting in hardware underutilization. In such cases, a programming model that supports asynchronous execution and dynamic work scheduling becomes essential. Furthermore, modern computing systems are increasingly heterogeneous, typically combining CPUs with accelerators such as GPUs. A programming model that enables workloads to be efficiently distributed across different hardware architectures is therefore important. Task-based programming models address these challenges by embedding dynamic schedulers within the runtime system, allowing tasks, i.e., units of work that can be executed in parallel, to be automatically mapped onto the underlying hardware resources. Such models have proven effective in addressing both asynchronous scheduling [3, 14] and heterogeneous scheduling [1, 2] challen

FAQs

为什么需要用任务式并行模型而不是传统的多色 Gauss–Seidel 分治并行？

传统分治并行会带来全局同步需求并可能出现负载不均，降低效率。任务式模型通过去除全局障碍并允许不同颜色更新部分时间重叠来缓解这些问题。

本文选择什么问题作为基准来评估红黑 Gauss–Seidel 的并行效率？

使用二维泊松方程求解作为基准，并采用红黑 Gauss–Seidel 方法来代表一类常见的模板（stencil）应用。

本文用哪些任务式编程模型与传统 fork-join 实现进行比较？

本文使用两个任务式模型：在 GCC 工具链中实现的 OpenMP，以及 OmpSs-2；并与基于 OpenMP parallel for 构造的传统 fork-join 实现进行对比。

Jul 16, 2026

Upload by Emma Wilson