分散メモリ型並列計算機上での行列演算の並列化

Presentation on theme: "分散メモリ型並列計算機上での行列演算の並列化"— Presentation transcript:

1 分散メモリ型並列計算機上での行列演算の並列化
秋田晃治 岩本健吾

2 概要 HPC2500上でMPIによって並列化した行列演算を実行 結果の比較 まとめ 基本的な分割による演算 Foxのアルゴリズム
キャッシュ・アクセスにおける問題と解決 Foxのアルゴリズム 結果の比較 まとめ

3 基本的な分割による演算 × = PU0 PU3 PU0 PU3 PU0 PU1 PU2 PU3 A0 A1 B0 B1 B2 B3 C0
(図は講義資料から拝借)

4 キャッシュ・アクセスにおける問題 ・必要な要素をL2からロード ・必要な要素がL1に存在しない ・列の要素は連続でない 場合、L2からロード
・次の要素をロードするときに 　再びL1キャッシュ・ミス ・必要な要素がL1に存在しない 　場合、L2からロード ・HPC2500は64B(要素×16)を L2キャッシュ・ヒット時にロード ・行の要素は連続 ・次の計算に必要な 　要素も同時にロード アクセス・レイテンシが 性能向上の妨げに

5 キャッシュ・アクセスにおける問題の解決 × = × = 基本的な計算法 PU0 PU3 PU0 PU3 PU0 PU1 PU2 PU3
A0 PU1 A1 × B0 B1 B2 B3 = C0 C1 C2 C3 PU2 A2 PU3 A3 改良型計算法 PU0 A0 B0 C0 PU1 A1 B1 C1 × = PU2 A2 B2 C2 PU3 A3 B3 C3

6 行列演算の比較 使用する演算法 比較の方法 基本的な分割による演算法 L1キャッシュ・ミスを減らした演算法
Foxのアルゴリズムを使用した演算法 比較の方法 正方行列数を変化 CPU数を変化

7 計算時間の結果(CPU固定) CPU=4の場合(N:正方行列のサイズ) N= 1000 2000 3000 4000 5000 基本
0.631 5.731 39.979 キャッシュ改 0.560 7.300 25.663 61.890 Fox 0.177 1.052 3.319 7.688 14.923 (計算時間の単位は[sec])

8 計算時間の結果(CPU固定)

9 計算時間の結果(サイズ固定) N=3600の場合 CPU=4 CPU=9 CPU=16 基本 54.960[sec] 30.706[sec]
0.85Gflops 1.52Gflops 4.65Gflops キャッシュ改 50.672[sec] 24.556[sec] 8.037[sec] 0.92Gflops 1.90Gflops 5.80Gflops Fox 6.044[sec] 2.680[sec] 1.651[sec] 7.72Gflops 17.40Gflops 28.26Gflops

10 まとめ キャッシュ・アクセスを意識して、行列をキャッシュに配置することで高速化が可能 Foxのアルゴリズムではそれ以上の速度が得られる