高性能コンピューティング論２ 1 高性能コンピューティング論２ 第7回 メモリ非曖昧化 高性能コンピューティング学講座 三輪 忍 [email protected] 高性能コンピューティング論２ 本日の講義内容 • メモリに関するデータ依存 • メモリ非曖昧化 2 高性能コンピューティング論２ 3 メモリに関するデータ依存 高性能コンピューティング論２ 4 復習： データ依存 • 制御駆動型 (control-driven) （⇔ データ駆動，data-driven） • 命令間のデータの授受は， • プログラム･オーダ上で，先行/後続 の関係にある 2命令が， • 同一のロケーションを ライト ⇒ リード する ことで表現 • ロケーション：レジスタ と メモリ Write add r4 = r1 + r2 add r5 = r4 + r3 Read ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「メモリ非曖昧化」より 高性能コンピューティング論２ 5 復習： データ依存 後続命令 Read Read Ip Ip Is Is time 先 行 命 令 Write time 入力依存 (input) 逆依存 (anti) Write Ip Ip Is Is time time フロー依存 (flow) 出力依存 (output) ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「スーパスカラ・プロセッサの基礎」より 高性能コンピューティング論２ 6 ロード/ストア命令とメモリ依存 • ロード命令 • r[Rt] = *(r[Rs] + immediate); • ストア命令 • *(r[Rs] + immediate) = r[Rt]; op Rs 25 31 Rt 20 後続命令 Read Read 先 行 命 令 Write ld r1 = *A ld r1 = *A ld r2 = *A st *A = r2 入力依存 (input) 逆依存 (anti) Write st *A = r1 st *A = r1 ld r2 = *A st *A = r2 フロー依存 (flow) 出力依存 (output) immediate 15 0 高性能コンピューティング論２ 7 レジスタ と メモリ の違い • レジスタ番号 • 少数 • 高々 25 個程度 • 簡単なハードウェアで依存関係を追跡可能 • 静的 • （実行の度に）変わらない • フロントエンド（デコード・ステージ）で分かる • メモリのアドレス • 多数 • 232 種類 • 完全に依存関係を追跡しようとすると，ハードウェアが複雑化 • 動的 • 実行の度に変わり得る • バックエンド（アドレス計算（実行）ステージ）で初めて分かる：「曖昧」 高性能コンピューティング論２ メモリ依存への保守的な対処法 • 保守的な解決策 • すべてのロード/ストアは先行するロード/ストアに依存すると仮定 • すべてのロード/ストアを in-order で実行 • 性能はあまり高くない（理想的な場合の1/2程） • プログラム中のロード/ストアの割合： 2～4割程度 • 「偽の依存」が存在 • アドレス計算してみたら，依存関係がないことがわかった 8 高性能コンピューティング論２ 9 ロード/ストアの Out-of-Order 実行 • できるだけ正確にスケジューリング • メモリ依存を解析し，依存関係が存在しないことが判明した時点で実行 • 投機的手法 • 依存関係が存在しないと予測して out-of-order に実行 • メモリ順序違反を検出したらキャンセル，再実行 • すべて out-of-order 実行した場合，0～7%のロードが順序違反を起こす • ロード/ストアの依存関係を賢く予測 高性能コンピューティング論２ 10 ロード/ストア命令のスケジューリングの重要性 • 性能に強く影響 • すべて in-order 実行した場合と理想的なスケジューリングとは２倍の差 • 上手にスケジューリングすると計算のかたまりがオーバーラップするため • 計算のかたまり： ロードで始まり，ストアで終わる ILP • ロード/ストアのスケジューリングの目標 • ロードをできるだけ早く実行する • ストアは遅くてもよい ld ILP ld ld • 依存する命令がクリティカル・パス上にない st （ことが多い） • 結局，リオーダ・バッファで待たされる （正確な例外を保証するため） ld st st ILP: Instruction Level Parallelism st [ in-order 実行の場合 ] [ 理想的な場合 ] 高性能コンピューティング論２ メモリ非曖昧化 11 高性能コンピューティング論２ メモリ・ディスアンビギュエーション • ディスアンビギュエーション (disambiguation)： • 「非曖昧化」，「曖昧性除去（解消）」 • メモリ・ディスアンビギュエーション • ロード/ストアを out-of-order 実行するための技術の総称 • メモリ依存の解析 • メモリ順序違反の検出，回復 12 高性能コンピューティング論２ メモリ非曖昧化の代表的な手法 • 分離ロード/ストア ＋ ロード/ストアキュー • ストアセット予測 13 高性能コンピューティング論２ 14 ロード/ストア命令 • 通常のロード/ストア命令： • アドレス計算部 • メモリ・アクセス部 • ロード命令 ：r[Rt] = *(r[Rs] + immediate); • ストア命令： *(r[Rs] + immediate) = r[Rt]; op 31 Rs 25 Rt 20 immediate 15 0 ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「メモリ非曖昧化」より 高性能コンピューティング論２ 15 分離 ロード/ストア (split load/store) • 通常のロード/ストア命令： • アドレス計算部 • メモリ・アクセス部 • 分離 ロード/ストア： • ディスパッチ時に分離，以降 2つの命令としてスケジューリング • 効果： • ストア・バリューがなくても，アドレス計算が開始できる • バリューより，アドレスが早く決まることが多い • ロードは変わらない • バリューに相当するソース・オペランドがないから ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「メモリ非曖昧化」より 高性能コンピューティング論２ 16 ロード/ストアキューによるメモリ非曖昧化 • 方針 • ロードの実行時にメモリ依存を解析 • メモリ依存が存在しないことが判明したら，先行するロード/ストアを追い 越して命令を実行 • ロード/ストアキュー • プロセッサに投入されたロード/ストア命令を格納するバッファ • ロード/ストア命令のプログラム・オーダと，実効アドレス，データを管理 • ロードの実行時にキューを参照し，以下のいずれかの場合に実行中止 • 先行するストアと実効アドレスが一致し，ストアデータが未解決だった場合 • 先行するストアの実効アドレスが（1つでも）未解決だった場合 高性能コンピューティング論２ 17 ロード/ストアキュー • 更新方法 • ロード/ストアのディスパッチ時に エントリを順に割り当て • 実効アドレスやストアデータが計 算されるとエントリを更新 実効アドレス ストアデータ st *A = r1 A ld r2 = *B B 100 ≠ • スケジューリング • ストア： • キューの先頭から順に • 実効アドレスとストアデータが揃っ ていたらキャッシュに反映 • ロード： • 自身よりも上位のエントリと実効ア ドレスを比較 • アドレスが一致しないことが確定し たらキャッシュのアクセスを開始 st A ld 100 B データキャッシュへ 高性能コンピューティング論２ 18 ストアフォワーディング レジスタへ • ロードのアドレスが先行する ストアのアドレスと一致 実効アドレス ストアデータ st *B = r3 B • データキャッシュにアクセスしない st *A = r1 A • ロード/ストアキューからデータ供給 ld r2 = *A A 100 • メリット • ロードのレイテンシの短縮 • キャッシュ・ポートの浪費を防止 データキャッシュへ 高性能コンピューティング論２ 19 ロード/ストアキューの問題点 • スケジューリングが（まだ）保守的 • 先行するすべてのストアのアドレスが解決するまでロードの発行は不可 • 偽の依存が存在 • ハードウェアが複雑 • スケジューリングのために，比較器のマトリクス（行列）が必要 • 比較器数 ≒ ½ ×（ウィンドウ・サイズ）２ 高性能コンピューティング論２ 20 発行可能検出 ― 比較器のマトリクス L/S V 0 effective address 0 1 2 3 4 先行命令 ready? ― ― 1 0 ― 0 = 0 ≠ 1 Valid Load 1 2 =? L/S Store 1 3 4 5 後続 ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「メモリ非曖昧化」より 高性能コンピューティング論２ 21 ストア・セット • あるロードのストア・セットとは： • そのロードが依存したことがあるストアの集合 • 計算の方法：recovery-based • 最初「依存していない」としておいて， • 順序違反 (memory-order violation) を検出して，追加 • 利用の方法： • ロードは，そのストア・セット内のストアに依存すると予測 ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「メモリ非曖昧化」より 高性能コンピューティング論２ 22 予測器の実装 • 原理的には： • ストア・セット内のすべてのストアが実行された後でロードを実行 • 実装上の制限： • ストア・セット内のストアは in-order で実行 • In-order チェイン： • ストア → ストア → … → ストア → ロード ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「メモリ非曖昧化」より 高性能コンピューティング論２ 23 構造と動作 SSID Table S1 SSID X S S2 S L L SSID X Last Fetched Store Table S21 X SSID X PC of Fetched Instructions SSID : Store Set ID ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「メモリ非曖昧化」より 高性能コンピューティング論２ 24 Recovery-Based • ストア・セットの計算の方法：recovery-based • 最初「依存していない」としておいて， • 順序違反 (memory-order violation) を検出して，追加 • 順序違反の検出： • 比較器数 ≒（ウィンドウ・サイズ）×（発行幅） • 「教訓」： • 厳密にやるより，いい加減にやったほうがうまくいく（こともある） ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「メモリ非曖昧化」より 高性能コンピューティング論２ 25 データ依存（load/store） 後続命令 Read Read Ip Ip Is Is time 先 行 命 令 Write time 入力依存 (input) 逆依存 (anti) Write Ip Ip Is Is time time フロー依存 (flow) 出力依存 (output) ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「スーパスカラ・プロセッサの基礎」より 高性能コンピューティング論２ 26 順序違反の検出 • プログラム・オーダで， • 後続の命令を先に実行した後で， • 先行する命令を実行した時に… • この 2命令が，フロー，逆，出力依存の関係にあれば順序違反 ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「メモリ非曖昧化」より 高性能コンピューティング論２ 27 順序違反検出 ― 比較器のアレイ + L/S V effective address 0 L １ 0x100 1: S, 0x100 + 0: L, 0x100 address calculators 後続 load 先行 load 1 S １ 0x100 store store Violation Violation Violation 2 3 L 1 0x100 4 5 6 後続 ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「メモリ非曖昧化」より 高性能コンピューティング論２ 28 発行可能検出 ― 比較器のマトリクス L/S V 0 effective address 0 1 2 3 4 先行命令 ready? ― ― 1 0 ― 0 = 0 ≠ 1 Valid Load 1 2 =? L/S Store 1 3 4 5 後続 ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「メモリ非曖昧化」より 高性能コンピューティング論２ 本日のまとめ 29 高性能コンピューティング論２ まとめ • メモリに関するデータ依存 • メモリ非曖昧化 30 高性能コンピューティング論２ 次回 • 12/17（木） 10:40～ • 10日は休講 • 「マルチスレッドプロセッサ」について解説 31
© Copyright 2024 ExpyDoc
