スライド 1

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