第 5 章 Temporary 行列の削除 28
5.3 提案
5.3.1 Temporary 行列を削除した 1-level Stassen アルゴリズム
先行研究で使用したTemporary行列を2個含んだ演算スケジュールは積行列の 部分行列C11, C12, C21, C22をTemporary行列の代わりに用いている[10]. 本研究で
はTemporary行列の個数を0にするために初期行列AとBの部分行列を再利用す
る逐次計算演算スケジュールを導いた. これらの部分行列のためのメモリの確保
と解放はStrassenアルゴリズムによる計算と標準的な乗算の両方で共通して行わ
れるので, Strassenアルゴリズムによる計算をより高速化するためのオーバーヘッ ドにならない. このようにしてTemporary行列を削除した演算スケジュールを表
Step Operation 1 C22=A11−A21 2 C11=B22−B12
3 C21=C22C11 4 A21 =A21+A22 5 C11=B12−B11 6 C22=A21C11 7 A21 =A21−A11 8 B12 = B22−C11 9 C12=A21B12 10 A21 =A12−A21 11 C12=A21B22 12 C12=C12+C22 13 B22 =A11−B11 14 C11=C11+B22 15 C12=C12+C11 16 C11=C11+C21 17 B11 =B12−B21 18 C21=A22B11 19 C21=C11−C21 20 C22=C22+C11 21 C11=A12B21 22 C11=B22+C11
表 5.1: Temporary行列を削除した逐次計算プログラムの演算スケジュール
5.1に示す. 表5.1の演算スケジュールを導くに際してデータの引き継ぎが正しく 行われることを確認するために, Strassenアルゴリズムによる計算の結果と標準的 な乗算の結果に大きな違いがないか調べた.
4章で報告したようにV100を用いた場合はStrassenアルゴリズムによる行列の 乗算が行列の標準的な乗算よりも高速になる行列のサイズで部分行列の乗算を並列 実行することが可能になる. それ故Temporary行列の削除に加えて部分行列の乗 算を2個づつ並列にしたプログラムを作成した. そのプログラムの演算スケジュー ルを5.2に示す.
5.3.2 Temporary 行列を削除した 2-level Stassen アルゴリズム
Multi-level Strassenは1-level Strassenで分割した部分行列の7回の乗算に再 びStrassenアルゴリズムを応用し, これを何度も繰り返す. 各levelでの1-level
Step Operation Stream 1 C22 =A11−A21
2 C11 =B22−B12
3 A21=A21A22 4 C12 =B12+B11 5 C21 =C22C11 0
C22 =A21C11 1 6 A21=A21−A11 7 B12=B22−C12
8 C12 =A12−A21 9 C11 =A21B12 0
A21=C12B22 1 10 C12 =C12+A21 11 B22=A11−B11 12 C11 =C11+B22
13 C12 =C12+C11 14 C11 =C11+C21 15 B11=B12−B21 16 C21 =A22B11 0
A11=A12B21 1 17 C22 =C22+C11 18 C21 =C11−C21 19 C11 =B22+A11
表 5.2: Temporary行列を削除したstream並列実行プログラムの演算スケジュール Strassenの標準的な乗算に対する speedupが1. 0を越えていると, multi-level Strassen全体のspeedupはさらに高くなる. もし含められた1-level Strassenの speedupが1. 0未満であるとmulti-level Strassen全体のspeedupは低下する. 5-5 節で説明するように1-level StrassenはV100を使用した場合行数が5, 200以上で speedupは1. 0以上になる. 一方行数が15, 000以上になるとglobal memoryの容 量不足のためにプログラムの実行不可能となる. 複数の GPUを使用するとメモリ が増えるので、より大きなサイズの行列の計算が可能になるが、GPU間の遅い通 信のためにStrassenアルゴリズムによる高速化の利点が失われる.したがって本研 究の実験環境では, multi-level Strassenは二つの levelだけを含むことになる. 図 5.2に2-level Strassenを模式的に示す.
図5.2で二つのlevelを元の行数の upper levelと, それを半分のサイズの部分 行列に分割したlower levelを示した. 本研究ではlower levelの計算に最速である
Temporary行列を削除し部分行列の乗算を2個づつ並列にした演算スケジュールを
図 5.2: 2-level Strassen アルゴリズムの模式図
用いた. 理由は行列の小さいサイズでTemporary行列の影響と並列化の効果が大 きくなるからである. Temporary行列の代わりに初期行列のAとBの部分行列を
使うとlower levelの計算の後初期データが上書きされる. また積行列Cの部分行
列も使われるのでlower levelでの部分行列の一つ乗算の結果が次の乗算で上書き される可能性がある. これらの上書きによって誤った結果が生じないようなupper
levelの演算スケジュールを作成しなければならない.
Upper levelの演算スケジュールを導くために, 最初に初期行列AとB の部分
行列のデータを一時的に保存するための8個のTemporary行列と部分行列の乗算 の結果を一時的に保存する7個のTemporary行列を含んだ演算スケジュールを作 成した. 次に計算途中でのデータの引き継ぎに誤りが出ないように確認しながら Temporary行列の個数を11まで減らした. その次の段階でLower levelの演算スケ ジュールで再利用される行列AとB の部分行列の個数を最小の3まで減らし, そ の条件のもとでUpper levelの演算スケジュールのTemporary行列の個数を7まで 減らした. またlower levelの演算スケジュールでTemporary行列の代わりに再利 用される初期行列の部分行列の個数をできる限り少なくしなければならない. こ のような条件の下で導いたupper levelとlower levelの演算スケジュールを表5.3 と5.4に示す.
Step Operation 1 S1 =A11 2 S2 =A21
3 S3 =B12 4 T1 =S1−S2 5 T2 =B22−S3 6 M1 =T1T2 7 T1 =S2+A22 8 T2 =S3−B11 9 S2 =T1T2 10 T1 =T1−S1 11 M2 =T1B22 12 M2 =M2+S2 13 T1 =T1B11 14 S3 =S2+T1 15 C12=M2+S3 16 S3 =S3+M1 17 T2 =T2−B21 18 M1 =A22T2 19 C21=S3 −M1 20 C22=S2 +S3 21 S3 =A12B21 22 C11=T1+S3
表 5.3: 2-level Strassen プログラムのupper levelの演算スケジュール