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

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

データ依存

データ依存 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

データ依存 入力依存 (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

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

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

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

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

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

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

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

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

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

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

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

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

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

比較器のマトリクス 先行命令 =? 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

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

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

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

構造と動作 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

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

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

今日のまとめ

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

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

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

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