3

私は LU 前処理を使用して共役勾配ソルバー (方程式の線形システム用) を作成し、nvidia の研究コミュニティに関するマキシム ナウモフ博士の論文をガイドラインとして使用しました。上三角行列システムは、次の 2 つの段階に分けられます。

  1. 分析フェーズ (スパース パターンを利用し、並列化レベルを決定します)。
  2. 解決段階そのもの。

このトピックに関連するすべての投稿、およびナウモフの論文自体によると、分析フェーズは解決フェーズよりも大幅に遅くなりますが、一度実行されるため、全体の実行時間を考慮すると問題になることはありませんが、私のプログラムでは、解析フェーズに全体のソリューション時間 (すべての反復を実行するのに必要な時間!) の ~35-45% が必要です。ほぼすべての要素で以前の要素が既知である必要があるため、大量の並列化が可能になります (CFD では、各ノードはその周囲に少なくとも隣接する 6 つのノード (六面体ボリューム) を必要とし、それがすべての行で繰り返されるため)、分析フェーズとにかくあまり役​​に立ちません！

このコードのmatrixLUには上三角行列と下三角行列の両方が含まれ、上三角行列は元の行列の対角線を使用し、下三角行列は 1 対角線 (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 ミリ秒
  • 解決フェーズの実行時間 (すべての反復の合計): 350 ミリ秒
  • すべての浮動小数点演算は倍精度形式で実行されます
  • GPU: GeForce GTX 550 Ti
  • OS: Windows 7 Ultimate、64 ビット
4

1 に答える 1

8

NVIDIA の線形代数ライブラリ チームに連絡したところ、次のようなフィードバックがありました。

  1. パフォーマンス結果に関して：

    1. CG 反復法は、線形システムの解が見つかるまで 10 回の反復のみを実行します。この場合、これは分析フェーズで費やされた時間を償却するのに十分な反復ではないようです。(編集:)ソリューションに収束するために必要なステップの数は、アプリケーションによって異なります。一部の前処理なしの反復法では収束せず (または数千回の反復が必要)、前条件付きの反復法では解に収束するのに数十回 (または数百回) の反復が必要です。この特定のアプリケーションで反復法が 10 回の反復で収束するという事実は、必ずしもすべてのアプリケーションを代表するものではありません。

    2. 分析段階と解決段階の比率は 6 = 210/35 であり、これは通常は区間 [4,10] にある他の行列での実験と一致しています。解析フェーズとソルブ フェーズの時間が、CPU での疎三角形のソルブにかかる時間とどのように比較されるかは明確ではありません。（これは知っておくと興味深い情報です。）

  2. アルゴリズムに関して：
    1. 残念ながら、パフォーマンスを少し回復するためにできることはごくわずかです (分析フェーズをスピードアップする実際の方法はありません)。たとえば、matrixLU を別々の下三角部分と上三角部分に分割できます。一般に、個別の三角形部分を使用した計算は、一般的な行列に埋め込まれた三角形部分を使用した計算よりも高速です。前提条件として 0 フィルインの不完全分解を使用している場合、CUSPARSE ライブラリで最近利用可能になった、GPU で 0 フィルインの不完全 LU/Cholesky を利用することもできます。(編集:) CUDA ツールキット 5.0 リリースでは、0 フィルインの不完全 LU 因数分解が利用可能です。現在、このリリースのアーリー アクセス バージョンは、登録済みの開発者が入手できます。NVIDIA の Web サイトで。
    2. 解析フェーズと解決フェーズの比率が異なる GPU 間でどのように変化するかを調べたことはありません。行ったすべての実験は C2050 で行われました。
    3. 分析フェーズは、どの行をまとめてレベルに処理できるかに関する情報を収集する必要があるため、時間がかかります。解決フェーズは、レベルのみを処理するため高速です (このペーパーを参照してください)。

最後に、問題には十分な並列性がないと考えていることにも言及しました。しかし、行列を見ただけでは、並列処理の量を推測するのは難しい場合があります。実際に並列性がほとんどない (すべての行が前の行に依存する) 場合、CUSPARSE 疎三角解はこの問題の適切なアルゴリズムではない可能性があります。また、前提条件を使用せずに、または問題により適している可能性のある他の種類の前提条件を使用して、CG 反復法を実行することもできます。

前述のように、このコードのパフォーマンスが GPU と CPU でどのように比較されるかを知ることは興味深いでしょう。

編集： いくつかのコメントについて...前述のように、前処理された反復法の最終的な反復回数は、アプリケーションによって異なります。場合によっては、非常に小さい場合もありますが (たとえば、アプリケーションでは 10 です)、比較的大きい場合もあります (100 単位で測定)。この論文は「勝利」ではなく、アルゴリズムのトレードオフに焦点を当てています。ルーチンを効果的に使用するために、ユーザーがルーチンをより深く理解できるようにします。繰り返しになりますが、手元のスパース パターンに並列性がない場合、これは適切なアルゴリズムではありません。

CPU と GPU の比較に関して、GPU が優れている特定の問題 (密な行列と行列または疎な行列とベクトルの乗算など) があり、他の問題 (リンクされたリストのトラバースや完全に連続した部分の実行など) があります。コード) ではありません。疎三角線形システムの解は、これらのアルゴリズムの間のどこかにあります (係数行列の疎パターンと線形システムの他のプロパティに応じて、適切に機能する場合と機能しない場合があります)。また、GPU を使用するかどうかの決定は、疎三角解法などの単一のアルゴリズムだけに基づいているのではなく、アプリケーションで使用されるアルゴリズムのセット全体に基づいています。最終的に、GPU は多くの場合、アプリケーション全体のパフォーマンスの高速化と改善に非常に成功しています。

最後に、trsm と csrsv の関係で、密なストレージで操作を実行する小さな行列のほうが、疎なストレージよりも高速であることは驚くことではありません (これらの小さな行列は疎かもしれませんが)。これは通常、三角解だけでなく、他の線形代数演算にも当てはまります (ただし、演​​算と行列のスパース パターンに応じて、異なるクロス ポイントで発生する可能性があります)。また、ここでも、疎三角解アルゴリズムは、解析が 1 回実行され、解が複数回実行される反復設定で実行されるように設計されています。したがって、1 回実行すると (そして分析フェーズでカウントすると)、この操作のクロスオーバー ポイントが高くなり、密な形式よりも疎な形式の方が効果的であることは驚くべきことではありません。

于 2012-07-12T04:45:39.837 に答える