並列計算システム特論演習 SCS特別講義 平成13年10月15日

並列アーキテクチャとコンパイラ 並列計算 リストラクチャリング･コンパイラ 計算能力増大 逐次処理のソフトウェアへの投資、莫大 物理的限界 既存のソフトウェアを並列計算機で効率よく作動させるにはどうすれば良いだろう？ 並列計算 リストラクチャリング･コンパイラ

逐次プログラムを並列プログラムにリストラクチャリング コンパイラの役割 Fortran Processor C Processor Program Database PARAFRASE-2 Parallel Fortran Parallel C Scheduler 　逐次プログラムを並列プログラムにリストラクチャリング

ループ表現 Do I1=1,N1 Do I2=1,N2 : Do Ik=1,Nk A(I1,I2,…,Ik)=… Enddo イタレーションのインスタンス をｋ次元ベクトルで表現

ループの並列実行 Do I=1,N Statement(I) Enddo Doall I=1,N Statement(I) Enddoall Statement(N) Statement(2) Statement(N)

データ依存関係の定義 ２つのステートメント S i ( i 1,･･･, i k ) , S j ( j 1,･･･, j k ) がフロー依存関係にある　 　　　　S i ( i 1,･･･, i k ) ≦ S j ( j 1,･･･, j k )　かつ　 　ＯＵＴ ( S i ( i 1,･･･, i k )) ∩ ＩＮ ( S j ( j 1,･･･, j k )) ≠φ 　を満たす( i 1, i 2 ･･･, i k ) , ( j 1, j 2 , ･･・, j k ) が存在する S i δS j と表す S i ( i 1,・・・, i k) : 依存元 S j ( j 1,･･･, j k) : 依存先

２つのステートメント S i ( i 1,･･･, i k ) , S j ( j 1,･･･, j k ) が逆依存関係にある 　を満たす( i 1, i 2 ･･･, i k ) , ( j 1, j 2 , ･･・, j k ) が存在する S i δS j と表す

２つのステートメント S i ( i 1,･･･, i k ) , S j ( j 1,･･･, j k ) が出力依存関係にある 　を満たす( i 1, i 2 ･･･, i k ) , ( j 1, j 2 , ･･・, j k ) が存在する S i δ°S j と表す

S i ≦S j の時、これら２つのステートメントには少なくとも一組の依存関係がある 　静的依存関係と呼ぶ 複数のインスタンスが存在する

距離の定義 デグリー k のステートメント( i 1, i 2 ･･･, i k ) と ( j 1, j 2 , ･･・, j k ) に対して、第 r 次元での距離φr φr = j r – i r (1 < r < k) <φ1,φ2, ･･･, φk > 　：　依存ベクトル 実距離 （ 距離 ） Φij = ∑ φr Π Nm k r=1 m= r +1 依存先と依存元の総イタレーション数

S 1 S 2 S 3 S 4 データ依存グラフ (DDG) S 5 S 1 : A = B + C S 2 : B = C + E S 3 : D = A + B S 4 : IF D > 0 THEN S 5 : B = D + 1 S 2 S 3 S 4 データ依存グラフ (DDG) S 5 ステートメント　　ノード　V = { S 1 , S 2 , ･･･ , S n } ステートメント間のデータ依存関係　　　アーク E = 　　　　　　　 {e ij = (S i,S j | S i , S j Є V )}

1 < I 1 < I 2 < N かつ I 1 + K = I 2 DO I = 1 , N 　　　　 S 1 : A ( I + K ) = ･･･ S 2 : ･･･ = A ( I ) ENDDO 依存関係を調べる 1 < I 1 < I 2 < N　かつ　I 1 + K = I 2 インデックス Iに対して次式を満たすI 1, I 2 を求める I 2 – I 1 = K が成り立つ　　　　　　　依存関係が存在する 依存距離 書き込みと読み出しとの間に実行されなければならないイタレーション数

ソースコードへのアーキテクチャに関係しない最適化 逐次プログラム 依存関係の検出 DDG作成 最適化 ソースコードへのアーキテクチャに関係しない最適化 リストラクチャリング 並列化

並列化の例 ループ・インターチェンジ ループ・アンローリング ループ・ディストリビューション ループ・ピーリング ストリップ・マイニング ループ・フュージョン ループ・コラプシング ：

複雑な依存関係を持つループの並列化 Do I=1,M Do J=1,N A(I,J) = (A(I,J)+A(I+1,J)+A(I,J+1))/3 Enddo I 6 5 4 3 2 1 1 2 3 4 5 6 7 J

外側のループの制御変数の値を内側のあるループの制御変数に加える変換 ループ傾斜 ( loop skewing ) 外側のループの制御変数の値を内側のあるループの制御変数に加える変換 DO i = 1, n DO i = 1, n DO j = 1 + 1, I + n DO j = 1, n S S ENDDO ENDDO ENDDO ENDDO

loop skewing I I J J 1 2 3 4 5 5 4 3 2 並列実効可 1 5 4 3 2 1 1 2 3 4 5 6 7 5 4 3 2 1 1 2 3 4 5 J 6 7 8

ループ・スキューイング適用後 I 6 5 4 3 2 1 1 2 3 4 5 6 7 J Do I=1,M Do J=I,N+I A(I,J-I+1) = (A(I,J-I+1)+A(I+1,J-I+1)+A(I,J-I+2))/3 Enddo I 6 5 4 3 2 1 1 2 3 4 5 6 7 J

巡回する依存関係を持つループの並列化 依存巡回を持つ逐次型ループの場合 巡回部分を除去できない 巡回縮小 逐次型ループに含まれる並列性の抽出

距離λが大きいほど、 スピードアップ率、上がる 巡回縮小 DO I = 1 , N S 1 S1: A ( I + K ) = B ( I ) – 1 S2: B ( I + K ) = A ( I ) + C ( I ) ENDDO (a) 距離λの依存巡回をもつループ S 2 逐次ループ DO I = 1 , N , K DOALL J = I , I + K – 1 A ( I + K ) = B ( I ) – 1 B ( I + K ) = A ( I ) + C ( I ) ENDDOALL ENDDO (b) 変換後のループ λ= K 倍速くなる 距離λが大きいほど、　　スピードアップ率、上がる λ : Reduction Factor

λ= 2 の場合 I = 3 : A ( 3 ) = B ( 1 ) – 1 B ( 3 ) = A ( 0 ) * K I = 4 : A ( 4 ) = B ( 2 ) – 1 B ( 4 ) = A ( 1 ) * K DO I = 3 , N A ( I ) = B ( I - 2 ) - 1 B ( I ) = A ( I - 3 ) * K ENDDO (a) 逐次ループ I = 5 : A ( 5 ) = B ( 3 ) – 1 B ( 5 ) = A ( 2 ) * K I = 6 : A ( 6 ) = B ( 4 ) – 1 B ( 6 ) = A ( 3 ) * K DO J = 3 , N , 2 DOALL I = J , J + 1 A ( I ) = B ( I - 2 ) - 1 B ( I ) = A ( I - 3 ) * K I = 7 : A ( 7 ) = B ( 5 ) – 1 B ( 7 ) = A ( 4 ) * K ENDDOALL ENDDO (b) 変換後のループ (c) b のアンロール版

Reduction Factor λ= min (3, 4) = 3 依存巡回の距離が違う場合 DO I = 1 , N X ( I ) = Y ( I ) + Z ( I ) Y ( I + 3 ) = X ( I - 4 ) * W ( I ) φ1 = 4, φ2 = 3 ENDDO Reduction Factor λ= min (3, 4) = 3 (a) DO J = 1 , N , 3 縮小 DOALL I = J , J + 2 X ( I ) = Y ( I ) + Z ( I ) Y ( I + 3 ) = X ( I - 4 ) * W ( I ) ENDDOALL ENDDO (b)

インスタンスごとに静的フロー依存 距離が異なる 可変依存距離に対する巡回縮小 DO I = 4 , N インスタンスごとに静的フロー依存　距離が異なる A ( 4I - 1 ) = M * B ( 3I - 1 ) B ( 4I - 1 ) = C ( I ) + A ( 3I – 1 ) ENDDO (a) 最小距離　λ =　2 DO J = 4 , N , 2 DOALL I = J , J + 1 A ( 4I - 1 ) = M * B ( 3I - 1 ) B ( 4I - 1 ) = C ( I ) + A ( 3I – 1 ) ENDDOALL ENDDO (b)

ネストしたループに使われる巡回縮小 1. 単純縮小 2. 選択的縮小 3. 実依存縮小 （TD 縮小） DO I = 3 , N 1 DO J = 5 , N 2 A ( I , J ) = B ( I – 3, J - 5 ) B ( I , J ) = A ( I – 2, J - 4) ENDDO ENDDO (a)　ネストしたループ例

J N1 　・・・・・・ N2 ．．． 9 8 A 7 6 5 B 4 3 2 1 I 1 2 3 4 5 6

ネストにおける各ループに対する依存巡回が別々であるもの。 ネスト深度１のループについては、距離ベクトルの最初の要素だけが使われる。 1. 単純縮小 　ネストにおける各ループに対する依存巡回が別々であるもの。 ネスト深度１のループについては、距離ベクトルの最初の要素だけが使われる。 ネストの各ループに対して、巡回縮小が単一ループの時のように別々に適用される。

2 4 A B J I のループに対する依存距離 A : 2 B : 3 J のループに対する依存距離 A : 4 B : 5 I 10 9 8 2 7 A 6 5 B J のループに対する依存距離 4 依存距離の最小値を使用する A : 4 B : 5 3 2 4 1 I 1 2 3 4 5 6

単純巡回縮小 DO I 1= 3 , N 1, 2 DO J 1= 5 , N 2, 4 DOALL I = I 1, I 1 + 1 DOALL J = J 1, J 1 + 3 A ( I , J ) = B ( I –3, J - 5 ) B ( I , J ) = A ( I – 2, J – 4 ) ENDDOALL ENDDOALL ENDDO 並列度＝２＊４ ENDDO (b)

k 個の異なる依存巡回を持つ深度k のループ 2. 選択的縮小 k 個の異なる依存巡回を持つ深度k のループ ある巡回の各依存を、その距離ベクトルの各要素でラベル付け　　　　 最浅部のループから始まるネストの各ループに対して　　　 Reduction Factor λi (i =1,2,…,k) を計算 　 (1 ≦ j ≦ k, λj ≧ 1 となるj が得られるまで)　　 ネストの第j 番目のループが係数λでブロック化　 　j 番目内の全てのネストしたループをDOALL に変換

2 J I のループに対する依存距離 A : 2 B : 3 I 12 11 10 9 8 7 A 6 5 B 4 3 2 1 1 2 3 1 2 3 4 5 6 7

選択的巡回縮小 DO I 1 = 3 , N 1, 2 DOALL I = I 1, I 1 + 1 DOALL J = 5, N 2 A ( I , J ) = B ( I –3, J - 5 ) B ( I , J ) = A ( I – 2, J – 4 ) ENDDOALL ENDDOALL ENDDO 並列度＝２＊(N2-4) (c)

依存巡回における各依存は実距離によってラベル付けされる。 ネストしているループがあたかも単一ループであるかのように巡回縮小が適用される。 3. 実依存縮小 （TD 縮小） 依存巡回における各依存は実距離によってラベル付けされる。 ネストしているループがあたかも単一ループであるかのように巡回縮小が適用される。

J 14 13 12 11 10 9 8 7 A 6 5 B 4 3 1 2 3 4 5 6 7 8 I

TD 巡回縮小 DO K = 1 , NM , λ T1 = ( K DIV M ) + 1 T3 = ( K MOD M ) + 5 T4 = ( ( K + λ) MOD M ) – 1 + 5 DOALL I = T1, T2 IF I <> T1 THEN L1 = 5 ELSE L1 = T3 IF I <> T2 THEN L2 = N2 ELSE L2 = T4 DOALL J = L1, L2 Reduction factor λは既知、 N = N1 - 3 + 1, M = N2 – 5 + 1 とする A ( I , J ) = B ( I –3, J - 5 ) B ( I , J ) = A ( I – 2, J – 4 ) ENDDOALL ENDDOALL ENDDO (c)

min (Φ1,･･･,Φ k )≧Π min (φ1i, φ2i ,･･･, φ k i) ＴＤ縮小によって得られる reduction factor は単純縮小によって得られる減少係数の総数以上である。 m min (Φ1,･･･,Φ k )≧Π min (φ1i, φ2i ,･･･, φ k i) i=1 　S 1 δ1 S 2 δ2 ･･･ δk-1 S k δ k S 1 を、それぞれ長さ　Ｎ1, Ｎ2, ･･･,Ｎm のｍ個のループの中でネストした、ｋ個のステートメントから成る依存巡回とする。 ＜φi1,･･･, φ i m＞ : 　距離ベクトル Φ i :　 δ i ( i = 1, ･･･, k ) の実距離

回のイタレーション以降はA ( 3 I + 1 ) は使えない 依存距離の計算 添字式の違い 依存関係の距離 DO I = 2 , N A ( 3I + 1 ) = ･･･ ・・・ = A ( 2I - 4 ) 増分係数ρ= 2 ENDDO 3 I + 1 > 2 I – 4 の時、フロー依存あり 差分　D = 3 I + 2 – 2 I + 4 = I + 5 D ρ I + 5 2 = 回のイタレーション以降はA ( 3 I + 1 ) は使えない DOALL を含む形に変換可

L 1 : INC = MIN ( N – J , CELL (( J + 5 ) / 2 ) –1 ) DOALL I = J , J + INC A ( 3I + 1 ) = ･･･ ・・・ = A ( 2I - 4 ) ENDDOALL J = J + INC + 1 IF J < N GOTO L 1 依存関係、保持 変換は効果的か？ ループ長 マシン特有の同期命令の性能 D やρのサイズ などの要因によって決まる

単一ループにおけるa I + b の形の線形表現に対する距離計算の概要 DO I = 1 , N A ( a I + b ) = ･･･ フロー依存が存在する ・・・= A ( c I + d ) ENDDO 添え字I に対し、ある i , j があり 1 < I < N かつ a i + b = c j + d a i – c i = d – b　が成り立つ gcd ( a , c ) がd – b を割り切る i = i 0 + j = j 0 + t c gcd (a , c ) t a 解のひとつが( i 0 , j 0 ) ならば、任意の解 ( i , j ) は、

巡回縮小と分割 分割 DO I = 1 , N DOALL J = 1 , g DO I = J , J + ( N – J ) / g S 1 S 2 ･･･ S k S 1 S 2 ･･･ S k 分割 ENDDO ENDDO (a) ENDDOALL (b) 依存巡回　：　S 1 δ1 S 2 δ2 ・・・ δk-1 S k δk S 1 δi の距離　：　φi ( I = 1, 2, ･･･, k ) g = gcd ( φ1 , φ2 , ･･･,φk )　：　k個全ての距離の最大公約数

(a) を依存巡回により、変換後 DOALL I = 1 , N , λ DO J = J , J + λ- 1 S 1 S 2 ･･･ S k ENDDO ENDDOALL (c) λ = min ( φ1 , φ2 , ･･･,φk )　

> 巡回縮小によって作られたDOALL のサイズ 分割によって作られたDOALL のサイズ 分割 巡回縮小 φ1 , φ2 , ･･･,φk が正の整数なら、 min ( φ1 , φ2 , ･･･,φk ) > gcd ( φ1 , φ2 , ･･･,φk )　 λ> g 巡回縮小によって作られたDOALL のサイズ 分割によって作られたDOALL のサイズ > 分割 DOループにおいて、１つの依存関係を形成するイタレーション全てを統合 群自体は逐次実行、異なる群を並列実行 （依存関係は各群の内部に対してのみ ） 巡回縮小 独立したイタレーションの並列実行 異なる群を演算順序を保証しながら並列実行（依存関係は群同志でのみ）

巡回縮小によって作られる群のすべてのイタレーションは、依存先の制約を受けない 各イタレーション内のすべてのステートメントも並列実行可能 K 個のステートメントからなるループは、k 倍のスピードアップが可能 分割では、適用できない 各群のすべてのイタレーションが依存関係の連鎖を形成するため スピードアップ率 分割 巡回縮小 S cs = λ* k S pa = g ( λ> g , k > 1 )

具体例 DO I = 3 , N A ( I ) = B ( I – 2 ) B ( I ) = A ( I – 3 ) λ= 2, g = 1 分割では並列性を抽出できない ENDDO 巡回縮小 DO J = 3 , N , 2 DOALL I = J , J + 1 A ( I ) = B ( I – 2 ) B ( I ) = A ( I – 3 ) ENDDOALL ENDDO

課題 次のプログラムをプロセッサ数１６のシステムで最も効率よく 並列稼動させるようにループ・リストラクチャリングを行え Do I=2,34 Do J=4,68 Do K=8,136 A(I,J,K)=B(I-2,J,K) B(I,J,K)=C(I,J-4,K) C(I,J,K)=A(I,J,K-8) Enddo 提出先 joe@ics.nara-wu.ac.jp 提出期限 10月22日になる前