A Highly Scalable TDMA for GPUs and Its Application to Flow Solver Optimization
Seungchan Kim, Jihoo Kim, Sanghyun Ha, Donghyun You · 2025
Read A Highly Scalable TDMA for GPUs and Its Application to Flow Solver Optimization by Seungchan Kim, Jihoo Kim, Sanghyun Ha, Donghyun You (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-03933.txt.
Introduction
Seungchan Kim and three co-authors study a scalable algorithm for solving tridiagonal systems on many graphics processors in a 2025 research paper. The tridiagonal matrix algorithm is a workhorse of flow simulation, but its sequential structure bottlenecks multi-GPU scaling. Their Pipelined-TDMA overlaps communication with computation and runs kernels concurrently, hiding the non-scalable stages behind scalable ones.
Batch size is tuned carefully: larger batches raise throughput per system, while oversized batches starve the pipeline. Tests reach sixty-four NVIDIA A100 processors with a billion grid cells per device. Weak scaling stays ideal up to that size, and strong scaling keeps about three quarters of ideal performance on a four-billion-cell problem. Integrated into a fractional-step flow solver, the method removes the Poisson solver's bottleneck. In a nine-billion-cell simulation, that component speeds up more than fourfold, lifting the flow solver by about thirty percent.
Catalog record
| CREATOR | Seungchan Kim, Jihoo Kim, Sanghyun Ha, Donghyun You |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 88 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-03933
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A Highly Scalable TDMA for GPUs and Its Application to Flow Solver Optimization Seungchan Kim, Jihoo Kim, Sanghyun Ha, Donghyun You Abstract A tridiagonal matrix algorithm (TDMA), Pipelined-TDMA , is developed for multi-GPU systems to resolve the scalability bottlenecks caused by the sequential structure of conventional divide-and-conquer TDMA. The proposed method pipelines multiple tridiagonal systems, overlapping communication with computation and executing GPU kernels concurrently to hide non-scalable stages behind scalable compute stages. To maximize performance, the batch size is optimized to strike a balance between GPU occupancy and pipeline efficiency: larger batches improve throughput for solving tridiagonal systems, while excessively large batches reduce pipeline utilization. Performance evaluations on up to 64 NVIDIA A100 GPUs using a one-dimensional (1D) slab-type domain decomposition confirm that, except for the terminal phase of the pipeline, the proposed method successfully hides most of the non-scalable execution time—specifically inter-GPU communication and low-occupancy computation. The solver achieves ideal weak scaling up to 64 GPUs with one billion grid cells per GPU and reaches 74.7% of ideal performance in strong scaling tests for a 4-billion-cell problem, relative to a 4-GPU baseline. The optimized TDMA is integrated into a ADI-based fractional-step method to remove the scalability bottleneck in the Poisson solver of the flow solver by Ha et al. 2021 . In a 9-billion-cell simulation on 64 GPUs, the TDMA component in the Poisson solver is accelerated by 4.37×, contributing to a 1.31× overall speedup of the complete flow solver. 1. Introduction Tridiagonal matrix (TDM) systems serve as a key component in numerical simulations of fluid flow, because they enable the use of implicit schemes for stable solutions while maintaining excellent computational efficiency. In particular, the Thomas algorithm ( Thomas 1949 ) , a widely used sequential tridiagonal matrix algorithm (TDMA), solves a TDM system of size n with only \mathcal{O}(n) operations, making it highly efficient. The efficiency of TDMA is especially valuable in semi-implicit fractional-step methods with second-order spatial discretization in finite-difference methods (FDM) for incompressible flow simulations, as solving multiple TDM systems constitutes the majority of the total computational cost. Since the pioneering work of Kim and Moin 1985 , such methods have been widely adopted to simulate incompressible flows ( Le and Moin 1990 ; Hahn et al. 2002 ; Abe et al. 2001 ) . These approaches consist of two main steps—solving the momentum and Poisson equations—both of which involve TDM systems that dominate computational cost. In the momentum equations, implicit schemes such as the alternating direction implicit (ADI) method introduce TDM systems through implicit treatment of viscous terms. Similarly, FFT-based Poisson solvers require TDM systems along specific directions and these TDM systems contribute significantly to the total execution time. For this reason, optimizing TDMA is critical for achieving high-performance incompressible flow simulations. Despite the efficiency of the Thomas algorithm, a parallel TDMA tailored to massively parallel architectures is crucial for achieving high performance on GPU systems. There has been extensive research focused on developing parallel TDMAs even before the advent of GPUs ( Hockney 1965 ; Stone 1973 ; Hockney and Jesshope 1981 ; Wang 1981 ; Sun et al. 1989 ; Mehrmann 1993 ; Mattor et al. 1995 ; Polizzi and Sameh 2007 ) . By leveraging two of these parallel TDMAs—parallel cyclic reduction (PCR) ( Hockney and Jesshope 1981 ) and cyclic reduction (CR) ( Hockney 1965 ) — Zhang et al. 2010 proposed a hybrid CR–PCR method, which proves highly effective on a single GPU. The PCR phase takes advantage of CUDA’s fast on-chip shared memory, minimizing memory access latency and boosting throughput. Building on this approach, NVIDIA provides a built-in function, cusparseDgtsv2 , which solves a TDM system on a single GPU using the hybrid CR–PCR method. However, the library does not support solving each TDM system across multiple GPUs. However, TDM systems can be solved in multi-GPU systems, even when the data of each TDM system are distributed across multiple GPUs. In a one-dimensional (1D) slab-type decomposition along the y -direction, where the TDM systems are also aligned in the same direction (see Fig. 1(c) ), the data within each TDM system are distributed across multiple GPUs (see Fig. 1(f) ), making it impossible to solve a complete TDM system on a single GPU. A domain transpose is a commonly used solution that redistributes the data, ensuring that each TDM system becomes fully localized within a single GPU. This data rearrangement strategy is also widely adopted in FFT-based Poisson solvers and has been implemented in both GPU- and CPU-based flow solvers such as ( Zhu et al. 2018 ; Costa et al. 2021 ; Lee et al. 2010 ; Lee et al. 2013 ) . As demonstrated by Zhu et al. 2018 , this approach achieves good scalability up to thousands of GPUs when using a 2D pencil-type decomposition. However, these approaches require all-to-all communication for the domain transpose, and these solvers consistently report that this communication overhead remains a major bottleneck in the overall runtime. (a) x direction TDM sytems (b) z direction TDM sytems (c) y direction TDM sytems Figure 1 : 1D slab-type decomposition into four subdomains along the y direction. The alignment direction of the tridiagonal systems is (a) x , (b) y , and (c) z . (d) x direction TDM sytems (e) z direction TDM sytems (f) y direction TDM sytems Figure 2 : Workload distribution of tridiagonal matrix systems when using four GPUs. When the TDM systems are aligned in the z - or x -direction, the matrix systems can be evenly distributed across the GPUs, as illustrated in (a) and (b). In contrast, when the data in TDM system are aligned in the y -direction, all four GPUs must cooperate to solve each TDM system, as shown in (c). Another approach to implementing TDMA on multi-GPU systems is through divide-and-conquer methods. Instead of rearranging the TDM system via global transpose, divide-and-conquer methods partition a TDM system into smaller sub-systems and distribute the reduced workload across multiple GPUs. In multi-GPU implementations of the divide-and-conquer method for parallel TDMA, each processor is mapped to an entire GPU, in contrast to CPU-based implementations, where processors are mapped to CPU cores, or single-GPU implementations, where they are mapped to threads or warps. Due to this distinct characteristic, although most parallel TDMA algorithms fall under the divide-and-conquer category, only a subset of these methods ( Sun et al. 1989 ; Mattor et al. 1995 ; Polizzi and Sameh 2007 , e.g.,) has been adopted for multi-GPU implementations, as seen in both standalone TDMA solvers ( Chang et al. 2012 ; Yang et al. 2023a ) and integrated flow solvers ( Ha et al. 2021 ) . Due to this distinct characteristic, although most parallel TDMA algorithms fall under the divide-and-conquer category, only a some of these methods ( Sun et al. 1989 ; Mattor et al. 1995 ; Polizzi and Sameh 2007 , e.g.,) has been adopted for multi-GPU implementations, as seen in both standalone TDMA solvers ( Chang et al. 2012 ; Yang et al. 2023a ) and integrated flow solvers ( Ha et al. 2021 ) . This approach exhibits high performance by eliminating the need for global all-to-all communication. However, the scalability of