6. パイプライン制御

(1)

(2)

パイプライン（パイプライン（パイプライン（ パイプライン（Pipelining）））） • 命令のスループットをあげて性能を向上する Instruction fetch R eg ALU Data access R eg

8 ns Instruction_fetch R eg ALU Data

access R eg 8 ns Instruction_fetch 8 ns Tim e lw $1, 100($0) lw $2, 200($0) lw $3, 300($0) 2 4 6 8 10 12 14 16 18 2 4 6 8 10 12 14 ... P rogram execution order (in instructions) Instruction

fetch Reg ALU

Data access Reg Time lw $1, 100($0) lw $2, 200($0) lw $3, 300($0)

2 ns Instruction_fetch Reg ALU Data

access Reg

2 ns Instruction_fetch Reg ALU Data

access Reg 2 ns 2 ns 2 ns 2 ns 2 ns P rogram execution order (in instructions)

(3)

パイプライン（パイプライン（パイプライン（ パイプライン（Pipelining）））） • 望ましい性質 – 命令長が等しい – 命令形式が少ない – ロード・ストアアーキテクチャ • 基本的課題（ハザードへの対応） – 構造ハザード: メモリの競合 – コントロールハザード: 分岐命令の処理 – データハザード: 先行する命令へ依存する場合 • 高度な課題 – 例外処理 – 順不同実行の制御（out-of-order execution)など

(4)

パイプラインの基本構造パイプラインの基本構造パイプラインの基本構造パイプラインの基本構造 • 命令フェッチ（ＩＦ） • デコードとレジスタアクセス（Ｄ） • 実行（ＥＸ）：ALU,アドレス計算、条件判断 • メモリ参照（MEM) • 結果の格納（ＷＢ） • 各実行段階を流れ作業で並列処理

(5)

理想的なパイプライン動作理想的なパイプライン動作理想的なパイプライン動作理想的なパイプライン動作 IF D EX MEM WB IF D EX MEM WB IF D EX MEM IF D EX 1 clock cycle t

(6)

データパスのパイプライン化データパスのパイプライン化データパスのパイプライン化データパスのパイプライン化 Instruction memory Address 4 32 0 Add Add result Shift left 2 Ins tr u cti o n

IF/ID EX/MEM MEM/WB M u x 0 1 Add PC 0 Address Write data M u x 1 Registers Read data 1 Read data 2 Read register 1 Read register 2 16 Sign extend Write register Write data Read data Data memory 1 ALU result M u x ALU Zero ID/EX

(7)

パイプラインの模式図パイプラインの模式図パイプラインの模式図パイプラインの模式図 IM Reg DM Reg IM Reg DM Reg CC 1 CC 2 CC 3 CC 4 CC 5 CC 6 Time (in clock cycles)

lw $10, 20($1) Program execution order (in instructions) sub $11, $2, $3 ALU ALU

(8)

パイプライン制御パイプライン制御パイプライン制御パイプライン制御 PC Instruction memory Address In s tr u c ti o n Instruction [20– 16] MemtoReg ALUOp Branch RegDst ALUSrc 4 16 32 Instruction [15– 0] 0 0 Registers Write register Write data Read data 1 Read data 2 Read register 1 Read register 2 Sign extend M u x 1 Write data Read data M u x 1 ALU control RegWrite MemRead Instruction [15– 11] 6

IF/ID ID/EX EX/MEM MEM/WB

MemWrite Address Data memory PCSrc Zero Add _resultAdd

Shift left 2 ALU result ALU Zero Add 0 1 M u x 0 1 M u x

(9)

• 制御信号をデータのように伝達するパイプライン制御パイプライン制御パイプライン制御パイプライン制御 Execution/Address Calculation stage control lines

Memory access stage control lines stage control lines Instruction Reg Dst ALU Op1 ALU Op0 ALU Src Branch Mem Read Mem Write Reg write Mem to Reg R-format 1 1 0 0 0 0 0 1 0 lw ₀ ₀ ₀ ₁ ₀ ₁ ₀ ₁ ₁ sw _X ₀ ₀ ₁ ₀ ₀ ₁ ₀ _X beq _X ₀ ₁ ₀ ₁ ₀ ₀ ₀ _X C o n tr o l E X M W B M W B W B I F /I D ID /E X E X /M E M M E M / W B I n s t r u c tio n

(10)

制御線とデータパス制御線とデータパス制御線とデータパス制御線とデータパス PC Instruction mem ory In stru cti o n Add Instruction [20– 16] M e m toReg ALUOp Branch RegDst ALUSrc 4 16 32 Instruction [15– 0] 0 0 M u x 0 1

Add_resultAdd

Registers W rite register W rite data Read data 1 Read data 2 Read register 1 Read register 2 Sign extend M u x 1 ALU result Zero Write data Read data M u x 1 ALU control Shift left 2 Reg W ri te M emRead Control ALU Instruction [15– 11] 6 EX M W B M WB WB IF/ID PCSrc ID/EX EX/MEM MEM/WB M u x 0 1 Me m W ri te Address Data memory Address

(11)

パイプラインの乱れパイプラインの乱れパイプラインの乱れ パイプラインの乱れ（ハザード）（ハザード）（ハザード）（ハザード） • 例 sub $2, $1, $3 and $12, $2, $5 or $13, $6, $2 add $14, $2, $2 sw $15, 100 ( $2 ) ...

(12)

データハザードデータハザードデータハザードデータハザード IM Reg IM Reg CC 1 CC 2 CC 3 CC 4 CC 5 CC 6

Time (in clock cycles)

sub $2, $1, $3 Program execution order (in instructions) and $12, $2, $5 IM _Reg DM Reg IM DM Reg IM DM Reg CC 7 CC 8 CC 9 10 10 10 10 10/– 20 – 20 – 20 – 20 – 20 or $13, $6, $2 add $14, $2, $2 sw $15, 100($2) Value of register $2: DM Reg Reg Reg Reg DM

(13)

ハザードの分類ハザードの分類ハザードの分類ハザードの分類 • データハザード – 先行する命令の結果を使用する場合 • コントロールハザード – 分岐命令によるパイプの乱れ • 構造ハザード – 資源の競合（メモリの競合など）

(14)

ストール（ストール（ストール（ ストール（Stalling）））） • 命令を同じステージに止める（ストール、バブル) lw $2, 20($1) Program execution order (in instructions) and $4, $2, $5 or $8, $2, $6 add $9, $4, $2 slt $1, $6, $7 Reg IM Reg Reg IM DM CC 1 CC 2 CC 3 CC 4 CC 5 CC 6

Time (in clock cycles)

IM Reg DM Reg IM IM DM Reg IM DM Reg CC 7 CC 8 CC 9 CC 10 DM Reg Reg Reg Reg bubble

(15)

• 中間結果を書き込み前に使う

– register file forwarding (同一レジスタへのリード・ライト） – ALU forwarding

フォワード（フォワード（フォワード（

フォワード（Forwarding））））

what if this $2 was $13?

IM R e g IM R e g C C 1 C C 2 C C 3 C C 4 C C 5 C C 6 T im e (in c lo c k c y c le s ) s u b $ 2, $ 1 , $ 3 P r o g ra m e x e c u tio n o rd e r (in in s tru c tio n s )

a n d $ 1 2 , $ 2, $ 5 IM R e g D M R e g I M D M R e g I M D M R e g C C 7 C C 8 C C 9 1 0 1 0 1 0 1 0 1 0 / – 2 0 – 2 0 – 2 0 – 2 0 – 2 0 o r $ 1 3 , $ 6 , $ 2 a d d $ 1 4 , $ 2, $ 2 s w $ 1 5 , 1 0 0($ 2 ) V a lu e o f re g is t e r $ 2 : D M R e g R e g R e g R e g X X X – 2 0 X X X X X V a lu e o f E X /M E M : X X X X – 2 0 X X X X V a lu e o f M E M /W B : D M

(16)

ハザード対策ハザード対策ハザード対策ハザード対策 • データハザード対策 – バイパス（forwarding） – 命令の並べ替え・遅延用命令(NOP) • コントロールハザード対策 – 分岐予測制御 – 遅延分岐 • 構造ハザード対策 – 命令とデータキャッシュの分離 – マルチアクセスレジスタ、メモリ

(17)

コントロール・ハザード対策（１）コントロール・ハザード対策（１）コントロール・ハザード対策（１）コントロール・ハザード対策（１） • 分岐を予測する – 分岐しない／する方に賭ける – 正方向の分岐は分岐しないとする負方向のみ分岐としておく – 過去の履歴を記録して判断（分岐テーブル） – 両方向とも仮に実行し、不要なほうを捨てる（ハードウェアが十分ある場合）

(18)

コントロール・ハザード対策（２）コントロール・ハザード対策（２）コントロール・ハザード対策（２）コントロール・ハザード対策（２） • 遅延分岐 – 分岐命令の動作定義を変える分岐は、分岐命令実行直後ではなく次の命令実行後に起こる（と変更する） – 命令の並べ替えを行い,分岐命令のあとに実行できる命令を分岐命令後に置く – 並べ替えができないときは,NOP 命令挿入

(19)

構造ハザード対策構造ハザード対策構造ハザード対策構造ハザード対策 • 資源の競合が起こらないように、資源を追加 – メモリからの命令読み出しとデータアクセスの競合 →命令メモリとデータメモリを分ける（Harvard Architecture) – レジスタ・ファイルの競合 →マルチアクセスレジスタファイル – データ・バスの競合 →バスの幅を広げるあるいはバイパスを作る