分散メモリ型並列計算機上での行列演算の並列化 秋田晃治 岩本健吾
概要 HPC2500上でMPIによって並列化した行列演算を実行 結果の比較 まとめ 基本的な分割による演算 Foxのアルゴリズム キャッシュ・アクセスにおける問題と解決 Foxのアルゴリズム 結果の比較 まとめ
基本的な分割による演算 × = PU0 PU3 PU0 PU3 PU0 PU1 PU2 PU3 A0 A1 B0 B1 B2 B3 C0 (図は講義資料から拝借)
キャッシュ・アクセスにおける問題 ・必要な要素をL2からロード ・必要な要素がL1に存在しない ・列の要素は連続でない 場合、L2からロード ・次の要素をロードするときに 再びL1キャッシュ・ミス ・必要な要素がL1に存在しない 場合、L2からロード ・HPC2500は64B(要素×16)を L2キャッシュ・ヒット時にロード ・行の要素は連続 ・次の計算に必要な 要素も同時にロード アクセス・レイテンシが 性能向上の妨げに
キャッシュ・アクセスにおける問題の解決 × = × = 基本的な計算法 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
行列演算の比較 使用する演算法 比較の方法 基本的な分割による演算法 L1キャッシュ・ミスを減らした演算法 Foxのアルゴリズムを使用した演算法 比較の方法 正方行列数を変化 CPU数を変化
計算時間の結果(CPU固定) CPU=4の場合(N:正方行列のサイズ) N= 1000 2000 3000 4000 5000 基本 0.631 5.731 39.979 102.527 273.702 キャッシュ改 0.560 7.300 25.663 61.890 126.017 Fox 0.177 1.052 3.319 7.688 14.923 (計算時間の単位は[sec])
計算時間の結果(CPU固定)
計算時間の結果(サイズ固定) 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
まとめ キャッシュ・アクセスを意識して、行列をキャッシュに配置することで高速化が可能 Foxのアルゴリズムではそれ以上の速度が得られる