cuThomasBatch and cuThomasVBatch, CUDA Routines to compute batch of tridiagonal systems on NVIDIA GPUs
cuThomasBatch and cuThomasVBatch, CUDA Routines to compute batch of tridiagonal systems on NVIDIA GPUs
复制标题
DOI：
10.1002/cpe.4909
复制
发表时间：
2018-12-25
影响因子：
2
通讯作者：
Pena, Antonio J.
中科院分区：
文献类型：
--
作者：
Valero-Lara, Pedro;Martinez-Perez, Ivan;Pena, Antonio J.
在许多应用中，三对角线系统的求解是计算成本最高的部分之一，因此许多研究都探索了使用NVIDIA gpu来加速这种计算。然而，这些研究主要集中在使用并行算法来计算此类系统，这种算法可以有效地利用共享内存，并且在系统数量较少的情况下会使gpu容量饱和，在处理系统数量较多的情况下，可扩展性较差。cuSPARSE NVIDIA包中的gtsvStridedBatch例程就是这些示例之一，本文将其用作参考。我们提出了一种基于Thomas算法的新实现（cuThomasBatch）。与其他算法不同，Thomas算法是顺序的，因此实现了一种粗粒度的方法，其中一个CUDA线程解决了一个完整的三对角系统，而不是像gtsvStridedBatch那样一个CUDA块。为了使用这种方法实现良好的可伸缩性，有必要对输入存储在内存中的方式进行转换，以利用合并（连续的线程访问连续的内存位置）。详细探讨了有关数据转换的不同变体。我们还探讨了可变批处理的一些变体，当批处理的系统大小不同时（cuThomasVBatch）。本研究给出的结果证明，在这项工作中进行的实现能够击败参考代码，使用最新的NVIDIA GPU架构Pascal P100，速度可达5倍（双精度）和6倍（单精度）。
The solving of tridiagonal systems is one of the most computationally expensive parts in many applications, so that multiple studies have explored the use of NVIDIA GPUs to accelerate such computation. However, these studies have mainly focused on using parallel algorithms to compute such systems, which can efficiently exploit the shared memory and are able to saturate the GPUs capacity with a low number of systems, presenting a poor scalability when dealing with a relatively high number of systems. The gtsvStridedBatch routine in the cuSPARSE NVIDIA package is one of these examples, which is used as reference in this article. We propose a new implementation (cuThomasBatch) based on the Thomas algorithm. Unlike other algorithms, the Thomas algorithm is sequential, and so a coarse-grained approach is implemented where one CUDA thread solves a complete tridiagonal system instead of one CUDA block as in gtsvStridedBatch. To achieve a good scalability using this approach, it is necessary to carry out a transformation in the way that the inputs are stored in memory to exploit coalescence (contiguous threads access to contiguous memory locations). Different variants regarding the transformation of the data are explored in detail. We also explore some variants for the case of variable batch, when the size of the systems of the batch has different size (cuThomasVBatch). The results given in this study prove that the implementations carried out in this work are able to beat the reference code, being up to 5x (in double precision) and 6x (in single precision) faster using the latest NVIDIA GPU architecture, the Pascal P100.