09. メモリ・ディスアンビギュエーション 五島 正裕.

Presentation on theme: "09. メモリ・ディスアンビギュエーション 五島 正裕."— Presentation transcript:

1 09. メモリ・ディスアンビギュエーション 五島 正裕

2 内容 データ依存 メモリ・ディスアンビギュエーション ストア・セット・メモリ依存予測器

3 データ依存

4 データ依存 Write add r4 = r1 + r2 add r5 = r4 + r3 Read
制御駆動型 (control-driven) （⇔ データ駆動，data-driven） 命令間のデータの授受は， プログラム･オーダ上で，先行/後続の関係にある2命令が， 同一のロケーションを参照する ことで表現 ロケーション：レジスタ と メモリ Write add r4 = r1 + r2 add r5 = r4 + r3 Read

5 データ依存 入力依存 (input) 逆依存 (anti) フロー依存 (flow) 出力依存 (output) Ip Ip Is Is
後 続 命 令 Read Write 先行命令 入力依存 (input) 逆依存 (anti) フロー依存 (flow) 出力依存 (output) Ip Ip Is Is time time Ip Ip Is Is time time

6 ロード/ストア命令 op Rs Rt immediate ロード命令 r[Rt] = *(r[Rs] + immediate); ストア命令
*(r[Rs] + immediate) = r[Rt]; op Rs Rt immediate 31 25 20 15

7 レジスタとメモリ レジスタ番号 静的 デコード・ステージで分かる メモリのアドレス 動的
アドレス計算（実行）ステージで初めて分かる：「曖昧」

8 メモリの曖昧性による偽の依存 偽の依存： ストアのアドレスが決まるまで， 後続のロード/ストアは 原則 実行できない 「決まったら違ってた」

9 解決法 防止（予防，prevention）： ロード/ストアは in-order で
発見 ＆ 回復 (detection & recovery)： 依存なしと予測して out-of-order で メモリ・オーダ違反 (memory-order violation) を発見 0～7% のロードがメモリ・オーダ違反 ⇒ ペナルティ 理想 (ideal, oracle)： IPC 最大2倍

10 偽の依存の影響 IPC 2倍の理由：「計算のかたまりが重なる」 「計算のかたまりは，ロードではじまり，ストアで終わる」
「真のメモリ・データ依存がクリティカルになるようなコードは， 　最適化されてない」 目標： ロードを，特に早期に実行したい （ストアは，そんなでもない）

11 メモリ・ディスアンビギュエーション

12 メモリ・ディスアンビギュエーション ディスアンビギュエーション (disambiguation)： 「非曖昧化」，「曖昧性除去（解消）」
分離 (split) ロード/ストア アドレス予測 アドレス一致/不一致予測

13 ロード/ストア命令 op Rs Rt immediate 通常のロード/ストア命令： アドレス計算部 メモリ・アクセス部
ロード命令 ： r[Rt] = *(r[Rs] + immediate); ストア命令： *(r[Rs] + immediate) = r[Rt]; op Rs Rt immediate 31 25 20 15

14 分離ロード/ストア 通常のロード/ストア命令： アドレス計算部 メモリ・アクセス部 分離ロード/ストア：
ディスパッチ時に分離，以降 2つの命令としてスケジューリング 効果： ストア・バリューがなくても，アドレス計算が開始できる バリューより，アドレスが早く決まることが多い ロードは変わらない バリューに相当するソースがないから

15 ロード/ストア命令 普通のロード/ストア命令： 非分離 (non-split) を想定 理由：
パイプライン・マシンで，ALU でアドレス計算をすることを想定 コード効率の改善（命令の圧縮） 非 RISC 的？

16 IF 100 200 LD 1 2 10 100 5 ID EX 1000 210 MEM WB PC IR Rs Rt Reg File
Rs 200 LD 1 2 10 100 5 ID Rt Reg File EX 1000 210 MEM DR MDR MA MD Main Memory WB

17 アドレス予測 ロード/ストアのアドレスを予測 単純にロードを早期実行する効果 ストアのアドレスを予測 ⇒ ディスアンビギュエーションの効果
値予測の一種 だが，値予測より歴史が古い メモリ・アクセスがストライドであることは容易に想像できる

18 ハードウェア 今までの方法： 分離ロード/ストア アドレス予測 実際にアドレスの一致検出を行う
スケジューリングのために，比較器のマトリクス（行列）が必要！ 比較器数 ≒ ½ ×（ウィンドウ・サイズ）２ もう1つの方法： アドレス一致/不一致予測

19 比較器のマトリクス 先行命令 =? rdy L/S Valid Load ― 1 Store ＝ ≠ 1 2 old effective
1 2 old effective address L/S V 先行命令 =? rdy L/S Valid Load ― 1 Store ＝ ≠ 1 2 3 new

20 ストア・セット・メモリ依存予測器

21 ストア・セット あるロードのストア・セットとは： そのロードが依存したことがあるストアの集合 計算の方法：recovery-based
最初「依存していない」としておいて， オーダ違反 (memory-order violation) を検出して，追加 利用の方法： ロードは，そのストア・セット内のストアに依存すると予測

22 予測器の実装 原理的には： ストア・セット内のすべてのストアが実行された後でロードを実行 制限：
ストア・セット内のストアは in-order で実行 In-order チェイン： ストア → ストア → … → ストア → ロード

23 構造と動作 SSID X S1 S SSID X S2 S S1 S2 X L L SSID X SSID Table Last
Fetched Store Table SSID X S1 S SSID X S2 S S1 S2 X L L SSID X Instruction Window SSID : Store Set ID

24 Recovery-Based ストア・セットの計算の方法：recovery-based 最初「依存していない」としておいて，
オーダ違反 (memory-order violation) を検出して，追加 Violation の検出： 比較器数 ≒（ウィンドウ・サイズ）×（発行幅） 「教訓」： 厳密にやるより，いい加減にやったほうがうまくいく

25 比較器のアレイ 先行命令 =? rdy L/S Valid Load ― 1 Store ＝ ≠ old effective address
＝ ≠ 1 2 3 new

26 今日のまとめ

27 メモリ・データ依存 データ依存： レジスタ メモリ メモリのデータ依存： 動的 アドレス計算しないと分からない：「曖昧」

28 メモリ参照の曖昧性による偽の依存 ストアのアドレスが決まるまで，後続のロード/ストアは実行できない
保守的 (conservative) な方法： ロード/ストアは in-order で ロードは，特に早期に実行したい 「計算のかたまりは，ロードではじまり，ストアで終わる」 ストアは，そんなでもない 真のメモリ・データ依存がクリティカルであるようなプログラムは，最適化されてない？

29 ディスアンビギュエーション ディスアンビギュエーション（非曖昧化，曖昧性除去，解消） 分離ロード/ストア アドレス予測
アドレス一致/不一致予測 ストア・セット依存予測器

30 今後の予定 7/ 5 マルチスレッド・プロセッサ 7/12 ベクトル処理 ベクトル型計算機 SIMD 命令セット 7/19 7/26