7

行列の並列分解を扱う際に、ブロック分布に精通しています。ここでは、(たとえば) 4 つのプロセスがあり、それぞれに行列のサブ領域があります。

ブロック行列の分解

たとえば、ここでは、行 ( procrows) のプロセス数が 2 に等しく、列 ( ) のプロセス数も 2 に等しく、元のマトリックス サイズが の場合、proccolsサブマトリックスのサイズは になります。A_localN/2 x M/2N x M

「ブロック循環」分布を使用するこの例を読んでいます。この部分では：

/* Begin Cblas context */
/* We assume that we have 4 processes and place them in a 2-by-2 grid */
int ctxt, myid, myrow, mycol, numproc;
int procrows = 2, proccols = 2;
Cblacs_pinfo(&myid, &numproc);
Cblacs_get(0, 0, &ctxt);
Cblacs_gridinit(&ctxt, "Row-major", procrows, proccols);

それらはハードコーディングされていますが、問題ありませんが、読み込まれたマトリックスの場合、ヘッダーがありますprocrows。proccols

Nb と Mb は [行列の] ブロックの行と列の数になります。

これはわかりません。N、M、procrows、proccols によって完全に決定されるのではNbありませんか?Mb

編集

例を実行すると、プロセス 0 のサブマトリックスには、上の図のように、マトリックスの左上隅のすべての要素が含まれていることがわかります。これは、ジョナサンの答えと矛盾しています。ただし、ScaLAPACK の Cholesky では問題なく動作します。

4

1 に答える 1

12

質問で説明した行列のブロック分解は、行列を配布する完全に有効な方法ですが、それが唯一の方法ではありません。

特に、ブロック データの分散 (マトリックスをprocrows x processサブマトリックスに分割する) は少し柔軟性に欠けます。マトリックスのサイズが行または列のプロセスの数で割り切れない場合 (通常、マトリックスのサイズを制御できず、procrows/proccols の柔軟性がある程度しかない場合)、重大な負荷分散の問題が発生する可能性があります。また、問題を「過度に分解」できると非常に便利な場合があります。タスクよりも多くの部分に分割します。特に MPI の場合、各タスクはプロセスであるため、各プロセスが操作する複数のサブマトリックスを使用できると便利な場合があります。これにより、この追加レベルの並列処理をスレッド化 (ほとんどのアプリケーションに組み込まれている) で処理できます。シングルプロセス線形代数ライブラリ)。

負荷分散の柔軟性を最大限に高め、最高度のプロセス間並列処理を利用できるようにする方法は、純粋に循環分散です。たとえば、15 のアイテムを 4 つのプロセッサに分割すると、プロセッサ 1 はアイテム 1 を取得し、2 はアイテム 2 を取得し、3 はアイテム 3 を取得し、4 は 4 を取得し、プロセッサ 1 はアイテム 5 を取得します。の上; プロセッサ間で項目を丸めます。

一方、1 次元ブロック分解では、プロセッサー 1 は項目 1 から 4 を取得し、プロセッサー 2 は項目 5 から 9 を取得します。

有用なLLNL 並列計算チュートリアルの図が続きます。各色のラベルは、どのプロセッサがデータの領域を取得したかを示しています。

ここに画像の説明を入力

したがって、巡回分解は、並列処理と負荷分散には最大限に適していますが、データ アクセスにはひどいものです。線形代数演算を実行するためにアクセスできる隣接するデータはすべてオフプロセッサです。一方、ブロック分解はデータ アクセスに最適です。できるだけ大きな連続したデータのチャンクがあるので、素敵な大きなサブマトリックスでマトリックス操作を行うことができます。ただし、並列処理には柔軟性がなく、負荷分散に関してコストがかかる可能性があります。

Block-Cyclic は 2 つの間の補間です。行列をブロックに分解し、それらのブロックをプロセス間で循環的に分散します。これにより、データ アクセスの連続性と柔軟性の間のトレードオフを調整できます。ブロック-サイクリック ブロック サイズが 1 の場合は、サイクリック分布です。彼らがそうであるN/procrowsか、N/proccolsあなたがブロックディストリビューションを持っている場合; 間に何かを入れることもできます。

2D では、原則として、行と列に沿って異なる分解を選択できることに注意してください。これは、行列が 1 種類の計算でのみ使用される場合に便利な場合があります。しかし、より一般的なケースは、分解がすべての次元で同じであるため、「ブロック分解」または「ブロック巡回分解」と言う場合、一般にすべての次元でのことを意味します。

これについての適切な説明は、netlib の Scalapack ページにあります。

于 2015-06-29T13:17:31.607 に答える