使用 CUDA 并行化 LSE 求解器

计算科学 算法 并行计算
2021-12-04 07:00:57

我想知道在 CUDA 架构上完全可并行化的方法。我已经实现了 Jacobi 和 Conjugate Gradient 方法,现在我正在考虑 Bi-Conjugate Gradient 方法。我正在使用 cublas 库来简化一些基本的代数运算。有人说 Gauss-Seidel 是半可并行的。我是 CUDA 的新手,所以我无法理解 Cholesky 分解或高斯消除论文中的一些问题,例如:

高斯消除

Cholesky 分解

我无法理解新算法,所以我说我必须使用经典的数值算法(我无法“创建”那种算法),比如。

关键是,是否存在关于这些算法并行化的任何“理论”?因为雅可比并行化和共轭梯度方法对我来说很容易,所以算法内部有一些 saxpy 和 gemv 操作。

例如,在 Cholesky 的情况下,内部循环取决于第一个,我们如何解决这个问题?

for k = 1 to n
...
   for j = k + 1 to n

PS:我一直在 C++ 上开发算法,从那里我开始并行化过程(这意味着“发现”如何并行化的过程)

1个回答

如果我正确理解了您的问题,您对直接方法的 GPU 实现感兴趣,用于求解密集线性方程组。

首先让我说,实现高效、准确和健壮的线性代数例程需要相当多的专业知识,因此您的第一个选择应该是使用现有的库,例如MAGMA

如果您出于教学目的对自己的实现感兴趣,我建议您专注于模型问题,例如 Cholesky 分解(A=CTC在哪里A是对称正定的并且C是上三角形),并研究数据之间的依赖关系cij要点C.

您很快就会了解到“完全”并行化是不可能的,但这是利用 GPU 并行性来布置计算的几种方法。谷歌搜索“GPU 并行密集 Cholesky”将向您展示有关该论点的大量文献,因此您不应假装在很短的时间内赶上。

几点建议:

  • 请记住,Cholesky 分解有几种算法变体,一本关于该主题的好书应该向您展示不止一个,
  • 不要只关注计算,还要关注内存布局以减少延迟
  • 注意您如何实现扩展以增加矩阵大小
  • 从比较简单的变体开始,不要从一开始就尝试优化
  • 如果您的实现比已建立的库效率低得多,请不要失望,而是学习他们的代码来学习。

至于 CUDA,它采用了一种针对特定架构量身定制的编程模型,其抽象程度低于 OpenCL 等其他框架或 MPI 等 API。编程必须是“硬件意识”才能获得良好的效率,因为没有中间层,为你做优化。同样,内存和算术延迟隐藏是关键因素,因此据我所知,没有简单的理论结果或“并行化模型”可供调用。“CUDA C 最佳实践指南”是一个很好的(并且几乎是必要的)起点。