2015年1月27日 公聴会

Optimizing Utilization of Memory Hierarchy
Based on Code Motion

東京理科大学大学院 理工学研究科 情報科学専攻
滝本研究室 博士後期課程 3 年
澄川 靖信

1

コンピュータのメモリ構成

マザーボード2

コンピュータのメモリ構成
メイン
メモ
リ

3

コンピュータのメモリ構成
レジスタ制御キャッシュメモリ

メイン
メモ
リ

4

データ転送の様子
main(){x=a[i];}配列a[i]のデータ：メモリに配置
変数xのデータ：レジスタに配置

Cプログラム※ 本発表で使用する全てのプログラムはＣ言語で書かれていると仮定する．

5データ転送の様子
main(){x=a[i];}
制
御レジス
タキ
ャッシ
ュ

メイン
メモ
リ

6

データ転送の様子
main(){x=a[i];a[i]のデータ}
はある？

制
御レジス
タキ
ャ
ッシ
ュ

メイン
メモ
リ

7

データ転送の様子
main(){x=a[i];}キャッシュミス
制
御レジス
タキャッシ
ュ

メイン
メモ
リ

8

データ転送の様子
main(){x=a[i];}
制
御レ
ジス
タキ
ャ
ッシ
ュ

メ
a[i]

イン
メモ
リ

9

問題点


プロセッサとメインメモリの性能差が拡大．


メインメモリのアクセスによるペナルティ増加を意味する

Hennessy,J.L. elc.:Computer Architecture: A Quantitative Approach 4th Edition,2007. 10

本研究の目的

メモリ階層を効率良く使用するプログラムを生成するコンパイラのコード最適化の手法を提案する．
1. メモリ参照をレジスタ参照へ変換

不要に実行される配列参照を除去する

2. キャッシュメモリのミス数の低減
参照の局所性を利用

11

本研究の目的

メモリ階層を効率良く使用するプログラムを生成するコンパイラのコード最適化の手法を提案する．
1. メモリ参照をレジスタ参照へ変換

不要に実行される配列参照を除去する

レジスタ
キャッシュ

1. メモリ参照をレジスタ参照へ変換

メインメモリ
12

本研究の目的

メモリ階層を効率良く使用するプログラムを生成するコンパイラのコード最適化の手法を提案する．
1. メモリ参照をレジスタ参照へ変換

不要に実行される配列参照を除去する

main(){
x=a[i];
y=a[i];}

a[i]を除去main(){
x=a[i];y=x;}
13

本研究の目的

メモリ階層を効率良く使用するプログラムを生成するコンパイラのコード最適化の手法を提案する．
2. キャッシュメモリのミス数の低減
参照の局所性を利用

レジスタ
キャッシュ
メインメモリ14

キャッシュメモリのミス数の低減


メモリ容量
キャッシュメモリ < メインメモリ→ キャッシュメモリにデータを配置するとき，古いデータをキャッシュから除去する
メ
a[i]

キャ
ッシュ

イン
メモ
リ

15

実現方法


コンパイラのコード最適化の手法として実現.cコンパイラ

機械語

1. 字句解析
2. 構文解析3. 意味解析4. コード最適化（効率の良いコードへの変換）
5. コード生成
16

COINSコンパイラ

字句解析
構文解析
意味解析

本手法

17

本研究の貢献メモリ参照の回数を低減

高速な解析法に基いて冗長なメモリ参照を除去．（3章）- 従来法よりも平均で約50%高速な解析法を実現
ループの繰返しを超えて冗長な配列参照を除去できるように拡張した手法を実現．（4章）- 従来法よりも実行効率を2%程度向上する．

キャッシュメモリのミス数を低減（5章）


同じ配列へのアクセスを，次元を考慮しながら連続させる．
- ミスを30%程度低減する．
18

目次
1.

効率的な要求駆動型部分冗長除去（PRE）（3章）


2.

要求駆動型スカラ置換（4章）


3.

ループの繰返しを超えて冗長なメモリ参照をレジスタ参照へ変換する．

大域ロード命令集約（5章）
4.

冗長なメモリ参照をレジスタ参照へ変換する．

PREを拡張してキャッシュミス数を低減する．

まとめ
19

目次
1.

効率的な要求駆動型PRE（3章）


2.

要求駆動型スカラ置換（4章）


3.

ループの繰返しを超えて冗長なメモリ参照をレジスタ参照へ変換する．

大域ロード命令集約（5章）


4.

冗長なメモリ参照をレジスタ参照へ変換する．

PREを拡張してキャッシュミス数を低減する．

まとめ20

本手法の対象
1. メモリ参照をレジスタ参照へ変換

レジスタ
キャッシュ
メインメモリ21

冗長な式の除去


条件分岐が無い場合は前回の結果を参照すれば良い．

main(){
x=a[i];
y=a[i];}

a[i]を除去main(){
x=a[i];y=x;}22

部分冗長除去（PRE）


一部の実行経路上だけで冗長な式を除去する手法

main(){
if(…){
x=a[i];}else{}
y=a[i];}

23

制御フローグラフ

プログラムの制御の様子をグラフで表現

x=a[i]y=a[i]24PREによる冗長な式の除去の方法

x=a[i]

y=a[i]

t=a[i]x=t

t=a[i]

y=t25

一般的なPRE

字面の一致性を用いてプログラム全体を解析．
冗長性を除去した後にコピー伝播を適用する→ 除去できる冗長性が出現する．（副次的効果）
 PREとコピー伝播を繰返し適用する必要がある．

26

一般的なPREb=a[i]
c=a[i]
x=a[b+1]y=a[c+1]27一般的なPREb=a[i]
c=a[i]

データフロー解析を用いてプログラム全体を解析

x=a[b+1]y=a[c+1]28一般的なPREt=a[i]b=t
冗長性の除去c=t
x=a[b+1]y=a[c+1]29一般的なPREt=a[i]
b=t
コピー伝播の適用

c=t
x=a[t+1]y=a[t+1]30一般的なPRE
t=a[i]b=t

c=t
x=a[t+1]
字面が同じ

y=a[t+1]31効率的な要求駆動型PRE


効率的な要求駆動型PRE

コピー伝播を適用せずに１回の適用で副次的効果を反映
クエリを伝播しプログラムの限定的な範囲で冗長性を解析
値番号の出現を記録し，不要なクエリの伝播を防ぐ

Sumikawa, Y. and Takimoto, M.: Effective Demand-driven Partial
Redundancy Elimination, Information Processing Society of Japan
Transactions on Programming, Vol. 6, No. 2(2013), pp. 33–44.
32効率的な要求駆動型PREのアルゴリズム
1.

大域値番号付けを適用し異なる字面の一致性を解析
Ex. a=bというプログラムが存在したとき，aとbに対して[1]という値番号を付加する．

2.

質問伝播を適用して冗長性を除去
質問伝播：プログラムの解析範囲を狭めて解析効率を向上

33大域値番号付け
b=a[i]

i

[1]

a[i]

[2]

c=a[i]
x=a[b+1]y=a[c+1]34

大域値番号付け
b=a[i]
c=a[i]

i[1]

a[i]

[2]

b
c

[2]

[2]

x=a[b+1]y=a[c+1]35

大域値番号付け
b=a[i]
c=a[i]

i

[1]

a[i]

[2]

b
c

[2]

[2]+1

[3]

[2]

x=a[b+1]y=a[c+1]36

大域値番号付け
b=a[i]
c=a[i]
x=a[b+1]y=a[c+1]

i

[1]

a[i]

[2]

b
c

[2]

[2]+1

[3]

a[[2]+1]

[4]

x
y[4]

[2]

[4]
37

質問伝播
[2]

b=a[i][2]c=a[i][4] x=a[b+1][4] y=a[c+1]
38

質問伝播
[1], [2][2]b=a[i][1], [2][2]c=a[i][1], [2],[3],[4][4] x=a[b+1][4] y=a[c+1]
39

質問伝播
[1], [2][2]b=a[i][1], [2][2]c=a[i][1], [2],[3],[4][4] x=a[b+1][4]は冗長か[4] y=a[c+1]
40

質問伝播
[1], [2][2]b=a[i][1], [2][2]c=a[i][1], [2],[3],[4][4] x=a[b+1]true[4] y=a[c+1]41質問伝播[1], [2][2]b=a[i][1], [2][2]c=a[i][1], [2],[3],[4][4] x=a[b+1][4] y=x42

不要なクエリ伝播の防止[1], [2][2]b=a[i][1], [2][2]c=a[i][1], [2],[3],[4][4] x=a[b+1][7] y=a[c+2]43不要なクエリ伝播の防止[1], [2][2]b=a[i][1], [2][2]c=a[i][1], [2],[3],[4][4] x=a[b+1]

3つ目の節までに[7]は出現しない[7]は冗長か[7] y=a[c+2]44不要なクエリ伝播の防止[2]b=a[i][2]c=a[i][4] x=a[b+1][7] y=a[c+2]

false
45

実験

COINSコンパイラのLIR変換器として実装

ベンチマーク

SPEC2000

解析効率（コンパイル時間）を比較



最適化の組み合わせ


PRE*2



EDDPRE：提案手法：従来手法のPREを2回適用する．

46

実験 | 解析効率

最大で約70%の向上
47

目次
1.

効率的な要求駆動型PRE（3章）
2.

要求駆動型スカラ置換（4章）


3.

ループの繰返しを超えて冗長なメモリ参照をレジスタ参照へ変換する．

大域ロード命令集約（5章）


4.

冗長なメモリ参照をレジスタ参照へ変換する．

PREを拡張してキャッシュミス数を低減する．

まとめ48

本手法の対象
1. メモリ参照をレジスタ参照へ変換

レジスタ
キャッシュ
メインメモリ49

スカラ置換のモチベーション

i=0;
while(i<10){x=a[i];
y=a[i+1];
i++;
}

50

スカラ置換のモチベーション

i=0;while(i<10){x=a[i];
y=a[i+1];
i++;
}

i=0:
x=a[0]
y=a[1]

51

スカラ置換のモチベーション

i=0;
while(i<10){x=a[i];
y=a[i+1];
i++;
}

i=0:
x=a[0]
y=a[1]i=1:
x=a[1]
y=a[2]

52

スカラ置換のモチベーション

i=0;
while(i<10){x=a[i];
y=a[i+1];
i++;
}

i=0:
x=a[0]
y=a[1]i=1:
x=a[1]
y=a[2]i=2:
x=a[2]
y=a[3]
53

スカラ置換のモチベーション

i=0;
while(i<10){x=a[i];
y=a[i+1];i++;}a[i+1]の値と次の繰返しのときのa[i]の値が同じ

i=0:x=a[0]y=a[1]i=1:
x=a[1]
y=a[2]i=2:
x=a[2]
y=a[3]
54

スカラ置換

複数の繰返し内で冗長な配列参照を除去する．
従来法
可約なループだけが対象
 ループ1つ1つに対して適用していた→ プログラム全体で見ると挿入した配列参照が冗長となりうる．


要求駆動型スカラ置換
既約なループも扱える．
 プログラム全体から適切な挿入点を求める．
澄川靖信，小島量，滝本宗宏: 要求駆動型スカラ置換，コンピュータソフト
ウェア, 採録決定.
55

要求駆動型スカラ置換の概説
a[i]の値は冗長？

x=a[i]

y=a[i+1]i=i+156

要求駆動型スカラ置換の概説

a[i]の値は冗長？

x=a[i]

y=a[i+1]i=i+157

要求駆動型スカラ置換の概説

a[i]の値は冗長？

x=a[i]

y=a[i+1]
i=i+158

要求駆動型スカラ置換の概説

a[i]の値は冗長？

x=a[i]

y=a[i+1]
n-1回目の繰返し

i=i+1n回目の繰返し59

要求駆動型スカラ置換の概説

x=a[i]一致

y=a[i+1]a[i+1]の値は冗長？

i=i+160

要求駆動型スカラ置換の概説
false
true

x=a[i]

y=a[i+1]
i=i+161

要求駆動型スカラ置換の概説

y=a[i]x=y

y=a[i+1]
i=i+162

要求駆動型スカラ置換の概説
a[i-1]の値は冗長？

x=a[i-1]y=a[i+1]
i=i+163

実験結果
環境





コンパイラ：COINS （Cコンパイラ）
CPU：Xeon E5-1660 3.3GHz
OS: Debian 64bit
ベンチマーク：SPEC2000


各プログラムのループだけを使用した．

最適化
TSR+: 一般的なスカラ置換の従来法
PRESR: 提案手法, 3回前の繰返しまでを解析

64

実験結果 | 実行効率（秒）最大で約3.4%の向上
65

目次
1.

効率的な要求駆動型PRE（3章）


2.

要求駆動型スカラ置換（4章）


3.

メモリ参照をレジスタ参照へ変換する．

大域ロード命令集約（5章）


4.

冗長なメモリ参照をレジスタ参照へ変換する．

PREを拡張してキャッシュミス数を低減する．

まとめ66

本手法の対象

2. キャッシュメモリのミス数を低減

レジスタ
キャッシュメインメモリ
67

大域ロード命令集約


大域ロード命令集約
メモリ参照の局所性を効率良く利用できるようにPREを拡張→ キャッシュミス数を低減する．
Sumikawa, Y., Takimoto, M.: Global load instruction
aggregation based on code motion. PAAP ’12, IEEE Computer
Society, pp.149–156
68モチベーションb[i]0000b[i+1] 0001
・・

00

main(){...=a[i]01...=b[i]10...=a[i+1]}
11

a[i]

1000

a[i+1] 1001
・・キャッシュメインメモリ69

モチベーション

b[i]

0000

b[i+1] 0001

00 a[i] a[i+1]main(){...=a[i]01...=b[i]10...=a[i+1]}
11・
・
a[i]

1000

a[i+1] 1001

・・
1000(2)(10進数：8)をライン数（4）で割った余りの番地に配置する．
キャッシュ
メインメモリ70

モチベーション

b[i]

0000

b[i+1] 0001

00 a[i] a[i+1]main(){...=a[i]01...=b[i]10...=a[i+1]}
11・
・
a[i]

1000

a[i+1] 1001

キャッシュミスキャッシュ・・

メインメモリ71

モチベーション

b[i]

0000

b[i+1] 0001

00 b[i] b[i+1]main(){...=a[i]01...=b[i]10...=a[i+1]}
11・
・
a[i]

1000

a[i+1] 1001
・・
キャッシュ

メインメモリ72

モチベーション

b[i]

0000

b[i+1] 0001

00 b[i] b[i+1]main(){...=a[i]01...=b[i]10...=a[i+1]}
11・
・
a[i]

1000

a[i+1] 1001

キャッシュミスキャッシュ・・

メインメモリ73

モチベーション
同じ配列のデータを同時に配置

00 b[i] b[i+1]

b[i]

0000

b[i+1] 0001
・・

main(){
a[i] 1000...=a[i]01...=b[i]a[i+1] 1001
10
同じ配列へのアクセスを連続する...=a[i+1]よう式の順序を入れ替えれば良い．
・
}
11・

キャッシュ

メインメモリ74

大域ロード命令集約の実現


PREの1つの実現方法で怠けたコード移動を拡張

x=a[i]

y=a[i]

75

怠けたコード移動のアルゴリズム
1. 式を挿入できる最も開始節に近い節を求める．

t=a[i]

x=a[i]

y=a[i]

76

怠けたコード移動のアルゴリズム
2. 式の挿入を可能な限り遅らせる．

t=a[i]

x=a[i]

y=a[i]

77

怠けたコード移動のアルゴリズム
3. 式を挿入して冗長性を除去する．

t=a[i]x=t

t=a[i]

y=t78

大域ロード命令集約のアルゴリズム
1. 式を挿入できる最も開始節に近い節を求める．

t=a[i+1]x=a[i]

y=b[i]
z=a[i+1]
79

大域ロード命令集約のアルゴリズム
2. 式の挿入を可能な限り遅らせる．

x=a[i]

t=a[i+1]y=b[i]
z=a[i+1]80

大域ロード命令集約のアルゴリズム
2. 式の挿入を可能な限り遅らせる．

x=a[i]
t=a[i+1]y=b[i]
z=a[i+1]81

大域ロード命令集約のアルゴリズム
3. 式を挿入して冗長性を除去する．

x=a[i]
t=a[i+1]y=b[i]z=t82

多次元配列への拡張

比較的サイズが大きい配列の場合


同じ配列への参照を連続させても効果が無い場合がある．

多次元配列


上位次元がその下位次元の配列とみなせる．

Sumikawa, Y., Takimoto, M.: Global Load Instruction Aggregation
Based on Array Dimensionsload. PAAP ’14, IEEE Computer Society,pp.123–129
83

多次元配列への拡張

・・・

a[i][j]main(){...=a[i][j]...=a[k][l]...=a[i][j+1]}

a[i][j+1]・・・

a[k][l]a[k][l+1]※ C言語を仮定したときのメモリレイアウト．

配列a[i]

メインメモリ

配列
a[k]
84

実験結果
環境







コンパイラ：COINS
CPU：core2duo 1.6GHz
OS: CentOS
ベンチマーク：SPEC2000

最適化



LCM-MEM :怠けたコード移動
GLIA: 大域ロード命令集約
MDGLIA:次元を考慮した大域ロード命令集約

85

キャッシュメモリのパラメータ86実験結果 | キャッシュミス数

最大で約30%の向上

87

キャッシュミス増加の原因
レジスタスピル増加

x=a[i]
t=a[i+1]y=b[i]z=ta[i+1]のデータをレジスタが保持する期間の増分
88

まとめ | メモリ階層最適化の提案
メモリ参照のレジスタ参照への変換


従来法より解析効率が約50%良いPREの提案（3章）
プログラム全体の中で適切な挿入点を求め，繰返しを越えて冗長となる配列参照を除去するPRESRの提案（4章）


従来法よりも平均で約2%，最大で約3.4%の実行効率の向上

キャッシュミス低減によるメインメモリ参照の低減


同じ配列へのアクセスを連続にするGLIAの提案（5章）
多次元配列の集約行うMDGLIAの提案（5章）


L2キャッシュミスを最大で30%低減．

コード移動によるメモリ階層最適化の枠組みを与えた
89