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