分散メモリ型並列計算機上での 行列演算の並列化 秋田晃治 岩本健吾 概要 • HPC2500上でMPIによって並列化した行列 演算を実行 – 基本的な分割による演算 • キャッシュ・アクセスにおける問題と解決 – Foxのアルゴリズム • 結果の比較 • まとめ 基本的な分割による演算 PU0 PU0 PU1 PU2 PU3 A0 A1 A2 A3 × PU3 B0 B1 B2 B3 PU0 = PU3 C0 C1 C2 C3 (図は講義資料から拝借) ・行列を CP U数iで分割 ・各 CP Uはブロック行 Aiと ブロック列 Biを持ち ブロック列 Ciを計算 キャッシュ・アクセスにおける問題 行Aiで L1キャッシュ 列BiでL1キャッシュ ミスしたとき ミスしたとき L1キャッシュ空間 ・必要な要素がL1に存在しない 場合、L2からロード ・HPC2500は64B(要素×16)を L2キャッシュ・ヒット時にロード ・行の要素は連続 ・次の計算に必要な 要素も同時にロード L1キャッシュ空間 ・必要な要素をL2からロード ・列の要素は連続でない ・次の要素をロードするときに 再びL1キャッシュ・ミス アクセス・レイテンシが 性能向上の妨げに キャッシュ・アクセスにおける問題の解決 基本的な計算法 PU0 PU1 PU2 PU3 PU0 A0 A1 A2 A3 PU3 × B0 B1 B2 B3 × B0 B1 B2 B3 PU0 PU3 = C0 C1 C2 C3 = C0 C1 C2 C3 改良型計算法 PU0 PU1 PU2 PU3 A0 A1 A2 A3 ブロック列 Biをあらかじめ転置した キャッシュに配置して 高速化 状態で キャッシュ・ミスを削 減 行列演算の比較 • 使用する演算法 – 基本的な分割による演算法 – 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 Fox 0.177 1.052 3.319 61.890 126.017 7.688 14.923 (計算時間の単位は[sec]) 計算時間の結果(CPU固定) 計算時間[sec] 1000 100 基本 キャッシュ改 Fox 10 1 0.1 1000 2000 3000 4000 正方行列のサイズ 5000 計算時間の結果(サイズ固定) • N=3600の場合 基本 キャッシュ改 Fox CPU=4 54.960[sec] 0.85Gflops 50.672[sec] 0.92Gflops 6.044[sec] 7.72Gflops CPU=9 30.706[sec] 1.52Gflops 24.556[sec] 1.90Gflops 2.680[sec] 17.40Gflops CPU=16 10.024[sec] 4.65Gflops 8.037[sec] 5.80Gflops 1.651[sec] 28.26Gflops まとめ • キャッシュ・アクセスを意識して、行列をキャッ シュに配置することで高速化が可能 • Foxのアルゴリズムではそれ以上の速度が 得られる
© Copyright 2025 ExpyDoc
