アドバンスト コンピュータ アーキテクチャ RISC と 命令パイプライン * 07/16/96 アドバンスト コンピュータ アーキテクチャ RISC と 命令パイプライン 五島 2018/11/30 *

講義の内容 RISC 命令セット 非パイプライン実装 命令パイプライン

RISC とは CISC： Complex Instruction Set Computer 複合 (?) 命令セット計算機 アーキテクチャの進化 ＝ 高機能な命令の追加 RISC： Reduced Instruction Set Computer 縮小命令セット計算機 複雑な機能は，基本的な命令の組み合わせで コンパイラ アーキテクチャの進化 ＝ システムの高効率化

RISC の位置づけ Reduced: ごく基本的な命令のみ とにかく HW が簡単/高効率になるように 最近のほとんどすべてのプロセッサの基礎 RISC スーパースカラ VLIW x86 スーパースカラ（RISC ではない！） Java プロセッサ/アクセラレータ （RISC ではない！） etc. RISC 以前のことは，忘れてもよい (?) 少なくとも，RISC を下敷きに議論し直したほうがよい．

RISC アーキテクチャ Reduced: ごく基本的な命令のみ とにかく HW が簡単/高効率になるように i860, M88000, PA-RISC SPARC, MIPS, POWER/PowerPC どれも，似たりよったり

RISC の特徴 Reduced: ごく基本的な命令のみ とにかく HW が簡単/高効率になるように 固定長命令 32b 大容量の汎用レジスタ・ファイル 汎用レジスタ (General Purpose Reg: GPR) x32 #0 レジスタは「0 レジスタ」 ロード/ストア・アーキテクチャ 演算は，レジスタに対してのみ

ロード/ストア・アーキテクチャ 演算器 演算器 演算 RF RF ロード ストア 主記憶 主記憶 非 ロード/ストア ― ロード/ストア ―

講義の内容 RISC 命令セット 非パイプライン実装 命令パイプライン

命令の種類 数え方にもよるが，数十種くらい． ロード/ストア 演算命令 算術論理演算 (ＡＬＵ: Arithmetic Logic Unit) シフト 浮動小数点演算 制御命令 分岐 (branch) 命令 ：PC 相対 ジャンプ命令 ：絶対 その他 システム・コール コプロセッサ制御

命令フォーマット op Rs Rt Rd func op Rs Rt immediate op jump_target op : 31 25 20 15 10 op Rs Rt immediate 31 25 20 15 op jump_target 31 25 op : op code Rs : source reg # Rt : target reg # Rd : destination reg #

演算命令 op Rs Rt Rd shamt func op Rs Rt immediate 算術論理演算 (ＡＬＵ, Arithmetic Logic Unit) 命令 r[Rd] = r[Rs] + r[Rt], … r[Rt] = r[Rs] + immediate, … シフト命令 r[Rd] = r[Rs] << shamt, … op Rs Rt Rd shamt func 31 25 20 15 10 op Rs Rt immediate 31 25 20 15

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

制御命令 （分岐命令） op Rs Rt immediate （条件）分岐命令 if (cond) PC = PC + immediate; branch on register cond: R[Rs] == 0, R[Rs] > 0, … compare and branch cond: R[Rs] == R[Rt], R[Rs] != R[Rt] op Rs Rt immediate 31 25 20 15

制御命令 （ジャンプ命令） op Rs Rt immediate op jump_target ジャンプ命令 （絶対） PC = jump_target; ジャンプ命令（レジスタ間接） PC = r[Rs]; op Rs Rt immediate 31 25 20 15 op jump_target 31 25

講義の内容 RISC 命令セット 非パイプライン実装 命令パイプライン

命令の実行フェーズ IF 命令フェッチ ID 命令デコード/レジスタ読み出し EX 実行 MEM メモリ・アクセス WB レジスタ書き戻し (Write-Back) 名称は歴史的（esp. ID）

IF 100 200 100 8 1 2 ID 104 1 2 3 EX 208 1000 MEM WB PC IR Rs Rt Reg Rs 200 100 8 ld 1 2 ID Rt 104 1 add 2 3 Reg File EX 208 1000 MEM DR MDR MA MD Main Memory WB

実行例 100 ld r2 = *(r1 + 8) 104 add r3 = r2 + 1

IF 100 104 PC IR 8 ld 1 2 Rs 200 100 8 ld 1 2 ID Rt 104 1 add 2 3 Reg File EX 208 1000 MEM DR MDR MA MD Main Memory WB

IF 104 PC IR 8 ld 1 2 Rs 200 100 8 ld 1 2 ID Rt 104 1 add 2 3 Reg File 200 8 EX 208 1000 MEM DR MDR MA MD Main Memory WB

IF 104 PC IR 8 ld 1 2 Rs 200 100 8 ld 1 2 ID Rt 104 1 add 2 3 Reg File 200 8 EX 208 1000 208 MEM DR MDR MA MD Main Memory WB

IF 104 PC IR 8 ld 1 2 Rs 200 100 8 ld 1 2 ID Rt 104 1 add 2 3 Reg File 200 8 EX 208 1000 208 MEM DR MDR MA MD 1000 Main Memory WB

IF 104 PC IR 8 ld 1 2 Rs 200 100 8 ld 1 2 1000 ID Rt 104 1 add 2 3 Reg File 200 8 EX 208 1000 208 MEM DR MDR MA MD 1000 Main Memory WB

IF 104 108 PC IR 1 add 2 3 Rs 200 100 8 ld 1 2 1000 ID Rt 104 1 add 2 3 Reg File EX 208 1000 MEM DR MDR MA MD Main Memory WB

IF 108 PC IR 1 add 2 3 Rs 200 100 8 ld 1 2 1000 ID Rt 104 1 add 2 3 Reg File 1000 1 EX 208 1000 MEM DR MDR MA MD Main Memory WB

IF 108 PC IR 1 add 2 3 Rs 200 100 8 ld 1 2 1000 ID Rt 104 1 add 2 3 Reg File 1000 1 EX 208 1000 1001 MEM DR MDR MA MD Main Memory WB

IF 108 PC IR 1 add 2 3 Rs 200 100 8 ld 1 2 1000 ID Rt 104 1 add 2 3 Reg File 1000 1 EX 208 1000 1001 MEM DR MDR MA MD 1001 Main Memory WB

IF 108 PC IR 1 add 2 3 Rs 200 100 8 ld 1 2 1000 ID Rt 104 1 add 2 3 Reg File 1001 1000 1 EX 208 1000 1001 MEM DR MDR MA MD 1001 Main Memory WB

講義の内容 RISC 命令セット 非パイプライン実装 命令パイプライン

非命令パイプライン IF ID EX MEM WB I5 I1 I0 IF ID EX MEM WB

命令パイプライン I0 I1 I2 I3 I4 I5 IF ID EX MEM WB パイプライン・ステージ

命令パイプラインの表現 I0 I1 I2 I3 I4 I5 IF ID EX MEM WB cycle I0 I1 I2 I3 I4 I5

パイプライン化 パイプライン化 (pipelining) の効果 レイテンシ (latency) 1命令の処理時間 変わらない（か，やや延びる） スループット (throughput) 単位時間当たりの処理量 （ステージ数）倍になる 使い勝手がよい技 「手」が余っているときには，やってみるとよい．

CPI cycle CPI = 5 cycle CPI = 1 CPI : Cycles Per Instruction スループット 命令パイプラインの効率を計る指標 （性能） ＝ （クロック速度）÷ （CPI） cycle I0 IF ID EX MEM WB CPI = 5 I1 IF ID EX MEM WB I2 IF ID EX MEM WB cycle I0 IF ID EX MEM WB I1 IF ID EX MEM WB CPI = 1 I2 IF ID EX MEM WB

パイプライン・ハザード パイプライン・ハザード (hazard) パイプライン動作を妨げる要因 構造ハザード (structural hazard) HW の資源の不足が原因 非構造ハザード SW の持つ依存関係が原因 データ・ハザード (data hazard) データ依存 制御ハザード (control hazard) 制御依存，分岐命令の実行

構造ハザードの例 cycle LD I1 I2 I3 I4 メモリのポートの不足 IF ID EX MEM WB IF ID EX MEM

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

構造ハザードの例 cycle LD I1 I2 I3 I4 メモリのポートの不足 IF ID EX MEM WB IF ID EX MEM

ちなみに… cycle LD ADD I2 ステージ間で，使用する資源が異なる IF ID EX MEM WB IF ID EX MEM

データ・ハザード cycle add r4 = r1 + r2 add r5 = r4 + r3 命令間のデータ依存 IF ID EX MEM WB add r4 = r1 + r2 IF ID EX MEM WB IF ID add r5 = r4 + r3

制御ハザード 分岐命令の実行 cycle IF ID EX MEM WB BE IF IF ID EX MEM WB I1

インターロック と バブル パイプライン・ハザード (hazard) パイプライン動作を妨げる要因 パイプライン・インターロック (interlock) によって対処 パイプライン・バブル (bubble) が発生 「パイプラインが乱れる」

ロード命令 と バブル I3 I4 I5 LD I1 I2 IF ID EX MEM WB

ロード/ストア命令 と バブル I3 I4 I5 LD I1 I2 IF ID EX MEM WB インターロック

バブルの表現 cycle LD I1 I2 I3 I4 IF ID EX MEM WB IF ID EX MEM WB IF ID EX

アーキテクチャ的対処 インターロックする ⇒ バブルが発生 ⇒ 性能低下 インターロックする機会を減らすことが重要！ 構造ハザード 資源の不足が原因 資源の追加で消える 例えば，メモリ・ポートの場合， 命令キャッシュとデータ・キャッシュの分離 (separate) 非構造ハザード プログラムが原因 原理的に消えない バブルの削減

バブルの削減 （データ・ハザード） cycle add r4 = r1 + r2 add r5 = r4 + r3 add IF ID EX MEM WB add r5 = r4 + r3 IF ID EX MEM WB add r4 = r1 + r2 IF OR EX MEM WB add r5 = r4 + r3 IF OR EX MEM WB add r4 = r1 + r2 IF OR EX MEM WB add r5 = r4 + r3 IF OR EX MEM WB バイパス

バイパス 同じもの： オペランド・バイパス レジスタ・バイパス 結果 (result) バイパス （データ）フォワーディング (forwarding)

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

バブルの削減（制御ハザード） cycle I0 be I1 I0 be I1 next PC 計算器 IF ID EX MEM WB IF nPC EX MEM WB I1 IF OR EX MEM WB next PC 計算器

インターロックの排除（制御ハザード） cycle I0 be I1 I0 be I1 be I0 遅延分岐 I1 IF ID EX MEM WB be IF ID EX MEM WB I1 IF ID EX MEM WB I0 IF ID EX MEM WB be IF nPC EX MEM WB I1 IF OR EX MEM WB be IF nPC EX MEM WB I0 IF OR EX MEM WB 遅延分岐 I1 IF OR EX MEM WB

遅延分岐 遅延分岐 (delayed branch) 分岐命令の実行が（1サイクル）遅延される（遅れる） 遅延スロット (delay slot) 分岐命令の次の命令（を置く場所） 「遅延スロットに置かれた命令は（分岐の成立/不成立にかかわらず）必ず実行される」 遅延スロットに入れる命令 本来の分岐の上流にあたる部分から探す 見つからなければ，nop を入れる

インターロックの排除（データ・ハザード） cycle I0 IF ID EX MEM WB ld IF ID EX MEM WB I1 IF ID EX MEM WB I0 IF OR EX MEM WB ld IF OR EX MEM WB バイパス I1 IF OR EX MEM WB ld IF OR EX MEM WB I0 IF OR EX MEM WB 遅延ロード I1 IF OR EX MEM WB

遅延ロード 遅延ロード (delayed load) ロード命令の実行が（1サイクル）遅延される（遅れる） 遅延スロット (delay slot) ロード命令の次の命令（を置く場所） 「遅延スロットに置かれた命令は，ロード命令の結果を使うことができない」 遅延スロットに入れる命令 まわりから探す 見つからなければ，nop を入れる

遅延分岐，遅延ロード プログラムに対して制約を課す HW を簡単化するため インターロック機構の排除 性能のため 遅延スロットを埋めることができれば，性能は向上する （コンパイラなら）多くの場合 埋められる MIPS (Tech. inc./Architecture) Microprocessor w/o Interlocked Pipeline Stages パイプライン・マシンのため スーパースカラ化すると負の遺産に…

バック・エッジ もろもろの元凶は，パイプラインのバック・エッジ バック・エッジ 逆向きの信号の流れ

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

バック・エッジ長 と バブルの量 cycle BE I1 IF ID EX MEM WB IF ID EX MEM WB IF ID EX

まとめ RISC 現在のアーキテクチャの基礎 命令パイプライン パイプライン・ハザード 構造ハザード： HW の追加で消せる 非構造ハザード： 原理的に消えない 非構造ハザード バック・エッジが元凶

今後の予定 次回 休み 次々回 スーパースカラ・プロセッサ Out-of-Order 実行 それ以降 投機：バック・エッジを消す？！