07. 値予測 五島 正裕

内容 キャッシュの復習 値予測

キャッシュの復習

キャッシュとは キャッシュ： 本体の内容の一部を，より小容量ゆえに高速なメモリにコピー 参照の局所性 (locality of reference) を利用して，高速化を図る 一部をコピー ⇒ 連想メモリ (associative memory)

連想メモリ 表 (table)，メモリ： key と value のペア，タプル (tuple) の集合 非連想表，メモリ ex.) 半分とか，1/10 とか

ハッシュ表 ハッシュ表 (hash table) ソフトウェアで連想表と言えば… ただし通常（一部ではなく）全体が入っている

ハッシュ表 (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

ハッシュ表 （配列） 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

ハッシュ表 （配列，最適化） 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

キャッシュの構成 tag valid value address selector value

マッピング : 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

値予測

投機のフェーズ cycle 予測 (prediction) 実行 (execution) 確認 (verification, confirmation) キャンセル，回復，再実行 (cancellation, recovery, re-execution) cycle A 1. 予測 3. 確認 4. 再実行 B B 2. 実行

分岐予測 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

分岐予測 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 再フェッチ

分岐予測 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)

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

値予測するには 値予測するには： どう予測するか？ 予測するとどうなるか？ 予測ミスしたらどうするか？

1. どう予測するか？ やっぱり，履歴 (history) 分岐履歴：PHT (pattern history table) 値 履 歴 ：VHT (value history table) 予測手法： Last-Value Stride Context-Base Hybrid

キャッシュの構成 tag valid value address selector value

Last-Value + Stride 値予測器 確信度カウンタ (confidence counter) ヒット：インクリメント ミ ス ：デクリメント or クリア 閾値以上（最大値）なら予測

フロントエンドで予測する 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

予測する PC （アドレス）で予測表を牽く 命令フェッチと同時に予測値が分かる 依存する命令： ずっと以前にソースの値が決まっていたかのように見える

値予測 cycle I OR EX WB I OR EX WB I OR EX WB I OR EX WB

2. 予測するとどうなるか？ cycle I OR EX VRFY I OR EX VRFY I OR EX VRFY WB I OR EX

投機のフェーズ cycle 予測 (prediction) 実行 (execution) 確認 (verification, confirmation) キャンセル，回復，再実行 (cancellation, recovery, re-execution) cycle A 1. 予測 3. 確認 4. 再実行 B B 2. 実行

2. 予測するとどうなるか？ ソース（依存元の命令の結果）が予測できた命令： ディスパッチ後，直ちに実行可能 あたかも，フロー依存がなくなったかのうよう 実行命令数は減らない！ ミスの分だけ増える 残る制約は，資源制約のみ

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

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

今日のまとめ

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

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