分岐予測と TC

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

Download Report