Advanced Computer Architecture 09. メモリ・ディスアンビギュエーション 五島 正裕 Advanced Computer Architecture 内容 1. データ依存 2. メモリ・ディスアンビギュエーション 3. ストア・セット・メモリ依存予測器 Advanced Computer Architecture データ依存 Advanced Computer Architecture データ依存 制御駆動型 (control-driven) (⇔ データ駆動,data-driven) 命令間のデータの授受は, プログラム・オーダ上で,先行/後続の関係にある2命令が, 同一のロケーションを参照する ことで表現 ロケーション:レジスタ と メモリ Write add r4 = r1 + r2 add r5 = r4 + r3 Read Advanced Computer Architecture データ依存 後続命令 Read Read 先 行 命 令 Write Ip Ip Is Is time time 入力依存 (input) Write time 逆依存 (anti) Ip Ip Is Is フロー依存 (flow) time 出力依存 (output) Advanced Computer Architecture ロード/ストア命令 ロード命令 r[Rt] = *(r[Rs] + immediate); ストア命令 *(r[Rs] + immediate) = r[Rt]; op 31 Rs 25 Rt 20 immediate 15 0 Advanced Computer Architecture レジスタとメモリ レジスタ番号 静的 デコード・ステージで分かる メモリのアドレス 動的 アドレス計算(実行)ステージで初めて分かる:「曖昧」 Advanced Computer Architecture メモリの曖昧性による偽の依存 偽の依存: ストアのアドレスが決まるまで, 後続のロード/ストアは 原則 実行できない 「決まったら違ってた」 Advanced Computer Architecture 解決法 防止(予防,prevention): ロード/ストアは in-order で 発見 & 回復 (detection & recovery): 依存なしと予測して out-of-order で メモリ・オーダ違反 (memory-order violation) を発見 0~7% のロードがメモリ・オーダ違反 ⇒ ペナルティ 理想 (ideal, oracle): IPC 最大2倍 Advanced Computer Architecture 偽の依存の影響 IPC 2倍の理由:「計算のかたまりが重なる」 「計算のかたまりは,ロードではじまり,ストアで終わる」 「真のメモリ・データ依存がクリティカルになるようなコードは, 最適化されてない」 目標: ロードを,特に早期に実行したい (ストアは,そんなでもない) Advanced Computer Architecture メモリ・ディスアンビギュエーション Advanced Computer Architecture メモリ・ディスアンビギュエーション ディスアンビギュエーション (disambiguation): 「非曖昧化」,「曖昧性除去(解消)」 分離 (split) ロード/ストア アドレス予測 アドレス一致/不一致予測 Advanced Computer Architecture ロード/ストア命令 通常のロード/ストア命令: アドレス計算部 メモリ・アクセス部 ロード命令 : r[Rt] = *(r[Rs] + immediate); ストア命令: *(r[Rs] + immediate) = r[Rt]; op 31 Rs 25 Rt 20 immediate 15 0 Advanced Computer Architecture 分離ロード/ストア 通常のロード/ストア命令: アドレス計算部 メモリ・アクセス部 分離ロード/ストア: ディスパッチ時に分離,以降 2つの命令としてスケジューリング 効果: ストア・バリューがなくても,アドレス計算が開始できる バリューより,アドレスが早く決まることが多い ロードは変わらない バリューに相当するソースがないから Advanced Computer Architecture ロード/ストア命令 普通のロード/ストア命令: 非分離 (non-split) を想定 理由: パイプライン・マシンで,ALU でアドレス計算をすることを想定 コード効率の改善(命令の圧縮) 非 RISC 的? IF 100 PC ID IR 0 200 5 Reg File Rs LD 1 2 10 100 Rt EX MEM WB 1000 DR MDR MA MD Main Memory 210 Advanced Computer Architecture アドレス予測 ロード/ストアのアドレスを予測 単純にロードを早期実行する効果 ストアのアドレスを予測 ⇒ ディスアンビギュエーションの効果 値予測の一種 だが,値予測より歴史が古い メモリ・アクセスがストライドであることは容易に想像できる Advanced Computer Architecture ハードウェア 今までの方法: 分離ロード/ストア アドレス予測 実際にアドレスの一致検出を行う スケジューリングのために,比較器のマトリクス(行列)が必要! 比較器数 ≒ ½ ×(ウィンドウ・サイズ)2 もう1つの方法: アドレス一致/不一致予測 Advanced Computer Architecture 比較器のマトリクス old L/S V effective address 0 1 2 先行命令 rdy ― ― 1 0 ― 0 = 0 ≠ 1 L/S Valid 1 Load 2 Store 3 new =? 0 1 Advanced Computer Architecture ストア・セット・メモリ依存予測器 Advanced Computer Architecture ストア・セット あるロードのストア・セットとは: そのロードが依存したことがあるストアの集合 計算の方法:recovery-based 最初「依存していない」としておいて, オーダ違反 (memory-order violation) を検出して,追加 利用の方法: ロードは,そのストア・セット内のストアに依存すると予測 Advanced Computer Architecture 予測器の実装 原理的には: ストア・セット内のすべてのストアが実行された後でロードを実行 制限: ストア・セット内のストアは in-order で実行 In-order チェイン: ストア → ストア → … → ストア → ロード Advanced Computer Architecture 構造と動作 SSID Table S1 SSID X S S2 S L L SSID X Last Fetched Store Table S21 X SSID X Instruction Window SSID : Store Set ID Advanced Computer Architecture Recovery-Based ストア・セットの計算の方法:recovery-based 最初「依存していない」としておいて, オーダ違反 (memory-order violation) を検出して,追加 Violation の検出: 比較器数 ≒(ウィンドウ・サイズ)×(発行幅) 「教訓」: 厳密にやるより,いい加減にやったほうがうまくいく Advanced Computer Architecture 比較器のアレイ old L/S V effective address 先行命令 rdy ― ― 1 0 ― 0 = 0 ≠ 1 L/S Valid 1 Load 2 Store 3 new =? 0 1 Advanced Computer Architecture 今日のまとめ Advanced Computer Architecture メモリ・データ依存 データ依存: レジスタ メモリ メモリのデータ依存: 動的 アドレス計算しないと分からない:「曖昧」 Advanced Computer Architecture メモリ参照の曖昧性による偽の依存 ストアのアドレスが決まるまで,後続のロード/ストアは実行できない 保守的 (conservative) な方法: ロード/ストアは in-order で ロードは,特に早期に実行したい 「計算のかたまりは,ロードではじまり,ストアで終わる」 ストアは,そんなでもない 真のメモリ・データ依存がクリティカルであるようなプログラムは, 最適化されてない? Advanced Computer Architecture ディスアンビギュエーション ディスアンビギュエーション(非曖昧化,曖昧性除去,解消) 分離ロード/ストア アドレス予測 アドレス一致/不一致予測 ストア・セット依存予測器 Advanced Computer Architecture 今後の予定 7/ 5 マルチスレッド・プロセッサ ベクトル処理 7/12 ベクトル型計算機 SIMD 命令セット 7/19 7/26
© Copyright 2024 ExpyDoc