07. 値予測 五島 正裕.

Slides:



Advertisements
Similar presentations
2.5 プログラムの構成要素 (1)文字セット ① ASCII ( American Standard Code for Interchange ) JIS コードと同じ ② EBCDIC ( Extended Binary Coded Decimal for Information Code ) 1.
Advertisements

CPU設計と パイプライン.
プログラミング演習II 2004年11月 30日(第6回) 理学部数学科・木村巌.
情報理工学系研究科 コンピュータ科学専攻 上嶋裕樹
07. 値予測 五島 正裕.
■ディレクトリエントリキャッシュ linuxではdentryという構造体に、ファイルパス名の情報を格納しメモリ上にキャッシングしている。
ヘテロジニアスマルチコアプロセッサ 環境を対象としたキャッシュシステム 自動生成ツールの開発
基本情報技術概論(第10回) 埼玉大学 理工学研究科 堀山 貴史
Ibaraki Univ. Dept of Electrical & Electronic Eng.
VLSI設計論第4回 アキュムレータマシンと 仮遅延シミュレーション
高性能コンピューティング学講座 三輪 忍 高性能コンピューティング論2 高性能コンピューティング論2 第4回 投機 高性能コンピューティング学講座 三輪 忍
4. 順序回路 五島 正裕.
キャッシュ 頻繁にアクセスされるデータを入れておく小規模高速なメモリ 当たる(ヒット)、はずれる(ミスヒット) マッピング(割り付け)
Explorations in Symbiosis on two Multithreaded Architectures
第6章 トランザクション管理 6.1 トランザクションの概念 6.2 同時実行制御 6.3 障害回復.
オリジナルなCPUの開発 指導教授:笠原 宏 05IE063 戸塚 雄太 05IE074 橋本 将平 05IE089 牧野 政道
App. A アセンブラ、リンカ、 SPIMシミュレータ
プロセッサ設計教育のための 命令セット・スーパースカラシミュレータの試作と評価
高性能コンピューティング論2 第1回 ガイダンス
第5回 CPUの役割と仕組み3 割り込み、パイプライン、並列処理
高性能コンピューティング論2 第5回 Out-of-Order実行機構
基本情報技術概論(第8回) 埼玉大学 理工学研究科 堀山 貴史
第7回 2006/6/12.
SpectreとMeltdown ITソリューション塾・第28期 2018年5月30日 株式会社アプライド・マーケティング 大越 章司
Advanced Computer Architecture
・ディジタル回路とクロック ・プロセッサアーキテクチャ ・例外処理 ・パイプライン ・ハザード
プロジェクト実習 LSIの設計と実現 パイプライン実行とハザード.
アドバンスト コンピュータ アーキテクチャ RISC と 命令パイプライン
作りながら学ぶコンピュータアーキテクチャ(改訂版)授業資料 テキスト ページ対応 天野英晴
非レイテンシ指向 レジスタ・キャッシュ・システム
2. 論理ゲート と ブール代数 五島 正裕.
勉強会その3    2016/5/1 10 8分35秒 データの表現 演算.
11. マルチスレッド・プロセッサ 五島 正裕.
最適化の方法 中田育男著 コンパイラの構成と最適化 朝倉書店, 1999年 第11章.
情報理工学系研究科 電子情報学専攻 豊島隆志
コンピュータ系実験Ⅲ 「ワンチップマイコンの応用」 第1週目 アセンブリ言語講座
ディジタル回路 6. 順序回路の実現 五島 正裕.
10. マルチスレッド・プロセッサ 五島 正裕.
Advanced Computer Architecture
第10章 これはかなり大変な事項!! ~ポインタ~
レジスタ間接分岐ターゲット・フォワーディング
Advanced Computer Architecture
Advanced Computer Architecture
オペレーティングシステムJ/K (仮想記憶管理)
動的データ依存関係解析を用いた Javaプログラムスライス手法
3. 論理ゲート の 実現 五島 正裕.
Javaバイトコードの 動的依存解析情報を用いた スライシングシステムの実現
メモリ投機を支援する CMPキャッシュコヒーレンスプロトコルの検討
計算機構成 第3回 データパス:計算をするところ テキスト14‐19、29‐35
計算機構成 第4回 アキュムレータマシン テキスト第3章
一時的な型 長谷川啓
08. メモリ非曖昧化 五島 正裕.
計算機構成 第11回 マルチサイクルCPU 慶應大学 天野英晴.
C言語を用いたマシン非依存な JITコンパイラ作成フレームワーク
09. メモリ・ディスアンビギュエーション 五島 正裕.
坂井 修一 東京大学 大学院 情報理工学系研究科 電子情報学専攻 東京大学 工学部 電気工学科
コンピュータアーキテクチャ 第 10 回.
IF文 START もしも宝くじが当たったら 就職活動する 就職活動しない YES END NO.
コンピュータアーキテクチャ 第 2 回.
アルゴリズムとデータ構造1 2006年7月4日
コンピュータアーキテクチャ 第 2 回.
計算機アーキテクチャ1 (計算機構成論(再)) 第二回 命令の種類と形式
SpectreとMeltdown ITソリューション塾・第27期 2018年3月20日 株式会社アプライド・マーケティング 大越 章司
SMP/マルチコアに対応した 型付きアセンブリ言語
コンピュータ工学基礎 マルチサイクル化とパイプライン化 テキスト9章 115~124
IPmigrate:複数ホストに分割されたVMの マイグレーション手法
Ibaraki Univ. Dept of Electrical & Electronic Eng.
値渡しと参照渡しについて.
6.3 インタプリタ (1)インタプリタ(interpreter)とは
情報システム基盤学基礎1 コンピュータアーキテクチャ編
Presentation transcript:

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 命令