メモリ非曖昧化

Advanced
Computer
Architecture
08. メモリ非曖昧化
五島正裕
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
データ依存
後続命令 Is
Read
Read
先
行
命
令
Write
Ip
Ip
Is
Is
time
time
入力依存 (input)
Ip
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
コード例
f (double* a, double* b,
double* x, double* y)
{
*x = *a * *a;
*y = *b * *b;
}
x == b ?
ld
ld
ld
mul
st
r1 = *(sp + 0)
r1 = *r1
r2 = *(sp + 16)
r1 = r1 * r1
*r2 = r1
// a
ld
ld
ld
mul
st
r3 = *(sp + 8)
r3 = *r3
r4 = *(sp + 24)
r3 = r3 * r3
*r4 = r3
// b
ret
// x
// y
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
オーバラップ実行
ILP
(Inst Level Parallelism)
ld
ILP
ld
ld
st
st
ld
st
st
Advanced
Computer
Architecture
メモリ非曖昧化 (memory disambiguation)
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
ロード/ストア命令
 普通の 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
Advanced Computer Architecture
アドレス予測
 ロード/ストアのアドレスを予測
 単純にロードを早期実行する効果
 非曖昧化の効果
 値予測の一種
 だが，値予測より歴史が古い
 メモリ・アクセスがストライドであることは容易に想像できる
Advanced Computer Architecture
ハードウェア
 今までの方法：
 分離ロード/ストア
 アドレス予測
 実際にアドレスの一致検出を行う
 スケジューリングのために，比較器のマトリクス（行列）が必要！
 比較器数 ≒ ½ ×（ウィンドウ・サイズ）２
 もう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
PC of Fetched Instructions
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
ディスアンビギュエーション
 ディスアンビギュエーション（非曖昧化，曖昧性除去，解消）
 分離ロード/ストア
 アドレス予測
 アドレス一致/不一致予測
 ストア・セット依存予測器

Download Report