Parallel-algorithm-matrix-multiplication
並列アルゴリズム-行列乗算
マトリックスは、固定数の行と列に配置された数値データと非数値データのセットです。 行列乗算は、並列計算における重要な乗算設計です。 ここでは、メッシュやハイパーキューブなどのさまざまな通信ネットワークでの行列乗算の実装について説明します。 メッシュとハイパーキューブはネットワーク接続性が高いため、リングネットワークなどの他のネットワークよりも高速なアルゴリズムを使用できます。
メッシュネットワーク
ノードのセットがp次元グリッドを形成するトポロジは、メッシュトポロジと呼ばれます。 ここでは、すべてのエッジがグリッド軸に平行であり、すべての隣接ノードが相互に通信できます。
ノードの合計数=（行のノード数）×（列のノード数）
メッシュネットワークは、次の要因を使用して評価することができます-
- 直径
- 分割幅
直径-メッシュネットワークでは、2つのノード間の最長*距離*は直径です。 kP ノードを持つp次元メッシュネットワークの直径は* p（k–1）*です。
- 2分割幅*-2分割幅は、メッシュネットワークを2つの半分に分割するためにネットワークから削除する必要があるエッジの最小数です。
メッシュネットワークを使用した行列乗算
ラップアラウンド接続を持つ2DメッシュネットワークSIMDモデルを検討しました。 特定の時間内にn ^ 2 ^プロセッサを使用して2つのn×n配列を乗算するアルゴリズムを設計します。
行列AとBにはそれぞれ要素a〜ij〜とb〜ij〜があります。 処理要素PE〜ij〜は、a〜ij〜およびb〜ij〜を表します。 すべてのプロセッサに乗算する要素のペアがあるように、行列AとBを配置します。 マトリックスAの要素は左方向に移動し、マトリックスBの要素は上方向に移動します。 マトリックスAおよびBの要素の位置のこれらの変更は、各処理要素PE、乗算する値の新しいペアを表します。
アルゴリズムのステップ
- 2つの行列をずらします。
- すべての製品を計算、a〜ik〜×b〜kj〜
- ステップ2が完了したら、合計を計算します。
アルゴリズム
Procedure MatrixMulti
Begin
for k = 1 to n-1
for all Pij; where i and j ranges from 1 to n
ifi is greater than k then
rotate a in left direction
end if
if j is greater than k then
rotate b in the upward direction
end if
for all Pij ; where i and j lies between 1 and n
compute the product of a and b and store it in c
for k= 1 to n-1 step 1
for all Pi;j where i and j ranges from 1 to n
rotate a in left direction
rotate b in the upward direction
c=c+aXb
Endハイパーキューブネットワーク
ハイパーキューブは、エッジが互いに垂直で、同じ長さのn次元の構造です。 n次元ハイパーキューブは、nキューブまたはn次元キューブとも呼ばれます。
2 ^ k ^ノードを持つHypercubeの機能
- 直径= k
- 分割幅= 2 ^ k–1 ^
- エッジの数= k
Hypercube Networkを使用した行列乗算
Hypercubeネットワークの一般仕様-
- N = 2 ^ m ^ をプロセッサの総数とします。 プロセッサをP〜0、〜P〜1〜…..P〜N-1〜とします。
- iとi ^ b ^を2つの整数、0 <i、i ^ b ^ <N-1とし、そのバイナリ表現は位置b、0 <b <k–1でのみ異なります。
- 2つのn×n行列、行列Aと行列Bを考えてみましょう。
- *ステップ1 *-行列Aおよび行列Bの要素は、位置i、j、kのプロセッサがa〜ji〜およびb〜ik〜を持つようにn ^ 3 ^プロセッサに割り当てられます。
- *ステップ2 *-位置（i、j、k）にあるすべてのプロセッサが積を計算します + C（i、j、k）= A（i、j、k）×B（i、j、k）
- *ステップ3 *-合計C（0、j、k）=ΣC（i、j、k）、0≤i≤n-1、ここで0≤j、k <n–1。
ブロックマトリックス
ブロックマトリックスまたはパーティションマトリックスは、各要素自体が個々のマトリックスを表すマトリックスです。 これらの個々のセクションは、*ブロック*または*サブマトリックス*として知られています。
例
図（a）で、Xはブロック行列で、A、B、C、Dはそれ自体の行列です。 図（f）は、マトリックス全体を示しています。
ブロック行列乗算
2つのブロック行列が正方行列である場合、単純な行列乗算を実行する方法で乗算されます。 例えば、
