1 - 東京大学

スパコンプログラミング（１）、（Ⅰ）
1
高性能プログラミング技法
の基礎（１）
東京大学情報基盤センター准教授塙敏博
2016年10月18日（火）10:25-12:10
スパコンプログラミング（１）、（Ⅰ）
講義日程（工学部共通科目）
7.
9月27日(今日)：ガイダンス
10月4日
1.
2.
l
l ログイン作業、テストプログラム実行
10月18日
4.
l
高性能プログラミング技法の基礎１
（階層メモリ、ループアンローリン
グ）
11月1日(8:30-10:15)
5.
l
l
10.
高性能プログラミング技法の基礎2
（キャッシュブロック化）
l
行列-ベクトル積の並列化
ＬＵ分解法（１）
コンテスト課題発表
12月20日
l
ＬＵ分解法（２）
1月10日（★大演習室2）
l
13.
行列－行列積の並列化（２）
12月13日
l
11.
行列-行列積の並列化（１）
12月6日
l
12.
11月1日(10:25-12:10)
6.
9.
べき乗法の並列化
11月29日
l
並列数値処理の基本演算（座学）
10月11日：スパコン利用開始
3.
11月22日
l
8.
2
レポートおよびコンテスト課題
（締切：
2017年2月13日（月）24時厳守
ＬＵ分解法（３）
1月13日(金曜、補講日)
l
新しいスパコンの紹介・お試し、
他
10/11はネットワーク障害のため演習ができなかったので
10/18の内容をほとんどやってしまった
スパコンプログラミング（１）、（Ⅰ）
講義の流れ
1. 階層キャッシュメモリ
2. 演算パイプライン
3. ループアンローリング
4. 配列連続アクセス
5. 演習課題
6. レポート課題
3
スパコンプログラミング（１）、（Ⅰ）
階層キャッシュメモリ
超高速メモリは小容量
4
5
スパコンプログラミング（１）、（Ⅰ）
最近の計算機のメモリ階層構造
高速
Ｏ（1ナノ秒）
Ｏ（1０ナノ秒）
Ｏ（1００
ナノ秒）
Ｏ（1０
ミリ秒）
レジスタ
バイト
Ｋバイト
キャッシュ～Ｍバイト
メインメモリ
ハードディスク
Ｇバイト
Ｇバイト
～Ｔバイト
大容量
•メインメモリ→レジスタへの転送コストは、
レジスタ上のデータアクセスコストのＯ（100）倍！
スパコンプログラミング（１）、（Ⅰ）
6
より直観的には…
レジスタ
キャッシュ
メインメモリ
l高性能（＝速い）プログラミングをするには、
きわめて小容量のデータ範囲について
何度もアクセス（＝局所アクセス）するように
ループを書くしかない
7
スパコンプログラミング（１）、（Ⅰ）
キャッシュの構成例
ＣＰＵ
セット
メインメモリ
演算器
演算
要求
バンク
(ブロック)
演算
結果
レジスタ
データ供給
データ蓄積
キャッシュメモリの構成
キャッシュメモリ
0
データ供給
1
0
2
9
0
1
6
1
4
データ蓄積
メインメモリ
8
キャッシュ
ディレクトリ
0
1
0
2
1
0
2
1
1
3
1
2
4
1
3
6
1
4
7
6
1
4
キャッシュメモリ
上位
物理アドレス
下位
ブロック内
スパコンプログラミング（１）、（Ⅰ）
8
Reedbush-Uのメモリ構成
●データ
高速
レジスタ
レベル１キャッシュ
（32Ｋバイト/１コア）
レベル2キャッシュ
（256Ｋバイト/１コア）
●データ
●データ
レベル3キャッシュ
（45Ｍバイト/18コア
=1ソケット）
メインメモリ
（256Ｇバイト／ノード）
●データ
大容量
9
スパコンプログラミング（１）、（Ⅰ）
Reedbush-Uのメモリ構成
●データ
高速
レジスタ
レベル１キャッシュ
（32Ｋバイト/１コア）
●データ
レベル2キャッシュ
（256Ｋバイト/１コア）
データが
Ｌ１キャッシュ上
にあれば、
速くアクセス可能
レベル3キャッシュ
（45Ｍバイト/18コア
=1ソケット）
メインメモリ
（256Ｇバイト／ノード）
大容量
10
スパコンプログラミング（１）、（Ⅰ）
Reedbush-Uのノードのメモリ構成
コア０コア１コア２コア３
コア
3２
コア
3３
コア
3４
コア
3５
Ｌ１
Ｌ１
Ｌ１
Ｌ１ … Ｌ１
Ｌ１
Ｌ１
Ｌ１
Ｌ2
Ｌ2
Ｌ2
Ｌ2
Ｌ2
Ｌ2
Ｌ2
Ｌ3 (物理的に分散）
Ｌ2
Ｌ3 (物理的に分散）
メインメモリ
※階層メモリ構成となっている
11
スパコンプログラミング（１）、（Ⅰ）
Reedbush-U全体メモリ構成
ココココ
アアアア
０
Ｌ１
Ｌ２
Ｌ３
Ｌ
コ
ア
3
Ｌ
…２
コ
ア
3
Ｌ
３
コ
ア
3
Ｌ
４
コ
ア
3
Ｌ
５
１１１１
１１１１
ＬＬＬＬ
ＬＬＬＬ
2 2 2 2
2 2 2 2
Ｌ3 (物理的
Ｌ3 (物理的
に分散）
に分散）
メインメモリ
ココココ
アアアア
０
Ｌ１
Ｌ２
Ｌ３
Ｌ
コ
ア
3
Ｌ
…２
コ
ア
3
Ｌ
３
コ
ア
3
Ｌ
４
コ
ア
3
Ｌ
５
１１１１
１１１１
ＬＬＬＬ
ＬＬＬＬ
2 2 2 2
2 2 2 2
Ｌ3 (物理的
Ｌ3 (物理的
に分散）
に分散）
メインメモリ
…
ココココ
アアアア
０
Ｌ１
Ｌ２
Ｌ３
Ｌ
コ
ア
3
Ｌ
…２
コ
ア
3
Ｌ
３
コ
ア
3
Ｌ
４
コ
ア
3
Ｌ
５
１１１１
１１１１
ＬＬＬＬ
ＬＬＬＬ
2 2 2 2
2 2 2 2
Ｌ3 (物理的
Ｌ3 (物理的
に分散）
に分散）
メインメモリ
…
メモリ階層が階層
InfiniBand-EDR
ネットワーク
（12.５Ｇバイト／秒
×双方向）
12
スパコンプログラミング（１）、（Ⅰ）
Reedbush-U計算ノードの構成
１ソケットのみを図示（もう1ソケットある）
Core
#0
L L
1 2
L3
Core
#5
Core
#1
L L
1 2
L3
Core
#6
L L
1 2
Core
#2
L L
1 2
L3
Core
#7
L L
1 2
Core
#3
L L
1 2
L3
Core
#8
L L
1 2
Core
#4
L L
1 2
L3
DDR4
DIMM
Memory
16GB ×2枚
コア当たりL1データ: 32KB, L2: 256KB,
L3: 2.5MB(共有) => L3 は全体で45MB
PCIe
QPI x2
L L
1 2
L3
Core
#9
L L
1 2
L3
Core
#14
L L
1 2
L3
L3
Core
#10
L L
1 2
L3
Core
#15
L L
1 2
L3
L3
Core
#11
L L
1 2
L3
Core
#16
L L
1 2
L3
L3
Core
#12
L L
1 2
L3
Core
#17
L L
1 2
L3
Core
#13
L L
1 2
L3
Memory
16GB ×2枚
ソケット当たりメモリ量：16GB×8＝128GB
Memory
Memory
16GB ×2枚
16GB ×2枚
76.8 GB/秒
=(8Byte×2400MHz×4 channel)
スパコンプログラミング（１）、（Ⅰ）
13
Reedbush-UのCPU(Xeon E5-2695v4)の
詳細情報
項目
命令セット
動作周波数
L1キャッシュ
L2キャッシュ
L3キャッシュ
演算実行
SIMD命令実行
レジスタ
値
IA32 64bit 拡張命令 + AVX2 (Advanced Vector
eXtensions 2)
2.1 GHz
32 Kbytes (命令、データは分離、コア単位)
256 Kbytes （コア単位）
45 Mbytes （ソケット単位）
２整数演算ユニット、2つの浮動小数点積和演算ユニット（FMA）
1命令で4つのFMAが動作
FMAは2つの浮動小数点演算（加算と乗算）を実行可能
l 浮動小数点レジスタ数：16本(物理的には168本？)
スパコンプログラミング（１）、（Ⅰ）
演算パイプライン
演算の流れ作業
14
スパコンプログラミング（１）、（Ⅰ）
15
流れ作業
車を作る場合
• １人の作業員が１つの工程を担当（５名）
•
フロント・バッ
クガラスを
つける
車体作成
•
内装
外装
機能確認
上記工程が２ヶ月だとする（各工程は0.4ヶ月とする）
• ２ヶ月後に１台できる
• 各工程の作業員は、
• ４ヶ月後に２台できる
０．４ヶ月働いて、
１．６ヶ月は休んでいる
（＝作業効率が低い）
• ２ヶ月／台の効率
１台目
２台目
３台目
車体作成
フロント・
バックガ
ラスをつ
ける
内装
外装
機能確
認
車体作成
フロント・
バックガ
ラスをつ
ける
内装
外装
機能確
認
車体作成
フロント・
バックガ
ラスをつ
ける
内装
外装
機能確
認
時間
16
スパコンプログラミング（１）、（Ⅰ）
流れ作業
作業場所が5ヶ所とれるとする
• 前の工程からくる車を待ち、担当工程が終わったら、
次の工程に速やかに送られるとする
•
• ベルトコンベア
0.4ヶ月
車体作成
0.4ヶ月
フロント・バック
ガラスをつける
0.4か月
内装
0.4か月
外装
0.4か月
機能確認
スパコンプログラミング（１）、（Ⅰ）
17
流れ作業
•
•各作業員は、
十分に時間が経つと
0.4か月の単位時間あたり
休むことなく働いている
（＝作業効率が高い）
この方法では
• 2ヶ月後に、1台できる
• 2.4ヶ月後に、2台できる
• 2.8ヶ月後に、3台できる
• 3.2ヶ月後に、4台できる
• 3.4ヶ月後に、5台できる
• 3.8ヶ月後に、6台できる
•このような処理を、
＜パイプライン処理＞
という
• 0.63ヶ月／台の効率
１台目
２台目
３台目
４台目
５台目
車体作成
フロント・
バックガ
ラスをつ
ける
車体作成
内装
外装
機能確
認
フロント・
バックガ
ラスをつ
ける
内装
外装
機能確
認
フロント・
バックガ
ラスをつ
ける
内装
外装
車体作成
車体作成
フロント・
バックガ
ラスをつ
ける
車体作成
機能確
認
内装
外装
機能確
認
フロント・
バックガ
ラスをつ
ける
内装
外装
機能確
認
時間
スパコンプログラミング（１）、（Ⅰ）
18
計算機におけるパイプライン処理の形態
ハードウエア・パイプライニング
1.
計算機ハードウエアで行う
以下の形態が代表的
•
•
1.
2.
演算処理におけるパイプライン処理
メモリからのデータ（命令コード、データ）転送における
パイプライン処理
ソフトウエア・パイプライニング
2.
プログラムの書き方で行う
以下の形態が代表的
•
•
1.
2.
コンパイラが行うパイプライン処理
（命令プリロード、データ・プリロード、データ・ポストストア）
人手によるコード改編によるパイプライン処理
（データ・プリロード、ループアンローリング）
19
スパコンプログラミング（１）、（Ⅰ）
演算器の場合
•
例：演算器の工程（注：実際の演算器の計算工程は異なる）
データＡを
メモリから取る
データＢを
メモリから取る
演算
を行う
演算結果を
収納
行列-ベクトル積の計算では
for (j=0; j<n; j++)
演算器が稼働
for (i=0; i<n; i++) {
する工程
y[j] += A[j][i] * x[i] ;
}
• パイプライン化しなければ以下のようになり無駄
•
A[0][0]を
メモリから取る
x[0]をメモリから
取る
A[0][0]*
x[0]
結果
y[0]収納
A[0][1]を
メモリから取る
x[1]をメモリから
取る
A[0][0]*
x[1]
結果
y[0]収納
A[0][2]を
メモリから取る
時間
x[2]をメモリから
取る
20
スパコンプログラミング（１）、（Ⅰ）
演算器の場合
先ほどの例では演算器は、４単位時間のうち、１単位時間し
か使われていないので無駄（＝演算効率１／４＝２５％）
• 以下のようなパイプライン処理ができれば、
十分時間が経つと、毎単位時間で演算がなされる
l十分な時間とは、十分な
（＝演算効率１００％）
•
A[0][0]を
メモリから取る
x[0]をメモリから
取る
A[0][1]を
メモリから取る
A[0][0]*
x[0]
結果
y[0]収納
x[1]をメモリから
取る
A[0][0]*
x[1]
結果
y[0]収納
x[2]をメモリから
取る
A[0][2]*
x[2]
A[0][2]を
メモリから取る
A[0][3]を
メモリから取る
x[3]をメモリから
取る
A[0][4]を
メモリから取る
結果
y[0]収納
ループ反復回数があること。
行列サイズNが大きいほど、
パイプラインが滞りなく流れ、
演算効率は良くなる。
→Nが小さいと演算効率
が悪い
A[0][3]*
x[3]
結果
y[0]収納
x[4]をメモリから
取る
A[0][2]*
x[4]
…
結果
y[0]収納
時間
スパコンプログラミング（１）、（Ⅰ）
21
演算パイプラインのまとめ
演算器をフル稼働させるため（＝高性能計算するため）に必
要な概念
• メインメモリからデータを取ってくる時間はとても大きい。
演算パイプラインをうまく組めば、メモリからデータを
取ってくる時間を＜隠ぺい＞できる
（＝毎単位時間、演算器が稼働した状態にできる）
• 実際は以下の要因があるので、そう簡単ではない
•
1.
2.
3.
計算機アーキテクチャの構成による遅延（レジスタ数の制約、
メモリ→CPU・CPU→メモリへのデータ供給量制限、など）。
ループに必要な処理（ループ導入変数（i, j）の初期化と加算処理、
ループ終了判定処理）
配列データを参照するためのメモリアドレスの計算処理
コンパイラが正しくパイプライン化される命令を生成するか
スパコンプログラミング（１）、（Ⅰ）
22
実際のプロセッサの場合
• 実際のプロセッサでは
1. 加減算
2. 乗算
ごとに独立したパイプラインがある。
• さらに、同時にパイプラインに流せる命令
（同時発行命令）が複数ある。
• Intel Pentium4ではパイプライン段数が３１段
• 演算器がフル稼働になるまでの時間が長い。
• 分岐命令、命令発行予測ミスなど、パイプラインを中断させる処理が多発す
ると、演算効率がきわめて悪くなる。
• 近年の周波数の低い（低電力な）マルチコアCPU／メニーコアCPUでは、パ
イプライン段数が少なくなりつつある（Xeon Phiは7段）
• Broadwellでは 14-19段 (?)
スパコンプログラミング（１）、（Ⅰ）
23
Reedbush-Uのハードウエア情報
•
１クロックあたり、16回の演算ができる
• AVX2ユニットあたり、乗算および加算が4つ
（8つの浮動小数点演算）
• １クロックで、２つのAVX2ユニットが動作
• 8浮動小数点演算×2 AVX2ユニット＝16浮動小数点演算／クロック
•
１コア当たり2.1ＧＨｚのクロックなので、
• 理論最大演算は、
2.1 GHz* 16回 = 33.6 GFLOPS / コア
• １ノード36コアでは、
33.6 * 36コア = 1209.6 GFLOPS / ノード
スパコンプログラミング（１）、（Ⅰ）
ループアンローリング
コンパイラがやりそうでなかなかやらないんだな
24
スパコンプログラミング（１）、（Ⅰ）
25
ループアンローリング
• コンパイラが、
1. レジスタへのデータの割り当て；
2. パイプライニング；
がよりできるようにするため、コードを書き
換えるチューニング技法
• ループの刻み幅を、１ではなく、ｍにする
• ＜ｍ段アンローリング＞とよぶ
スパコンプログラミング（１）、（Ⅰ）
26
ループアンローリング
• コンパイラ用語では、最内側のループの
展開のこと
• 狭義のループアンローリング
• アプリ屋さんは、多重ループのどの
ループでも展開することをいう
• 広義のループアンローリング
• もしくはコンパイラ用語で、
ループリストラクチャリング（ループ再構成）
の一種
スパコンプログラミング（１）、（Ⅰ）
27
ループアンローリングの例
（行列-行列積、Ｃ言語）
lk-ループ2段展開 (nが2で割り切れる場合)
for (i=0; i<n; i++)
for (j=0; j<n; j++)
for (k=0; k<n; k+=2)
C[i][j] += A[i][k] *B[k][j] + A[i][k+１]*B[k+１][j];
Øk-ループのループ判定回数が１/2になる。
スパコンプログラミング（１）、（Ⅰ）
28
ループアンローリングの例
（行列-行列積、Ｃ言語）
lj-ループ2段展開
(nが2で割り切れる場合)
for (i=0; i<n; i++)
for (j=0; j<n; j+=2)
for (k=0; k<n; k++) {
C[i][j ] += A[i][k] *B[k][j ];
C[i][j+１] += A[i][k] *B[k][j+１];
}
ØA[i][k]をレジスタに置き、高速にアクセスできるようになる。
スパコンプログラミング（１）、（Ⅰ）
29
ループアンローリングの例
（行列-行列積、Ｃ言語）
li-ループ2段展開
(nが2で割り切れる場合)
for (i=0; i<n; i+=2)
for (j=0; j<n; j++)
for (k=0; k<n; k++) {
C[i ][j] += A[i ][k] *B[k][j];
C[i+１][j] += A[i+１][k] *B[k][j];
}
ØB[i][j]をレジスタに置き、高速にアクセスできるようになる。
スパコンプログラミング（１）、（Ⅰ）
ループアンローリングの例
（行列-行列積、Ｃ言語）
li-ループ、および
j-ループ 2段展開
(nが２で割り切れる場合)
for (i=0; i<n; i+=2)
for (j=0; j<n; j+=2)
for (k=0; k<n; k++) {
C[i ][j ] += A[i ][k] *B[k][j ];
C[i ][j+１] += A[i ][k] *B[k][j+１];
C[i+１][j ] += A[i+１][k] *B[k][j ];
C[i+１][j+１] += A[i+１][k] *B[k][j +１];
}
ØA[i][j], A[i+１][k],B[k][j],B[k][j+１]をレジスタに置き、
高速にアクセスできるようになる。
30
スパコンプログラミング（１）、（Ⅰ）
31
ループアンローリングの例
（行列-行列積、Ｃ言語）
lコンパイラにわからせるため、以下のように書く方がよい
場合がある
for (i=0; i<n; i+=2)
for (j=0; j<n; j+=2) {
dc00 = C[i ][j ]; dc01 = C[i ][j+１];
dc10 = C[i+１][j ]; dc11 = C[i+１][j+１] ;
for (k=0; k<n; k++) {
da0= A[i ][k] ; da1= A[i+１][k] ;
db0= B[k][j ]; db1= B[k][j+１];
dc00 += da0 *db0; dc01 += da0 *db1;
dc10 += da1 *db0; dc11 += da1 *db1;
}
C[i ][j ] = dc00; C[i ][j+１] = dc01;
C[i+１][j ] = dc10; C[i+１][j+１] = dc11;
}
スパコンプログラミング（１）、（Ⅰ）
ループアンローリングの例
（行列-行列積、Fortran言語）
lk-ループ2段展開 (nが2で割り切れる場合)
do i=１, n
do j=１, n
do k=１, n, 2
C(i, j) = C(i, j) +A(i, k) *B(k, j) + A(i, k+
１)*B(k+１, j)
enddo
enddo
enddo
Øk-ループのループ判定回数が１/2になる。
32
スパコンプログラミング（１）、（Ⅰ）
33
ループアンローリングの例
（行列-行列積、Fortran言語）
lj-ループ2段展開
(nが2で割り切れる場合)
do i=１, n
do j=１, n, 2
do k=１, n
C(i, j ) = C(i, j ) +A(i, k) * B(k, j )
C(i, j+１) = C(i, j+１) +A(i, k) * B(k, j+１)
enddo
enddo
enddo
ØA(i,
k)をレジスタに置き、高速にアクセスできるようになる。
スパコンプログラミング（１）、（Ⅰ）
34
ループアンローリングの例
（行列-行列積、Fortran言語）
li-ループ2段展開
(nが2で割り切れる場合)
do i=１, n, 2
do j=１, n
do k=１, n
C(i , j) = C(i , j) +A(i , k) * B(k , j)
C(i+１, j) = C(i+１, j) +A(i+１, k) * B(k , j)
enddo
enddo
enddo
ØB(i,
j)をレジスタに置き、高速にアクセスできるようになる。
スパコンプログラミング（１）、（Ⅰ）
35
ループアンローリングの例
（行列-行列積、Fortran言語）
li-ループ、および j-ループ 2段展開
(nが２で割り切れる場合)
do i=１, n, 2
do j=１, n, 2
do k=１, n
C(i , j ) = C(i , j ) +A(i , k) *B(k, j )
C(i , j+１) = C(i , j+１) +A(i , k) *B(k, j+１)
C(i+１, j ) = C(i+１, j ) +A(i+１, k) *B(k, j )
C(i+１, j+１) =C(i+１, j+１) +A(i+１, k) *B(k, j +１)
enddo; enddo; enddo;
ØA(i,j), A(i+１,k),B(k,j),B(k,j+１)をレジスタに置き、
高速にアクセスできるようになる。
スパコンプログラミング（１）、（Ⅰ）
36
ループアンローリングの例
（行列-行列積、Fortran言語）
lコンパイラにわからせるため、以下のように書く方がよい
場合がある
l do i=１, n, 2
do j=１, n, 2
dc00 = C(i ,j ); dc01 = C(i ,j+１)
dc10 = C(i+１,j ); dc11 = C(i+１,j+１)
do k=１, n
da0= A(i ,k); da1= A(i+１, k)
db0= B(k ,j ); db1= B(k, j+１)
dc00 = dc00+da0 *db0; dc01 = dc01+da0 *db1;
dc10 = dc10+da1 *db0; dc11 = dc11+da1 *db1;
enddo
C(i , j ) = dc00; C(i , j+１) = dc01
C(i+１, j ) = dc10; C(i+１, j+１) = dc11
enddo; enddo
スパコンプログラミング（１）、（Ⅰ）
配列連続アクセス
とびとびアクセスには弱い
37
38
スパコンプログラミング（１）、（Ⅰ）
配列の格納方式
• Ｃ言語の場合
}
Ａ［i］［j］
Ｆｏｒｔｒａｎ言語の場合
Ａ（i, j）
j
j
1
2
3
4
1
5
9
13
5
6
7
8
2
6
10
14
9
10
11
12
3
7
11
15
13
14
15
16
4
8
12
16
格納方向
i
i
格納方向
39
スパコンプログラミング（１）、（Ⅰ）
キャッシュとキャッシュライン
•
メインメモリ上とキャッシュ上のデータマッピング方式
• メインメモリからキャッシュへ
• ダイレクト・マッピング方式：単位（メモリバンク）ごとに直接的
• セット・アソシアティブ方式：ハッシュ関数で写像する（間接的）
• キャッシュからメインメモリへ
• ストア・スルー方式：キャッシュ書き込み時に
メインメモリと中身を一致させる
• ストア・イン方式：対象となる単位（キャッシュライン）
が置き換え対象となったときに一致させる
キャッシュメモリ
キャッシュ
ライン
ライン０
ライン１
ライン２
ライン３
ライン４
ライン５
…
メインメモリ
写像関数
メモリバンク
…
40
スパコンプログラミング（１）、（Ⅰ）
キャッシュライン衝突
• 直接メインメモリのアドレスをキャッシュに写像する
簡単なダイレクト・マッピングを考える
• このマッピングの間隔を、ここでは、４とする
• メインメモリ上のデータは、間隔４ごとに、同じキャッシュラインにのる
• この例で、格納方向と逆方向に連続アクセスする
（＝Ｃ言語の場合、i方向を連続アクセス）
メインメモリ
キャッシュ
ライン
メモリ連続
キャッシュメモリ
ライン０
ライン１
ライン２
ライン３
１
５
９
１３
配列アクセス方向
２
６
１０
１４
…
３
７
１１
１５
４
８
１２
１６
41
スパコンプログラミング（１）、（Ⅰ）
キャッシュライン衝突
この場合、データ１がキャッシュライン０に乗ったあと、
すぐにデータ５がアクセスされるため、
キャッシュライン０のデータを追い出さないといけない
2. 同様に、データ５がキャッシュライン０に乗ったあと、
すぐにデータ９がアクセスされるため、
キャッシュライン０のデータを追い出さないといけない
1.
メインメモリ
キャッシュ
ライン
レジスタへ
キャッシュメモリ
９
５
１
ライン０
ライン１
ライン２
ライン３
１
５
９
１３
２
６
１０
１４
…
配列アクセス方向
３
７
１１
１５
メモリ連続
４
８
１２
１６
スパコンプログラミング（１）、（Ⅰ）
42
キャッシュライン衝突
• 以上の、１、２の状態が連続して発生する。
• メモリ→キャッシュの回線が詰まっている
（お話し中状態で待たされる）
• メモリからデータを逐次で読み出しているの
と同じになる。
• キャッシュがないのと同じ。
• 演算器にデータが高速に届かず、演算パイプラインが
中断し、演算器の利用効率が悪くなる。
• 以上の現象を、（キャッシュの）＜スラッシング＞、
＜キャッシュライン衝突＞、＜キャッシュ合同＞
スパコンプログラミング（１）、（Ⅰ）
43
メモリインターリービング
物理的なメモリの格納方向に従いアクセスする場合
• データのアクセス時、現在アクセス中のメモリ上の管理
単位（バンク）上のデータは、周辺バンク上のデータも
一括して同一キャッシュライン上に乗せる機能がある
• ライン０のデータをアクセスしている最中に、ライン１中に
近隣のバンク内データを（並列に）持ってくることが可能
•
• メモリの＜インタリービング＞
• 演算機から見た場合、データアクセス時間の短縮になる
• 演算器が遊ぶ時間が少なくなる（＝演算効率が高くなる）
物理的なデータ格納方向に連続アクセスする
ループ構成にする
スパコンプログラミング（１）、（Ⅰ）
44
キャッシュライン衝突が起こる条件
• キャッシュラインへのメモリバンク割り付けは、
２冪の間隔で行っていることが多い
• たとえば、３２、６４、１２８など
• 特定サイズの問題（たとえば、１０２４次元）で、
性能が１／２～１／３、ときには１／１０になる
場合、キャッシュライン衝突が生じている
可能性が高い。
• 実際はもっと複雑なので、厳密な条件を見つける
ことは難しいが
2冪サイズでの配列確保は避けるべき
スパコンプログラミング（１）、（Ⅰ）
45
キャッシュライン衝突への対応
• キャッシュライン衝突が生じた場合防ぐ方法は以下
（このサイズの計算を避けるという自明な解以外）
1. パティング法：配列に（２冪でない）余分な領域を確
保し確保配列の一部の領域を使う。
•
•
余分な領域を確保したうえで、(&A)++；など
コンパイラによるオプション在り
2. データ圧縮法：計算に必要なデータのみ、
新しい配列をキャッシュライン衝突しないように
確保し、必要なデータを移す。
3. 予測計算法：キャッシュライン衝突が起こる回数を
予測するルーチンを埋め込み、そのルーチンを
配列確保時に呼ぶことで対応。
スパコンプログラミング（１）、（Ⅰ）
46
FX10特有の回避法
• Sparc64 Ivｆｘでは、L1キャッシュラインは2Wayのため、
キャッシュライン衝突が起こりやすい
• 特に、OpenMPなど、スレッド実行時には、起こる確率が増す
• そこで、OpenMPのスレッド実行の方法を、Staticから
Dynamic(Cyclic)にすることで、隣のコアがL2にロードした情報を再
利用し、L1キャッシュライン衝突を防げることが報告されている。
• !$OMP DO SCHEDULE(static,1)
• 参考
• 理化学研究所次世代スーパコンピュータ開発実施本部開発グループアプ
リケーション開発チーム南一生氏
「スーパーコンピュータ「京」におけるアプリケーションの高並列化と高性能
化」、SACSIS2012チュートリアル資料
http://sacsis.hpcc.jp/2012/files/SACSIS2012-tutorial1-pub.pdf
スパコンプログラミング（１）、（Ⅰ）
47
サンプルプログラムの実行
（行列-行列積）
スパコンプログラミング（１）、（Ⅰ）
48
ＵＮＩＸ備忘録
• emacsの起動： emacs 編集ファイル名
• ^x ^s （＾はcontrol）：テキストの保存
• ^x ^c ：終了
（ ^z で終了すると、スパコンの負荷が上がる。絶対にしないこと。）
^g : 訳がわからなくなったとき。
• ^k : カーソルより行末まで消す。
消した行は、一時的に記憶される。
• ^y : ^kで消した行を、現在のカーソルの場所にコピーする。
• ^s 文字列 : 文字列の箇所まで移動する。
• ^M x goto-line : 指定した行まで移動する。
•
スパコンプログラミング（１）、（Ⅰ）
49
ＵＮＩＸ備忘録その2
• rm ファイル名：ファイル名のファイルを消す。
• rm *~ : test.c~ などの、~がついたバックアップファイルを消す。使う時は
慎重に。*~ の間に空白が入ってしまうと、全てが消えます。
• ls : 現在いるフォルダの中身を見る。
• cd フォルダ名：フォルダに移動する。
• cd .. : 一つ上のフォルダに移動。
• cd ~ ：ホームディレクトリに行く。訳がわからなくなったとき。
• cat ファイル名：ファイル名の中身を見る
• make : 実行ファイルを作る
（Makefile があるところでしか実行できない）
• make clean : 実行ファイルを消す。
（clean がMakefileで定義されていないと実行できない）
スパコンプログラミング（１）、（Ⅰ）
50
ＵＮＩＸ備忘録その3
• less ファイル名：ファイル名の中身を見る(catでは
画面がいっぱいになってしまうとき）
• スペースキー : 1画面スクロール
• / : 文字列の箇所まで移動する。
• q ：終了（訳がわからなくなったとき）
スパコンプログラミング（１）、（Ⅰ）
51
行列-行列積のサンプルプログラムの注意点
• C言語版およびFortran言語版のファイル名
Mat-Mat-noopt-rb.tar
• ジョブスクリプトファイルmat-mat-noopt.bash
中のキュー名を u-lecture から
u-lecture5 (工学部共通科目)
に変更してから qsub してください。
• u-lecture : 実習時間外のキュー
• u-ecture5: 実習時間内のキュー
スパコンプログラミング（１）、（Ⅰ）
52
行列-行列積のサンプルプログラムの実行
（Ｃ言語版、Fortran言語でも同様）
以下のコマンドを実行する
$ cp /lustre/gt15/z30105/Mat-Mat-noopt-rb.tar ./
$ tar xvf Mat-Mat-noopt-rb.tar
$ cd Mat-Mat-noopt
• 以下のどちらかを実行
$ cd C : C言語を使う人
$ cd F : Ｆｏｒｔｒａｎ言語を使う人
• 以下は共通
$ make
$ qsub mat-mat-noopt.bash
• 実行が終了したら、以下を実行する
$ cat mat-mat-noopt.bash.oXXXX (XXXXは数字)
•
スパコンプログラミング（１）、（Ⅰ）
53
行列-行列積のサンプルプログラムの実行
• 以下のような結果が見えれば成功
(Fortran言語の場合)
N = 512
Mat-Mat time[sec.] =
1.41415309906006
MFLOPS = 189.820646364729
スパコンプログラミング（１）、（Ⅰ）
54
行列-行列積のサンプルプログラムの実行
• 以下のような結果が見えれば成功
(C言語の場合)
N = 512
Mat-Mat time = 1.243629 [sec.]
215.848505 [MFLOPS]
OK!
スパコンプログラミング（１）、（Ⅰ）
55
サンプルプログラムの説明（Ｃ言語）
• #define N
512
の、数字を変更すると、行列サイズが変更
できます
• #define DEBUG １
「１」にすると、行列-行列積の演算結果が
検証できます。
• MyMatMat関数の仕様
• Ｄｏｕｂｌｅ型N×N行列ＡとＢの行列積をおこない、
Ｄｏｕｂｌｅ型Ｎ×Ｎ行列Ｃにその結果が入ります
スパコンプログラミング（１）、（Ⅰ）
56
Fortran言語のサンプルプログラムの注意
• 行列サイズNNの宣言は、以下のファイルにあ
ります。
mat-mat-noopt.inc
• 行列サイズ変数が、ＮＮとなっています。
integer NN
parameter (NN=512)
スパコンプログラミング（１）、（Ⅰ）
57
演習課題
• MyMatMat関数（手続き）を、アンローリングな
どにより高速化してください
• どういうアンローリングの仕方がよいか、
最も高速となる段数、などを調べてください。
• コンパイラの最適化レベルを０にしてあります。
本演習では、最適化レベルをとりあえず０で固定
しておいてください。
• コンパイラによる最適化を行い、かつ手による
アンローリングしてもよいのですが、場合により
アンローリングの効果がなくなります。
スパコンプログラミング（１）、（Ⅰ）
58
レポート課題
[L１０] 行列-行列積について、メモリ連続アクセスとな
る場合と、不連続となる場合の性能を調査せよ。
2. [L１５] 行列-行列積のアンローリングを、i, j, k ループ
について施し、性能向上の度合いを調べよ。どのアン
ローリング方式や段数が高速となるだろうか。
1.
問題のレベルに関する記述：
•L00: きわめて簡単な問題。
•L10：ちょっと考えればわかる問題。
•L20：標準的な問題。
•L30：数時間程度必要とする問題。
•L40：数週間程度必要とする問題。複雑な実装を必要とする。
•L50：数か月程度必要とする問題。未解決問題を含む。
※L４０以上は、論文を出版するに値する問題。
スパコンプログラミング（１）、（Ⅰ）
59
参考文献（最適化全体）
1. 寒川光、「ＲＩＳＣ超高速化プログラミング技
法」、共立出版、ＩＳＢＮ４－３２０－０２７５０
－７、３,５００円
2. Kevin Dowd著、久良知真子訳、「ハイ・パ
フォーマンス・コンピューティング：ＲＩＳCワー
クステーションで最高の性能を引き出すため
の方法」、インターナショナル・トムソン・パブ
リッシング・ジャパン、ＩＳＢＮ４－９００７１８－
０３－３、４,４００円
スパコンプログラミング（１）、（Ⅰ）
来週へつづく
高性能プログラミング技法の基礎（２）
60

Download Report