Presentation is loading. Please wait.

Presentation is loading. Please wait.

07. 値予測 五島 正裕.

Similar presentations


Presentation on theme: "07. 値予測 五島 正裕."— Presentation transcript:

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 v value v value
function v value v value v value v value v value v value v value v value index v value v value v value v value v value 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 tag index selector value

11 マッピング : cache line way set cache address space direct map
8 4 8 1 1 2 2 3 3 4 cache address space direct map 2-way set-associative

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 RF 命令 ウィンドウ フロントエンド front-end バックエンド back-end RF 命令
キャッシュ 命令 ウィンドウ リネーム 演算器 ロジック フェッチ Fetch リネーム Rename ディスパッチ Dispatch スケジュール Schedule 発行 Issue 読出 OR 実行 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 2. 予測するとどうなるか? ソースが予測できた命令: ディスパッチ後,直ちに実行可能 あたかも,フロー依存がなくなったかのうよう
実行命令数は減らない! ミスの分だけ増える 残る制約は,資源制約のみ

27 3. 予測ミスしたらどうするか? 依存する命令をやり直す ただし,依存する命令は: 分岐予測:下流の命令すべて フラッシュ
値 予 測 :フロー依存関係にある命令 フラッシュ(下流の命令すべて) 予測ヒットの命令も,予測しなかった命令もやり直し 無駄が多い! 選択的無効化 ちょっと難しい

28 値予測の効果 高い予測率 予測ヒット率:20~80% 半定数が多い? ex) コマンド・ライン引数 低い性能向上
IPC の向上:-数%~十数% HW 量には見合いにくい 理由: 予測できる命令はクリティカル・パス上にない? 半定数なら,そう

29 今日のまとめ

30 値予測 (value prediction)
値予測: 投機の一種 個々の命令の結果を予測 先行制約の緩和 分岐予測:分岐命令の結果を予測 制御依存による先行制約を緩和 値 予 測 :すべての命令の結果を予測 データ依存(フロー依存)による先行制約の緩和

31 今後の予定 メモリ・ディスアンビギュエーション デバイスの微細化への対応 演算器クラスタリング 0次キャッシュ レイテンシ予測
マルチスレッド・プロセッサ SIMD 命令


Download ppt "07. 値予測 五島 正裕."

Similar presentations


Ads by Google