6

私は現在、管理しているシミュレーションツール用に、C++のスパース行列/数学/反復ソルバーライブラリに取り組んでいます。既存のパッケージを使用したかったのですが、徹底的な調査の結果、シミュレーターに適したものは見つかりませんでした（flens、it ++、PetSC、eigenなどを調べました）。良いニュースは、私のソルバーとスパース行列構造が非常に効率的で堅牢になったことです。悪いニュースは、OpenMPを使用した並列化を検討していることです。学習曲線は、少し急です。

私たちが解決するドメインは、ブロック対角形式でまとめられたサブドメインに分割できます。したがって、私たちのストレージスキームは、それぞれがサブドメインに適した形式（たとえば、圧縮行ストレージ：CRS、圧縮対角ストレージ：CDS、高密度など）を持つ小さな正方行列（blocks []）の配列のように見えます。サブドメイン間の接続を説明するバックグラウンドマトリックス（現在CRSを使用）。

ほとんどの（すべて？）反復ソルバーの「ホットスポット」は、行列ベクトルの乗算演算です。これは、私のライブラリにも当てはまります。したがって、私はMxVルーチンの最適化に注力してきました。ブロック対角構造の場合、M * x=bの擬似コードは次のようになります。

b=background_matrix*x
start_index = 1;
end_index = 0;
for(i=1:number of blocks) {
    end_index=start_index+blocks[i].numRows();
    b.range(start_index, end_index) += blocks[i] * x.range(start_index, end_index);
    start_index = end_index+1;
}

ここで、background_matrixはバックグラウンド（CRS）行列、blocksはサブドメイン行列の配列、.rangeは開始インデックスから終了インデックスまでのベクトルの部分を返します。

操作はループの他の反復から独立しているため、明らかにループを並列化できます（そして並列化できます）（範囲は重複しません）。通常のシステムには10〜15個のブロックがあるため、4つ以上のスレッドが実際に大きな違いを生みます。

並列化が適切なオプションであると見なされているもう1つの場所は、各サブドメインストレージスキームのMxV操作です（上記のコードの1行目と6行目で呼び出します）。CRS、CDS、および密行列MxV操作の並列化についてはたくさんあります。通常、2つのスレッドで素晴らしいブーストが見られ、スレッドが追加されるにつれて収穫逓減が大幅に減少します。

上記のコードのブロックループで4つのスレッドが使用され、それらの各スレッドがサブドメインの解決に2つのスレッドを使用するスキームを想定しています。ただし、OpenMPを使用してスレッドのプールを管理する方法がわかりません。openmpforループのスレッド数を制限することは可能ですか？このマルチレベルの並列処理は、実際には意味のあることですか？私がここで提案したことについての他の考えはありがたいです（そして最後まで読んでくれてありがとう！）

4

2 に答える 2

5

私が説明するものはすべて実装に依存することに注意してください。

openmp forループのスレッド数を制限することは可能ですか？

はい。これを行うにはさまざまな方法があります。外側のループに類似したomp_set_nested(1);ものを設定し、内側のループにディレクティブを使用します。これにより、8つのスレッドが得られるはずです（実装によっては、コアが8つ未満の場合も設定する必要があります）#pragma omp parallel for num_threads(4)#pragma omp parallel for num_threads(2)OMP_THREAD_LIMIT

または、次のようなものを使用して、ループを手動で展開することもできます。

#pragma omp parallel sections {
     #pragma omp section 
     do your stuff for the first part, nest parallel region again
     #pragma omp section 
     and so on for the other parts
}

OpenMP 3.0では、を使用して同じことをより効率的に実行できる場合があります#pragma omp task。

または、8つのスレッドを開始して、並列セクション内の現在のスレッド番号を取得し、スレッド番号に基づいて手動でスケジュールします。

最後に、完全にネストされたループがある場合（ループが完全にネストされている場合、実際の割り当てが最も内側のループでのみ発生する場合）、すべてを1つのループに書き換えることができます。i基本的に、2つのイテレータをj1つの大きなイテレータにパックします(i, j)。これにより、局所性が低下し、パフォーマンスが低下する可能性があることに注意してください

このマルチレベルの並列処理は、実際には意味のあることですか？

それは状況によって異なります、そしてあなたは自分自身を見つけなければなりません。一般に、マルチレベルの並列処理により、問題はよりスケーラブルになります。ただし、スケジューリングはより複雑になる可能性があります。この論文は面白いかもしれません。

スレッド数を手動で設定する場合：スレッド数を設定する主な利点は、スケジューリング時に問題に関する特定の知識を使用できることです。これにより、オーバーヘッドを削減し、実行中のコードの局所性を高めることができるため、キャッシュヒットが増え、メインメモリI/Oが少なくなります。

ネストされた並列処理でスレッド数を手動で設定することの主な欠点は、最も内側のループのスレッドが暗黙のバリアでアイドル状態で待機する可能性がある一方で、追加の作業を実行できることです（例）。また、粗粒度の並列処理は適切にスケーリングされません。したがって、外部ループの実行時間がループ内で大きく異なる場合は、単に4つのスレッドに分割するよりも柔軟にスケジュールを設定する必要があります。

その他の考え

SIMDでMxVを行うことについてはどうですか。アーキテクチャによっては、これにより2〜4のスピードアップが得られます。私はすぐにあなたのためにこのプレゼンテーションをグーグルで検索しました。

MxVの場合、ループタイリング、レジスタとキャッシュのブロック、および関連する手法により、データの局所性を高め、偽共有などの他の問題を減らすことができます。この本の第11章（プレビューできます）では、データアクセスを再構築する方法についていくつかの追加のアイデアが得られる可能性があります。

于 2010-07-01T20:06:40.863 に答える
0

OpenMP.orgで専門家に聞いてみませんか

登録してログインします：http： //openmp.org/forum/viewforum.php？f = 3

于 2010-07-01T19:41:12.023 に答える