cusparse csrsv_analysis的性能非常慢

Question

我用LU预处理编写了一个共轭梯度求解器(用于线性方程组),我使用了Maxim Naumov博士关于nvidia研究界的论文作为指导,残差更新步骤,需要求解下三角矩阵系统然后求解上三角矩阵系统分为两个阶段:

1. 分析阶段(利用稀疏模式并决定并行化级别).
2. 解决方案阶段本身.

根据与该主题相关的所有帖子,以及Naumov的论文本身,分析阶段明显慢于解决阶段,但它执行了一次,所以考虑到整个执行时间不应该是一个问题,但是,在我的程序中,分析阶段需要整个解决时间的约35-45%(执行所有迭代所需的时间!),这非常烦人,另一件事是我很确定矩阵的稀疏模式不会允许大量并行化,因为几乎所有元素都需要知道先前的元素(因为在CFD中每个节点至少需要相邻的6个节点(六面体体积),并且每个节点都重复),因此分析阶段反正不会很有用!

此代码中的 matrixLU包含上三角矩阵和下三角矩阵,上三角矩阵使用原始矩阵对角线,下三角矩阵具有统一对角线(LU分解).

// z = inv(matrixLU)*r
cusparseMatDescr_t descrL = 0 ;
cusparseMatDescr_t descrU = 0 ;
cusparseStatus = cusparseCreateMatDescr(&descrL) ;
cusparseStatus = cusparseCreateMatDescr(&descrU) ;

cusparseSetMatType(descrL,CUSPARSE_MATRIX_TYPE_GENERAL) ;
cusparseSetMatIndexBase(descrL,CUSPARSE_INDEX_BASE_ONE) ;
cusparseSetMatDiagType(descrL,CUSPARSE_DIAG_TYPE_UNIT) ;
cusparseSetMatFillMode(descrL,CUSPARSE_FILL_MODE_LOWER) ;

cusparseSetMatType(descrU,CUSPARSE_MATRIX_TYPE_GENERAL) ;
cusparseSetMatIndexBase(descrU,CUSPARSE_INDEX_BASE_ONE) ;
cusparseSetMatDiagType(descrU,CUSPARSE_DIAG_TYPE_NON_UNIT) ;
cusparseSetMatFillMode(descrU,CUSPARSE_FILL_MODE_UPPER) ;

cusparseSolveAnalysisInfo_t inforL = 0 ;
cusparseSolveAnalysisInfo_t inforU = 0 ;
cusparseStatus = cusparseCreateSolveAnalysisInfo(&inforL) ;
cusparseStatus = cusparseCreateSolveAnalysisInfo(&inforU) ;

double startFA = omp_get_wtime() ;
cusparseStatus = cusparseDcsrsv_analysis(cusparseHandle, CUSPARSE_OPERATION_NON_TRANSPOSE, N, NZ, descrL, matrixLU, iRow, jCol, inforL) ;
if(cusparseStatus != CUSPARSE_STATUS_SUCCESS) printf("%s \n\n","cusparseDcsrsv_analysis1 Error !") ;
cusparseStatus = cusparseDcsrsv_analysis(cusparseHandle, CUSPARSE_OPERATION_NON_TRANSPOSE, N, NZ, descrU, matrixLU, iRow, jCol, inforU) ;
if(cusparseStatus != CUSPARSE_STATUS_SUCCESS) printf("%s \n\n","cusparseDcsrsv_analysis2 Error !") ;
double finishFA = omp_get_wtime() ;

所以,任何人都知道为什么分析阶段如此缓慢？以及它如何加速？是(依赖于GPU的分析阶段执行时间)/(解决阶段执行时间)比率？

编辑: 我在很多情况下试过这个求解器,结果很接近,但在我关注的具体情况下,它有以下条件:

• 尺寸(N):〜860,000*860,000
• 非零数(NZ):~ 6,000,000
• 收敛所需的迭代次数:10
• 分析阶段执行时间:210 ms
• 解决阶段执行时间(总计所有迭代):350 ms
• 所有浮点运算都以双精度格式执行
• GPU:GeForce GTX 550 Ti
• 操作系统:Windows 7终极版,64位

Answer 1

我联系了NVIDIA的线性代数库团队,他们提供了以下反馈.

1. 关于绩效结果:

   1. CG迭代方法仅执行10次迭代,直到找到线性系统的解.在这种情况下,似乎没有足够的迭代来分摊分析阶段所消耗的时间.(编辑:)收敛到解决方案所需的步骤数在不同的应用程序中有所不同.在一些未经处理的迭代方法中,不会聚(或进行数千次迭代),并且预处理的迭代方法需要数十(或数百)次迭代才能收敛到解.在该特定应用中迭代方法在10次迭代中收敛的事实不一定代表所有应用.

   2. 分析和求解阶段的比例是6 = 210/35,这与我们在其他矩阵上的实验一致,其中它通常在区间[4,10].目前尚不清楚分析和求解阶段的时间如何与CPU上稀疏三角形求解所花费的时间相比较.(这将是有趣的信息.)

2. 关于算法:
   1. 不幸的是,你只能做一些事情来恢复一点性能(没有真正的方法可以加快分析阶段).例如,您可以将matrixLU拆分为单独的下三角和上三角部分.使用单独的三角形部分进行计算通常比使用嵌入在一般矩阵中的三角形部分进行计算更快.如果你使用0填充作为预处理器的不完全因子分解,你也可以利用GPU上的不完全LU/Cholesky和0填充,这最近在CUSPARSE库中可用.(编辑 :) CUDA Toolkit 5.0版本中提供了带有0填充的不完全LU分解.目前,此版本的早期访问版本可以由NVIDIA网站上的注册开发人员获取.
   2. 我们从未研究过不同GPU的分析和解决阶段的比例是如何变化的; 我们所做的所有实验都是在C2050上进行的.
   3. 分析阶段很慢,因为它必须收集关于哪些行可以一起处理成级别的信息.解决阶段更快,因为它只处理级别(参见本文).

最后,您还提到您认为问题中没有足够的并行性.但是,通过查看矩阵,很难猜测并行度.如果确实存在很少的并行性(每行依赖于前一行),则CUSPARSE稀疏三角形求解可能不是该问题的正确算法.此外,您可以尝试在没有预处理的情况下运行CG迭代方法,或者使用可能更适合您的问题的其他类型的预处理器.

如前所述,了解此代码的性能如何在GPU和CPU上进行比较会很有趣.

编辑: 关于一些评论......如前所述,预处理迭代方法的最终迭代次数在不同的应用程序中有所不同.在某些情况下,它可能非常小(例如,在您的应用程序中为10),但在其他情况下,它可能相对较大(以100秒为单位).本文不是关注"胜利",而是关注算法的权衡.它试图让用户更深入地了解例程,以便有效地使用它.同样,如果手头的稀疏模式没有任何并行性,这对您来说不是正确的算法.

关于CPU和GPU比较,存在某些问题(例如密集矩阵矩阵或稀疏矩阵 - 向量乘法),其中GPU很棒,还有其他问题(例如遍历链表或执行完全连续的它不是的代码).稀疏三角形线性系统的解决方案位于这些算法之间(取决于系数矩阵的稀疏模式和线性系统的其他属性,它可能或不适合您).此外,使用GPU的决定不仅仅基于单个算法,例如稀疏三角形求解,而是基于应用程序使用的整个算法集.最终,GPU通常非常成功地加速和改进整个应用程序的性能.

最后,关于trsm与csrsv,我们并不感到惊讶的是,对于在密集存储中执行操作的小矩阵比在稀疏存储中执行操作更快(即使这些小矩阵可能是稀疏的).这通常不仅对于三角形求解而且​​对于其他线性代数运算也是如此(尽管可能在不同的交叉点处发生,这取决于矩阵的操作和稀疏模式).此外,稀疏三角形求解算法再次设计为在迭代设置中运行,其中分析一次完成并且多次完成求解.因此,运行一次(并在分析阶段计算)并不奇怪,这种操作的更高交叉点在稀疏而不是密集格式中更有效.