マルチコア CPU を⽤いた性能検証

1 subroutine MTOSJ( [ ⋯ ], tol):

2 nb1 = CASHSIZE / n

3 [ ⋯ ] ,

4 do

5 maxt = 0

6 sort-columns( , )

7 omp-parellel-do

8 id = omp_thread_num()

9 nt = omp_num_threads()

10 nb = n/nt

11 for r=1:2*nt

12 (pp,qq,flag) = modulus-pair(2*nt, id, r)

13 if flag == false:

14 for p2=nb*(pp-1)+1:nb*pp:nb1

15 for =nb*(qq-1):nb*qq:

16 for =p2:p2+nb1-1

17 t = orthcols( , , , )

18 maxt = max(maxt, t)

19 end

20 end

21 end

22 else if flag == true:

23 for p2=nb*(pp-1)+1:nb*pp:nb1

24 for =p2+1:nb*pp:

25 for =p2:q

26 t = orthcols( , , , )

27 maxt = max(maxt, t)

28 end

29 end

30 end

31 for p2=nb*(qq-1)+1:nb*qq:nb1

32 for =p2+1:nb*qq:

33 for =p2:q

34 t = orthcols( , , , )

35 maxt = max(maxt, t)

36 end

37 end

38 end

39 end

40 end

41 while maxt > tol

42 for = 1,

43 ‖ ‖

44 end

45 ( , , … , )

46

47 return ( , , , )

図5.1 共有メモリ並列⽤の⽚側ヤコビ法の擬似プログラム

#ofsweeps

index

mode=1 mode=2 mode=3 mode=4 mode=5

図5.2 xGESVJ の巡回回数．縦軸が巡回回数．横軸が⾏列番号．

mode ごとに式 (4.91) によって番号付けて整理し，異なる乱数シードを持つものの中で最⼤の値を持つ ものを⽰している．また，巡回回数は選択したペアの個数を ^{( )}で割ったものと定義する．このよ うに定義する理由は，xGESVJ が対⾓に近い要素を複数回消去するため 1 巡回におけるペアの個数が

( )の倍数とならないためである．また，規格化演算量𝑐 は次の形で定義する：

𝑐 = 3𝑠 − 2𝑟 𝑠. (5.2)

ただしここで𝑠は上で定義した巡回回数であり，𝑟 は選択したペアの内，列ベクトル同⼠が⼗分直 交していたため𝐴の更新をスキップしたものの割合である．このとき𝑛 𝑐 が𝑉の計算を⾏わな い⽚側ヤコビ法における演算量の主要項となるため，𝑐 はそこから巡回回数とスキップの割合に よって決まる係数を抜き出したものとみることができる．

図5.2と図5.3はそれぞれ xGESVJ と MTOSJ の巡回回数である．この図から，巡回回数が特異値分布 や条件数に⼤きく依存していることがわかる．とくに mode= 3や mode= 5は相対的に⼩さな密集特 異値を持つような特異値分布であるため，収束が遅く，条件数が⼤きいときには巡回回数が30を超え るものもある^*2．⼀⽅で，mode= 2の場合の巡回回数はほぼ定数となっている．xGESVJ と MTOSJ を⽐較すると，MTOSJ の⽅に⼩さなばらつきがみられるが，ほぼ同じ巡回回数となっていることが わかる．そこで，このテストにおいて，巡回回数の⾯では，MTOSJ は xGESVJ の性能を損なわずに並 列化できていることがわかる．

図5.4と図5.5はそれぞれ，xGESVJ と MTOSJ の規格化演算量である．規格化演算量は巡回回数に⽐

例した項を持つため，巡回回数のグラフと同様の傾向がみられ，特異値分布や条件数によって⼤き く値が異なる．しかし規格化演算量は巡回回数とは異なり xGESVJ と MTOSJ とで値が⼤きく異な るものが多く存在し，最⼤で約15，割合にして約38%の増⼤となるものがある．これは逆算すると

*2前処理を⾏うことでこのような⾏列に対しても⼩さな巡回回数で収束させることが可能であるが，このテストでは xGESVJ と MTOSJ の⽐較を⽬的としているため，前処理の効果については考慮していない．

#ofsweeps

index

mode=1 mode=2 mode=3 mode=4 mode=5

図5.3 MTOSJ の巡回回数．縦軸が巡回回数．横軸が⾏列番号．

normalizedcost

index

mode=1 mode=2 mode=3 mode=4 mode=5

図5.4 xGESVJ の規格化演算量．縦軸が規格化演算量．横軸が⾏列番号．

MTOSJ の⽅が𝑟 が⼩さいことを⽰しており，すなわち，無駄な計算が⾏われていることを⽰して いる．しかしこのオーバーヘッドは 10 割に満たないため，単純計算では 2 並列以上を⽤いれば単体計 算時よりも⾼速化することが期待される．そこで，MTOSJ は xGESVJ と⽐べて並列化によって計算 の無駄は⽣まれるが，並列化の加速によって実⾏時間⾃体は⾼速化することが期待される．

2 つ⽬のテストでは条件数𝜅 = 10 と並列化のための列ブロック数𝑤 = 2nt= 20，そして特異値分 布 mode= 5を固定し，⾏列サイズ𝑚 = 𝑛 = 512, 768, 1, 152, … , 8, 760と約1.5倍ずつ変化させたと きの実⾏時間を⽰す．測定は異なる 5 つの乱数シードを⽤いて⾏い，その平均を⽰す．テストは 10 コ

normalizedcost

index

mode=1 mode=2 mode=3 mode=4 mode=5

図5.5 MTOSJ の規格化演算量．縦軸が規格化演算量．横軸が⾏列番号．

.

timeinsec.

xGESVJ MTOSJ

図5.6 xGESVJ と MTOSJ の実⾏時間の⽐較

アの CPU Xeon E5-2660 v2 上で⾏ったため，ちょうどすべてのコアを⽤いる設定となっている．この CPU は 25MB のキャッシュを持っているため，⾏列サイズが約1, 800を超えると⾏列のデータがキャ ッシュに収まらないようになるため，メモリアクセスの影響が表れる可能性がある．

図 5.6は xGESVJ と MTOSJ の実⾏時間の結果を⽰している．MTOSJ は並列化の効果によって xGESVJ よりも⾼速となっており，⾏列サイズが⼤きいところでは約4.7倍，⾏列サイズが⼩さいとこ ろでは約6.6倍となっている．その中間のサイズでは性能差はより⼤きくなっており，𝑚 = 𝑛 = 2, 592 のときが最⼤で約11倍となっている．これはコア数よりも⼤きな加速効果となっているが，MTOSJ

1,1 1,2 1,3 1,4 1,5 1,6 1,7 1,8

2,1 2,2 2,3 2,4 2,5 2,6 2,7 2,8

3,1 3,2 3,3 3,4 3,5 3,6 3,7 3,8

4,1 4,2 4,3 4,4 4,5 4,6 4,7 4,8

5,1 5,2 5,3 5,4 5,5 5,6 5,7 5,8

6,1 6,2 6,3 6,4 6,5 6,6 6,7 6,8

7,1 7,2 7,3 7,4 7,5 7,6 7,7 7,8

1,1 1,3 1,5 1,7 1,2 1,4 1,6 1,8

3,1 3,3 3,5 3,7 3,2 3,4 3,6 3,8

5,1 5,3 5,5 5,7 5,2 5,4 5,6 5,8

7,1 7,3 7,5 7,7 7,2 7,4 7,6 7,8

2,1 2,3 2,5 2,7 2,2 2,4 2,6 2,8

4,1 4,3 4,5 4,7 4,2 4,4 4,6 4,8

6,1 6,3 6,5 6,7 6,2 6,4 6,6 6,8

図5.7 ⼆次元ブロックサイクリック分割の例． × ⾏列を × のブロックで分割し， × ノ ードへ配置した．左図は元の⾏列上にそのブロックを配置するノードによって⾊を付けたもの，右 図はノードごとにどのブロックを持つのか番号を振り分けたものである．

においてCASHSIZEをこの⾏列サイズ近辺で最適となるようにチューニングした結果が現れていると

考えられる．

以上のように，xGESVJ の並列化を⾏い，共有メモリ上で⾼速に動作する⽚側ヤコビ法の実装を得 た．この実装は以下の分散メモリ並列化実装で⽤いる．