値予測

Advanced
Computer
Architecture
07. 値予測
五島正裕
Advanced Computer Architecture
内容
1. キャッシュの復習
2. 値予測
Advanced
Computer
Architecture
キャッシュの復習
Advanced Computer Architecture
キャッシュとは
 キャッシュ：
 本体の内容の一部を，より小容量ゆえに高速なメモリにコピー
 参照の局所性 (locality of reference) を利用して，高速化を図る
 一部をコピー ⇒ 連想メモリ (associative memory)
Advanced Computer Architecture
連想メモリ
 表 (table)，メモリ：
 key と value のペア，タプル (tuple) の集合
 非連想表，メモリ
 ∀key に対して，タプルがある
 連想表，メモリ
 ∀key に対して，タプルがあるとは限らない

ex.) 半分とか，1/10 とか
Advanced Computer Architecture
ハッシュ表
 ハッシュ表 (hash table)
 ソフトウェアで連想表と言えば…
 ただし通常（一部ではなく）全体が入っている
Advanced Computer Architecture
ハッシュ表 (chained hash table)
key
hash
function
index
int hash(int key) {
return 7 &
(key >> 0) ^
(key >> 3) ^
(key >> 6) ^
/* ... */ ;
}
key
key
value
value
key
value
Advanced Computer Architecture
ハッシュ表（配列）
int hash(int key) {
return 7 & key;
}
key
hash
function
index
key
v
value
key
v
value
key
v
value
key
v
value
key
v
value
key
v
value
key
v
value
key
v
value
key
v
value
key
v
value
key
v
value
key
v
value
key
v
value
key
v
value
key
v
value
key
v
value
way #0
way #1
Advanced Computer Architecture
ハッシュ表（配列，最適化）
int hash(int key) {
return 7 & key;
}
key
hash
function
index
tag
v
value
tag
v
value
tag
v
value
tag
v
value
tag
v
value
tag
v
value
tag
v
value
tag
v
value
tag
v
value
tag
v
value
tag
v
value
tag
v
value
tag
v
value
tag
v
value
tag
v
value
tag
v
value
Advanced Computer Architecture
キャッシュの構成
address
tag
value
valid
selector
value
Advanced Computer Architecture
マッピング
: cache line
set
way
address
address
0
0
4
1
1
5
2
2
6
3
3
7
0
8
cache
4
5
8
address space
2-way set-associative
6
7
cache address space
full associative
direct map
address
0
7
0
cache
1
2
address space
Advanced
Computer
Architecture
値予測
Advanced Computer Architecture
投機のフェーズ
1. 予測 (prediction)
2. 実行 (execution)
3. 確認 (verification, confirmation)
4. キャンセル，回復，再実行 (cancellation, recovery, re-execution)
cycle
A
1. 予測
3. 確認
2. 実行
B 4. 再実行
Advanced Computer Architecture
分岐予測
cycle
3. 確認
add r5 = r4 + r3
IF
OR
EX
MEM WB
be
IF
OR
EX
MEM WB
r1 == r2, L0
PC 予測
add r8 = r8 1.
+ 1
IF
OR
EX
MEM WB
IF
OR
EX
MEM WB
2. フェッチ
sub r9 = r6 - r7
IF
OR
EX
MEM WB
ld
IF
OR
EX
MEM WB
r8 = *(r9)
Advanced Computer Architecture
分岐予測
cycle
3. 確認
add r5 = r4 + r3
IF
OR
EX
MEM WB
be
IF
OR
EX
MEM WB
L0: ld
r1 == r2, L0
r8 = *(r6)
PC
add r9
r8 = r8 1.
+ 1
sla
<<
1 予測
IF
OR
IF
OR
EX
MEM WB
IF
OR
IF
OR
EX
MEM WB
2. フェッチ
add
sub r9 = r9
r6 +
- 1
r7
ld
r8 = *(r9)
4. 再フェッチ
IF
IF
OR
EX
M
IF
IF
OR
EX
M
Advanced Computer Architecture
分岐予測
cycle
add r5 = r4 + r3
IF
OR
EX
MEM WB
be
IF
OR
EX
MEM WB
L0: ld
r1 == r2, L0
r8 = *(r6)
sla r9 = r8 << 1
add r9 = r9 + 1
IF
OR
IF
OR
EX
MEM WB
IF
OR
IF
OR
EX
MEM WB
IF
IF
OR
EX
M
IF
IF
OR
EX
M
ミス･ペナルティ (= H, M = 0)
Advanced Computer Architecture
値予測
 値予測 (value prediction)：
 投機の一種
 個々の命令の結果を予測
 先行制約の緩和
 分岐予測：分岐命令の結果を予測

制御依存による先行制約を緩和
 値予測：すべての命令の結果を予測

データ依存（フロー依存）による先行制約の緩和
Advanced Computer Architecture
値予測するには
 値予測するには：
1. どう予測するか？
2. 予測するとどうなるか？
3. 予測ミスしたらどうするか？
Advanced Computer Architecture
1. どう予測するか？
 やっぱり，履歴 (history)
 分岐履歴：PHT (pattern history table)
 値履歴：VHT (value history table)
 予測手法：
 Last-Value
 Stride
 Context-Base
 Hybrid
Advanced Computer Architecture
キャッシュの構成
address
tag
value
valid
selector
value
Advanced Computer Architecture
Last-Value + Stride 値予測器
 キャッシュの value のフィールド：
 Last-Value
 Stride

予測値は，Last-Value + Stride
 確信度カウンタ (confidence counter)

ヒット：インクリメント

ミス：デクリメント or クリア

閾値以上（最大値）なら予測
Advanced Computer Architecture
フロントエンドで予測する
命令
キャッシュ
RFRF
リネーム
ロジック
F
N
フェッチ
Fetch
リネーム
Rename
22
命令
ウィンドウ
D
S
ディスパッチスケジュール
Dispatch
Schedule
フロントエンド
front-end
演算器
I
R
X
W
発行
Issue
Reg 読出
Reg Read
実行
Exec
書戻
WB
バックエンド
back-end
Advanced Computer Architecture
予測する
 PC （アドレス）で予測表を牽く
 命令フェッチと同時に予測値が分かる
 依存する命令：
 ずっと以前にソースの値が決まっていたかのように見える
Advanced Computer Architecture
値予測
cycle
I OR
EX
I OR
WB
EX
I OR
WB
EX
I OR
WB
EX
WB
Advanced Computer Architecture
2. 予測するとどうなるか？
cycle
I
OR
I OR
EX
VRFY
I OR
EX
VRFY
EX
WB
I OR
EX
I OR
EX
VRFY
I OR
WB
EX
VRFY
Advanced Computer Architecture
投機のフェーズ
1. 予測 (prediction)
2. 実行 (execution)
3. 確認 (verification, confirmation)
4. キャンセル，回復，再実行 (cancellation, recovery, re-execution)
cycle
A
1. 予測
3. 確認
2. 実行
B 4. 再実行
Advanced Computer Architecture
2. 予測するとどうなるか？
 ソース（依存元の命令の結果）が予測できた命令：
 ディスパッチ後，直ちに実行可能
 あたかも，フロー依存がなくなったかのうよう
 実行命令数は減らない！
 ミスの分だけ増える
 残る制約は，資源制約のみ
Advanced Computer Architecture
3. 予測ミスしたらどうするか？
 依存する命令をやり直す
 ただし，依存する命令は：
 分岐予測：下流の命令すべて

フラッシュ
 値予測：フロー依存関係にある命令

フラッシュ（下流の命令すべて）
– 予測ヒットの命令も，予測しなかった命令もやり直し
– 無駄が多い！

選択的無効化
– ちょっと難しい
Advanced Computer Architecture
値予測の効果
 高い予測率
 予測ヒット率：20～80%
 半定数 (semi-constant）が多い？
ex) コマンド・ライン引数
 低い性能向上
 IPC の向上：－数%～十数%
 HW 量には見合いにくい
 理由：
 予測できる命令はクリティカル・パス上にない？
 半定数なら，そう
Advanced
Computer
Architecture
今日のまとめ
Advanced Computer Architecture
値予測 (value prediction)
 値予測：
 投機の一種
 個々の命令の結果を予測
 先行制約の緩和
 分岐予測：分岐命令の結果を予測

制御依存による先行制約を緩和
 値予測：すべての命令の結果を予測

データ依存（フロー依存）による先行制約の緩和
Advanced Computer Architecture
今後の予定
 メモリ・ディスアンビギュエーション
 デバイスの微細化への対応
 演算器クラスタリング
 0次キャッシュ
 レイテンシ予測
 マルチスレッド・プロセッサ
 SIMD 命令

Download Report