演習問題解答案(第4章プロセッサ) パタヘネ: コンピュータの構成と設計 5th

Patterson & Hennessy: コンピュータの構成と設計 第5版の演習問題を解いています．
本記事は4章プロセッサの解答をまとめたものです．
間違いが多々あると思いますが，コメントいただけると嬉しいです．

2018/07/08: “第5章容量と速度の両立：記憶階層の利用”の記事はこちらです(作成中)。

4.1 Building a Datapath

4.1.1

• RegWire: assert
• MemRead: deassert
• ALUsrc: deassert(ALUの第二入力はレジスタから取る)
• MemWrite: deassert
• MemtoReg:deassert
• ALU制御入力: 4'b0000(AND)(p.251を参考にした)
• Branch: deassert

4.1.2

命令メモリ, レジスタ, ALU, PC更新用加算器, 制御ブロック

4.1.3

Branch用加算器, データメモリ

4.2 Building a Datapath

4.2.1

命令メモリ, レジスタ, ALU, PC更新用加算器, データメモリ, 制御ブロック
(Branch用加算器以外全てのブロック)

4.2.2

無し

4.2.3

無し
図4.18に従うと下記のように制御信号を設定すれば良い.

命令名	RegDst	ALUSrc	MemtoReg	RegWrite	MemRead	MemWrite	Branch	ALUOp1	ALUOp0
lwi	1	0	1	1	1	0	0	0	0

4.3 Building a Datapath

4.3.1

乗算器追加前と後でcritical pathは変化しない.

• old: 1100[ps]
• new: 1400[ps]

4.3.2

乗算器追加前の命令数をKとする．
図4.2の構成では，どの命令に対してもCPIは1である．

• old: Execution Time = 1100K[ps]
• new: Execution Time = 1330K[ps]

よって，0.827倍となり, 速度は向上しない.

4.3.3

• old: Perf./cost = 1/1110K/3840
• new: Perf./cost = 1/1330K/4440

よって, 0.715倍となり, この改善でコスト性能比は向上しない.

4.4 Building a Datapath

4.4.1

200[ps]

4.4.2

315[ps]

4.4.3

420[ps]

4.4.4

beq, j (,bne, jal, bclt, bclf)

4.4.5

j (, jal)

4.4.6

「2ビット左にシフト」のレイテンシをtshtとする．

max(305 + tsht, 420)

4.5 Building a Datapath

4.5.1

35%

4.5.2

80%

すべてのサイクルで符号拡張を行い，ID/EX registerに渡す．(p.280-282の記述より)

※Immを必要としない命令のID/EX.Imm registerのスイッチングを抑えるために，
IDしながらImmが必要か否かを判定する論理を組んで，ID/EX.Imm registerのenable信号をdeassertしても良い気がする．
ID stageのDelayが多少悪化することが良くないのかもしれない．

※一方で，SignExtとZeroExtがあるので，ID stageでSignExtかZeroExtかの判定を行っているはず．
それなら，上述の"ID/EX.Imm registerのenable信号をdeassert"する論理ぐらい入れても良い気がする．

4.6 Instruction pipelining

問題の設定をよく読み取れなかったため，下記を想定して解答を作成します．

• テスト前にPC, RegFile, メモリを所望の値で初期化できる
• 初期化後，所望の命令を1命令だけ実行させることができる
• 命令を実行後，PC, RegFile, メモリをスキャンできる
• PC,RegFile,メモリの初期値・期待値及び，実行する命令のセットを指してテストと呼ぶ

4.6.1

設計できる

• 0膠着エラーの場合

  • 初期値:\$t0 = 1
  • 命令: add \$t1, \$t0, \$zero
  • 期待値：\$t1 = 1 (\$t1=0なら0膠着エラー)

• 1膠着エラーの場合

  • 初期値:無し
  • 命令: add \$t1, \$zero, \$zero
  • 期待値：\$t1 = 0 (\$t1=1なら1膠着エラー)

4.6.2

設計できない

下記２つを同時に満たすテストは作成できないから

• 書き込みレジスタに指定したレジスタのビット0に対して，期待値：1であるテスト
• 書き込みレジスタに指定したレジスタのビット0に対して，期待値：0であるテスト

4.6.4

図4.22より, RegDest=0かつMemRead=1となる命令はlwであるので，

• 初期値:Memory 0x0000_0000 = deedbeef
• 命令: lw \$t0,0($zero)
• 期待値：\$t0 = deedbeef (それ以外ならMemRead0膠着エラー)

4.6.5

設計できない

もし，j命令実行時にRegDest = 1(本来はX)とする構成なら，設計できる

• 初期値:無し
• 命令: j 1
• 期待値：PC = PC + 8 (PC+4ならJump0膠着エラー)

4.7 Instruction pipelining

問題文に示された命令は，

• sw r2, 20(r3) -> sw \$v0, 20(\$v1) である．
  ※設問の内容からbeqが期待のような気がする・・・

4.7.1

28'b1880050

4.7.2

ALUop = 2'b00

4.7.3

PC + 4

4.7.4

• brnch用のMUX: PC + 4 (制御信号Branch & ゼロ判定 = 1'b0より)
• j用のMUX: PC + 4 (制御信号Jump = 1'b0より)
• ALU用のMUX: 32'h0000_0014 (制御信号ALUSrc = 1'b1より)

• MemtoRegのMUX: 32'hX (制御信号MemtoReg = 1'bXより)

• レジスタ： sw命令なのでレジスタファイルに変化はない

4.7.5

• ALU: r2(= 2), Imm = 32'h0000_0014
• PC用加算器: PC, 4
• Branch用加算器: PC + 4, Imm = 32'h0000_0014

4.7.6

• 読み出しレジスタ１： 5'h00011 (r3)
• 読み出しレジスタ2： 5'h00010 (r2)
• 書き込みレジスタ: 5'hX
• 書き込みデータ: 32'hX

なお，出力は

• 読み出しデータ1: -3
• 読み出しデータ2: 2

4.8 Instruction pipelining

4.8.1

• パイプライン方式: 350[ps]
• パイプライン方式ではない： 1,250[ps]
  ※実際には，パイプライン化で追加したStage間のregisterのレイテンシを加算しないと公平でない

4.8.2

• パイプライン方式: 1,250[ps] -> 1,750[ps]
• パイプライン方式ではない： 1,250[ps]

4.8.3

• 分割するstage: ID stage
• clock cycle: 300ps

4.8.4

35%

4.8.5

65%

4.8.6

命令数をKとする．

• 単一クロックサイクル型：
  • クロックサイクル時間： 1,250[ps]
  • 実行時間:1,250K[ps]
• マルチサイクル型：
  • クロックサイクル時間：
  • ALU: 950[ps]
  • beq: 750[ps]
  • lw: 1,250[ps]
  • sw: 1,050[ps]
  • 実行時間: 985K[ps]
• パイプライン型：
  • クロックサイクル時間： 350[ps]
  • 実行時間: 350K[ps]

よって，マルチサイクル型は単一クロックサイクル型と比較して，1,27倍の高速化となる．
また，パイプライン型は単一クロックサイクル型と比較して，4.34倍の高速化となる．

4.9 Data hazards

[inst. 1] or r1, r2, r3
[inst. 2] or r2, r1, r4
[inst. 3] or r1, r1, r2

4.9.1

• [inst. 1]の\$rd = r1 と[inst. 2]の\$rs = r1がデータ依存
• [inst. 1]の\$rd = r1 と[inst. 3]の\$rs = r1がデータ依存
• [inst. 2]の\$rd = r2 と[inst. 3]の\$rt = r2がデータ依存

4.9.2

• [inst. 1]と[inst. 2]のデータ依存により， EX/MEM.RegisterRd = ID/EX.RegisterRsの条件を満たすデータ・ハザードが発生している．
• [inst. 1]と[inst. 3]のデータ依存により， MEM/WB.RegisterRd = ID/EX.RegisterRsの条件を満たすデータ・ハザードが発生している．
• [inst. 2]と[inst. 3]のデータ依存により， EX/MEM.RegisterRd = ID/EX.RegisterRtの条件を満たすデータ・ハザードが発生している．

[inst. 1] or r1, r2, r3
[nop 1] nop
[nop 2] nop
[inst. 2] or r2, r1, r4
[nop 3] nop
[nop 4] nop
[inst. 3] or r1, r1, r2

4.9.3

[inst. 1] or r1, r2, r3
[inst. 2] or r2, r1, r4
[inst. 3] or r1, r1, r2

4.9.4

• フォワーディング無し：Execution Time = 2,750[ps]
• 全面的にフォワーディングあり: Execution Time = 2,100[ps]

よって，全面的にフォワーディングありは，フォワーディング無しと比較して，1.31倍の高速化となる．

4.9.5

[inst. 1] or r1, r2, r3
[inst. 2] or r2, r1, r4
[nop 1] nop
[inst. 3] or r1, r1, r2

4.9.6

• ALU同士の間のフォワーディングのみあり: Execution Time = 2,320[ps]

よって，ALU同士の間のフォワーディングのみありは，フォワーディング無しと比較して，1.19倍の高速化となる．

4.10 Branching hazards

4.10.1

Execution Time = 2,200[ps]

※問題文中の”構造ハザード”が，IF stageにおけるメモリアクセスとMEM stageにおけるメモリアクセスの構造ハザードだけを指しているとします．

下記のようにnopを追加すると，メモリアクセスのタイミングがずれて，競合が発生しなくなるから．
[inst. 1] sw r16, 12(r6)
[inst. 2] lw r16, 8(r6)
[inst. 3] beq r5, r4, Label
[nop 1] nop
[nop 2] nop
[inst. 4] add r5, r1, r4
[inst. 5] slt r5, r15, r4

4.10.2

※メモリはInst. Mem, Data Memが別個に用意されており，4.10.1のような構造ハザードは考えなくて良いとして解答を作成します．

[inst. a] addi r2, r6, 12
[inst. b] addi r3, r6, 8
[inst. 1] sw r16, r2
[inst. 2] lw r16, r3
[inst. 3] beq r5, r4, Label
[inst. 4] add r5, r1, r4
[inst. 5] slt r5, r15, r4

• 5 stage pipeline: Execution Time = 1,800[ps]
• 4 stage pipeline: Execution Time = 2,000[ps]

よって，0.9倍となり，この変更では高速化されない．

4.10.3

[inst. 3] beq命令のオペランドに，データ依存関係は存在しない．よって，[inst. 3]beq直後に
追加されるストールのみ考慮すれば良い．

• EX stageで判定： Execution Time = 2,200[ps]
• ID stageで判定： Execution Time = 2,000[ps]

よって，1.1倍の高速化となる．

4.10.4

• 5 stage pipeline: Execution Time = 1,800[ps]
• 4 stage pipeline: Execution Time = 2,100[ps]

よって，0.86倍となり，この変更では高速化されない．

4.10.5

結果的に，クロックサイクル時間は変化しない．
* EX stageで判定： Execution Time = 2,200[ps]
* ID stageで判定： Execution Time = 2,000[ps]

よって，1.1倍の高速化となる．

4.10.6

この変更により，beqのストールが3サイクルに増加する．

• 変更前： Execution Time = 2,200[ps]
• 変更後： Execution Time = 2,400[ps]

よって，0.92倍となり，この変更では高速化されない．

4.11 Branching hazards

※land命令はand命令の誤記であるとして，解答を作成します．

4.11.1

		CC1	CC2	CC3	CC4	CC5	CC6	CC7	CC8	CC9	CC10	CC11	CC12	CC13	CC14	CC15	CC16	CC17	CC18	CC19	CC20	CC21	CC22	CC23	CC24	CC25	CC26	CC27	CC28	CC29
1st	lw	IF	ID	EX	MEM	WB
	and -> nop		IF	ID
	and			IF	ID	EX	MEM	WB
	lw				IF	ID	EX	MEM	WB
	lw -> nop					IF	ID
	lw						IF	ID	EX	MEM	WB
	beq -> nop							IF	ID
	beq								IF	ID	EX	MEM	WB
2nd	lw									IF	ID	EX	MEM	WB
	and -> nop										IF	ID
	and											IF	ID	EX	MEM	WB
	lw												IF	ID	EX	MEM	WB
	lw -> nop													IF	ID
	lw														IF	ID	EX	MEM	WB
	beq -> nop															IF	ID
	beq																IF	ID	EX	MEM	WB
3rd	lw																	IF	ID	EX	MEM	WB
	and -> nop																		IF	ID
	and																			IF	ID	EX	MEM	WB
	lw																				IF	ID	EX	MEM	WB
	lw -> nop																					IF	ID
	lw																						IF	ID	EX	MEM	WB
	beq -> nop																							IF	ID
	beq																								IF	ID	EX	MEM	WB

4.11.2

0%

全てのサイクルで5 stageのどれかが，nopとなっている．

4.12 Branching hazards

RAWデータ依存関係タイプの内訳を示した表の解釈が難しいです．

• ”すべての命令には，いずれかのタイプのRAWデータ依存関係がある”としながら，表の割合を合計しても100%にならない．
• "EX to 1stおよびMEM to 2nd"が指すものが不明．

そこで，下記と解釈して，解答を作成します．

		EXto1st	MEMto1st	EXto2nd	MEMto2nd	EXto1st MEMto2nd	others	EX or MEM 3rd以上
割合[%]	-	5%	20%	5%	10%	10%	10%	40%
stall cycle	no Forward	2	2	2	2	2	2	0
↑	All Forward	0	1	0	0	0	1	0
↑	EX/MEM Forward	0	2	1	1	1	2	0
↑	MEM/WB Forward	1	1	0	0	1	1	0

※"EXto1st"は，"片方のオペランドが一つ前の命令にデータ依存を持っており，EX stageでデータが利用可能になる(一つ前の命令がALU系命令である)．もう片方のオペランドはデータ依存関係を持っていない．"ことを示す．

※"EXto1st MEMto2nd" は，"片方のオペランドが一つ前の命令にデータ依存を持っており，EX stageでデータが利用可能になる．もう片方のオペランドは２つ前の命令にデータ依存を持っており，MEM stageでデータが利用可能になる(2つ前の命令がlw/swである)．" ことを示す．
※"others"は，"EXto1st EXto2nd", "MEMto1st EXto2nd","MEMto1st MEMto2nd"を示す．stall cycleが一意に定まらないため，最悪ケースの数値で解答を作成する．

※"EX or MEM 3rd以上"は，""前の命令とデータ依存を持つが，3命令以前の命令との依存関係なのでハザードを発生させない．”ことを示す．このような命令が全体の40%を占めると仮定する．

また，あるRAWハザードのためストールさせた際，別のRAWハザードも同時に解決できるパターンがあると思いますが，
与えられた情報からそれらを算出することは難しいため，今回は考慮しないこととします．

4.12.1

60%に対し，2cycleのストールが必要になる．

4.12.2

30%に対し，1cycleのストールが必要になる．

4.12.3

• EX/MEMフォワーディング： 85%
• MEM/WBフォワーディング: 45%

よって，MEM/WBフォワーディングのほうが，ストールさせるサイクル数が少なくて済む．

4.12.4

命令数をKとする．
フォワーディング無し・全面的フォワーディングともに，Clock Cycleは150[ps]である．

• フォワーディング無し: 330K[ps]
• 全面的フォワーディング: 195[ps]

よって，1.69倍の高速化となる．

4.12.5

命令数をKとする．
フォワーディング無しのClock Cycleは150[ps]，
データハザード全回避フォワーディングのClock Cycleは250[ps]である．

• フォワーディング無し: 330K[ps]
• データハザード全回避フォワーディング: 250K[ps]

よって，1.32倍の高速化となる．
全面的フォワーディングに比べ，高速化しない．

4.12.6

• EX/MEMフォワーディング： CPI = 1.85 [cycle/inst.] -> 277.5[ps/inst.]
• MEM/WBフォワーディング: CPI = 1.45 [cycle/inst.] -> 217.5[ps/inst.]

よって，MEM/WBフォワーディングのほうが，命令あたりの時間が短くなる．

4.13 Fowarding

4.13.1

add r5, r2, r1
nop
nop
lw r3, 4(r5)
lw r2, 0(r2)
nop
or r3, r5, r3
nop
nop
sw r3, 0(r5)

4.13.2

※4.13.1と結果が変わらない気がします．何か勘違いしているんですかね？

add r5, r2, r1
nop
nop
lw r3, 4(r5)
lw r2, 0(r2)
nop
or r3, r5, r3
nop
nop
sw r3, 0(r5)

※設問の命令列が誤記で，正しくは下記であるとして，解答を作成します．

add r5, r2, r1
lw r3, 4(r5)
lw r2, 0(r2)
or r3, r5, r2★
sw r3, 0(r5)

-解答-

add r5, r2, r1
lw r2, 0(r2)
nop
lw r3, 4(r5)
or r7, r5, r2
nop
nop
sw r7, 0(r5)

4.13.3

ストールは必要ないため，正常に実行される．

※やはり，設問の命令列が誤記であると思います．4.13.2と同様に，正しくは下記であるとして，解答を作成します．

add r5, r2, r1
lw r3, 4(r5)
lw r2, 0(r2)
or r3, r5, r2★
sw r3, 0(r5)

-解答-

or命令が参照する第二オペランドr2の値が不正となる．

具体的には，lw r2, 0(r2)実行前の値となってしまう．

これは，or命令で1cycleのストールが必要になるところ，ハザード検出ユニットが無いためにストールされなかったためである．

4.13.4

CC1:
CC2:
CC3:
CC4: FowardA = 10 // lw r3, 4(r5) のID stage
CC5: stall(PCWrite, IF/IDWrite: PCとIF/ID registerを保持する． ID/EX.RegWrite = 0 ID/EX.MemWrite = 0: or命令をnop扱いにする)

4.13.5

全てのデータハザードに対し，ストールする必要があるので，下記のような論理が必要になる．
p_stl_dhzd =1'b1のとき，パイプラインをストールすれば良い．

※Forwarding論理と似ているが，Forwading論理がEX stageで判定するのに対し，
stall論理はID stageで判定しなければならない．

assign p_stl_dhzd = (   // EXハザード
                            ID/EX.RegWrite
                        && (ID/EX.RegisterRd != 0)
                        && (   
                               (ID/EX.RegisterRd == IF/ID.RegisterRs)
                            || (ID/EX.RegisterRd == IF/ID.RegisterRt)
                           )
                    )
                 || (   // MEMハザード
                            EX/MEM.RegWrite
                        && (EX/MEM.RegisterRd != 0)
                        && (   
                               (EX/MEM.RegisterRd == IF/ID.RegisterRs)
                            || (EX/MEM.RegisterRd == IF/ID.RegisterRt)
                           )
                    )
                 || stall // EXハザード(lw) //既に実装済みのstall論理(p.304参照)
                 || (  // MEMハザード(lw)
                           EX/MEM.MemRead
                       && (   
                              (EX/MEM.RegisterRt == IF/ID.RegisterRs)
                           || (EX/MEM.RegisterRt == IF/ID.RegisterRt)
                          )
                   );

したがって，

• 新たな入力信号
  • ID/EX.RegWrite
  • ID/EX.RegisterRd
  • EX/MEM.RegWrite
  • EX/MEM.MemRead
  • EX/MEM.RegisterRd
  • EX/MEM.RegisterRs
  • EX/MEM.RegisterRt
• 新たな出力信号
  • 無し(既に実装されているハザード検出ユニットの出力信号PCWrite, IF/IDWriteなどを使ってパイプラインをストールさせれば良い．)

4.13.6

CC1:
CC2:
CC3: p_stl_dhzd // lw r3, 4(r5)のID stage -> stall
CC4: p_stl_dhzd
CC5: // lw r3, 4(r5)のID stage

4.14 Branch predication

4.14.1

		CC1	CC2	CC3	CC4	CC5	CC6	CC7	CC8	CC9	CC10	CC11	CC12	CC13	CC14	CC15	CC16
	lw r2, 0(r1)	IF	ID	EX	MEM	WB
label1:	beq r2, r0, label2		IF	ID	stall
label1:	beq r2, r0, label2			IF	ID	EX	MEM	WB
	lw r3, 0(r2)				IF	ID	EX	MEM	WB
	beq r3, r0, label1					IF	ID	stall
	beq r3, r0, label1						IF	ID	EX	MEM	WB
	add r1, r3, r1							IF	ID	flush
	sw r1, 0(r2)								IF	flush
label1:	beq r2, r0, label2									IF	ID	EX	MEM	WB
	lw r3, 0(r2)										IF	ID	flush
	beq r3, r0, label1											IF	flush
label2:	sw r1, 0(r2)												IF	ID	EX	MEM	WB

4.14.2

		CC1	CC2	CC3	CC4	CC5	CC6	CC7	CC8	CC9	CC10	CC11	CC12	CC13	CC14	CC15	CC16
	lw r2, 0(r1)	IF	ID	EX	MEM	WB
label1:	beq r2, r0, label2		IF	ID	stall
label1:	beq r2, r0, label2			IF	ID	EX	MEM	WB
	lw r3, 0(r2)				IF	ID	EX	MEM	WB	//slot
	beq r3, r0, label1					IF	ID	stall
	beq r3, r0, label1						IF	ID	EX	MEM	WB
	nop							//slot
	add r1, r3, r1								IF	flush
label1:	beq r2, r0, label2									IF	ID	EX	MEM	WB
	lw r3, 0(r2)										IF	ID	EX	MEM	WB	//slot
	beq r3, r0, label1											IF	flush
label2:	sw r1, 0(r2)												IF	ID	EX	MEM	WB

4.14.3

        lw r2,0(r1)
label1: seq r8, r2, r0
        bez r8, label2
        lw r3, 0(r2)
        seq r8, r3, r0
        bez r8, label1
        add r1, r3, r1
lael2:  sw r1, 0(r2)

4.14.4

新しいハザード検出ロジックが検出するハザードのタイプは，データハザードである．
具体的には，新しいハザード検出ロジックは，下記2下記2つの機能を提供する．
このハザード検出ロジックは，ID stageで動作する．
このハザード検知ロジックは，beq命令の分岐判定をID stageに移すためのフォワーディング論理が実装されていることを前提としている．

• ”beq命令が，1つ前の命令がWBする結果を用いて分岐判定する”データハザードを検知し，1サイクルストールさせる．
• ”beq命令が，2つ前のlw命令がWBする結果を用いて分岐判定する”データハザードを検知し，2サイクルストールさせる．
• ”beq命令が，2つ前のlw命令がWBする結果を用いて分岐判定する”データハザードを検知し，1サイクルストールさせる．

assign p_stl_dhzdbeq = (   // EXハザード
                            IF/ID.Branch
                        &&  ID/EX.RegWrite
                        && (ID/EX.RegisterRd != 0)
                        && (   
                               (ID/EX.RegisterRd == IF/ID.RegisterRs)
                            || (ID/EX.RegisterRd == IF/ID.RegisterRt)
                           )
                    )
                 || (  // EXハザード(lw)
                           IF/ID.Branch
                       &&  ID/EX.MemRead
                       && (   
                              (ID/EX.RegisterRt == IF/ID.RegisterRs)
                           || (ID/EX.RegisterRt == IF/ID.RegisterRt)
                          )
                   );
                 || (  // MEMハザード(lw)
                           IF/ID.Branch
                       &&  EX/MEM.MemRead
                       && (   
                              (EX/MEM.RegisterRt == IF/ID.RegisterRs)
                           || (EX/MEM.RegisterRt == IF/ID.RegisterRt)
                          )
                   );

4.14.5

上のコードに関して，分岐がEX stageで実行される場合，クロックサイクル数は16サイクルであった．(4.14.1)
これに対し，分岐がID stageで実行される場合，パイプライン図は下記のようになりクロックサイクル数は16サイクルのままである．
よって，1倍の速度向上となり改善も劣化もしない．

		CC1	CC2	CC3	CC4	CC5	CC6	CC7	CC8	CC9	CC10	CC11	CC12	CC13	CC14	CC15	CC16
	lw r2, 0(r1)	IF	ID	EX	MEM	WB
label1:	beq r2, r0, label2		IF	stall
label1:	beq r2, r0, label2			IF	stall
label1:	beq r2, r0, label2				IF	ID	EX	MEM	WB
	lw r3, 0(r2)					IF	ID	EX	MEM	WB
	beq r3, r0, label1						IF	stall
	beq r3, r0, label1							IF	stall
	beq r3, r0, label1								IF	ID	EX	MEM	WB
	add r1, r3, r1									flush
label1:	beq r2, r0, label2										IF	ID	EX	MEM	WB
	lw r3, 0(r2)											flush
label2:	sw r1, 0(r2)												IF	ID	EX	MEM	WB

• 根拠: 上のコードでは，計3回の分岐判定が実行される． この３回の分岐判定それぞれに対し，分岐のID stage繰り上げの実装がどのように影響するかを述べる．

第一の分岐判定では，直前のlw命令とのデータハザードが発生し，分岐不成立のため分岐ペナルティは発生しない．
よって，第一の分岐判定では，データハザードのストールで1サイクル損をする．
第二の分岐判定では，直前のlw命令とのデータハザードが発生し，分岐成立のため分岐ペナルティが発生する．
よって，第二の分岐判定では，データハザードのストールで1サイクル損をし，分岐ペナルティで1サイクル得をする．
最後の分岐判定では，データハザードのストールは無く，分岐成立のため分岐ペナルティが発生する．
よって，最後の分岐判定では，分岐ペナルティで1サイクル得をする．

以上より，クロックサイクル数は変わらない．

4.14.6

”新しいフォワーディングユニット"は，ID stageの"(beq命令)専用の比較器"にフォワーディングを行う．
具体的には，下記のようなフォワーディングを行う．
* ２つ前の命令がWBする結果をbeq命令が用いる場合，MEM stageからID stageにあるbeq命令に結果をバイパスする．(ただし，MEM stageの命令がALU命令の場合に限る)

なお，3つ前の命令がWBする結果を用いる場合は，"クロックサイクルの前半でレジスタへの書き込みを行い，後半でレジスタからの読み出しを行える"のでデータハザードは発生しない．よってフォワーディングしなくて良い．

フォワーディングユニットの回路規模は1.5倍程度になる．
変更前フォワーディングユニットは，変更後フォワーディングユニットおていて，beq命令以外の命令に対するフォワーディング論理としてそのまま必要で，これに加えて，上述beq命令専用のフォワーディング論理が必要になる．
beq命令の場合のフォワーディング論理は，beq命令専用のフォワーディング論理は，ほぼ半分程度の回路規模になると思わる．

※"複雑性"って何でしょうね？

4.15 Branch predication

4.15.1

分岐ペナルティは２サイクルとなる．
したがって，CPIは1.275倍となる．

4.15.2

CPIは1.225倍となる．

4.15.3

CPIは1.075倍となる．

4.15.4

CPIは，1.0375倍となる．
よって，1.036倍の高速化となり，ほとんど速度向上しない．

4.15.5

CPIは1.1625倍となる．
よって，0.925倍の高速化となり，この変換では速度向上しない．

4.15.6

25%

4.16 Branch predication

4.16.1

常に成立: 60%
常に不成立: 40%

4.16.2

25%

4.16.3

60%

設問に示された分岐パターン(分岐5回)が無限に繰り返される場合，予測精度はどうなるか？という問題です．
5回の分岐のうちTakenが3回，Not Takenが2回であるので，2bit予測方式の状態はStrongly Taken側に遷移していきます．
しかしながら，5回の分岐のうち最後の一回がNot Takenです．

したがって，設問に示された分岐パターンが無限に繰り返されるということは，
2bit予測方式の状態がWeakly Takenで，設問に示された分岐パターンが始まるというケースが無限に繰り返されるということです．

4.16.4

設問に示された分岐パターンが無限に繰り返される場合に，
完全に正確となる予測機構BRPDAを下記に示す．

module BRPDA ( // Branch Predictor A
  input clk,
  input rst,
  input p_val, // 条件分岐であることを示す制御信号
  output p_tkn // 予測結果, assert: Taken, deassert: NotTaken
  );
  reg [2:0] stat; //d0,d1,d2,d3,d4,d0,d1,...
  always @(posedge clk or negedge rst) begin
    if (rst == 1'b0)) begin
      stat <= 3'd0;
      end
    else begin
      if (p_val == 1'b1) begin // enable signal
        stat <= (stat == 3'd4) 3'd0
                             : stat + 3'd1;
        end
      end
    end
  assign p_tkn = stat[1] | ~stat[1] & ~stat[0];
  endmodule

※p_valがdeassertのサイクルは，p_tknは無意味な信号です．
BRPDAを使う親モジュールは，p_valがassetされp_tknを取得すべきタイミングがわかっている
と仮定するのが自然です．

使用資源見積もりは下記です．

• 3bit幅FF(enable付き)x1
• セレクタx1
• ANDゲート換算x4程度
• 3bit加算器x1

4.16.5

0%

4.16.6

設問に示された分岐パターンと，その正反対のパターンが無限に繰り返される場合に，
(予測誤りが生じる最初の分岐以外は)完全に正確となる予測機構BRPDBを下記に示す．

module BRPDB ( // Branch Predictor B
  input clk,
  input rst,
  input p_val, // 条件分岐であることを示す制御信号
  input p_tkn_prvs, // 簡単のため，前回の分岐結果をp_valに同期して与えられるとする,
                    // assert: Taken, deassert: NotTaken
  output p_tkn // 予測結果, assert: Taken, deassert: NotTaken
  );
  reg [2:0] stat; //d0,d1,d2,d3,d4,d0,d1,...
  wire m_mode_a; // 0:設問に示された分岐パターン,　１：その正反対のパターン
  always @(posedge clk or negedge rst) begin
    if (rst == 1'b0)) begin
      stat <= 3'd0;
      end
    else begin
      if (p_val == 1'b1) begin // enable signal
        stat <= (stat == 3'd4) 3'd0
                             : stat + 3'd1;
        end
      end
    end
  assign m_mode_a = p_tkn_prvs ~^ (stat[2] | (stat[1] ^ stat[0]));   
  assign p_tkn = m_mode_a ^ (stat[1] | ~stat[1] & ~stat[0]);
  endmodule

現在のstatから前回の分岐予測を再計算して，
前回の予測があっていたか判定し，
最終的な今回の予測p_tknを決定する構成になっています．
この部分がクリティカルパスです．
XNORx1,XORx2とディレイが厳しいと思われます．
改善が必要かもしれません．

また，分岐結果が，p_val（予測）の何サイクル後にわかるのか，
前回の条件分岐が何サイクルなのかなどの設定が不明なので，
100%の解答が作れないですね．

4.17 Exceptions

4.17.1

• bne r1, r2, label1
  • Ov: 算術オーバーフロー ※ @ ID stage
  • AdEL：　アドレス・エラー例外(load or i-fetch) @ EX stage
  • IBE: 命令フェッチ時のバス・エラー @ IF stage
  • TLB miss @ IF stage
  • Page fault @ IF stage

※ bne命令におて，($PC + 4) + signExt(imm16 << 2)の加算器におけるOverflowのつもりで書きました．
図4.65に従い，上記加算器はID stageにあるとします．
このOverflowも，Causeレジスタの例外コード12:Ov,算術オーバーフロー例外として報告されるのかはわかっていません．

• lw r1, 0(r1)
  • AdEL: アドレス・エラー例外(load or i-fetch) @ Ex stage
  • DBE: データのロードまたはストア時のバス・エラー @ MEM stage
  • TLB miss @ MEM stage
  • Page fault @ MEM stage

4.17.2

下記3つの構成を追加する．

1. 各種例外検知の有効/無効を設定できる特殊な制御レジスタ
2. 各種例外のプライオリティを決定する構成
3. 上記各種例外のプライオリティを決定するユニットの結果にしたがって，例外ハンドラのアドレス(既知)から次クロックサイクルの$PCを選択する構成

4.17.3

例外ハンドラの最初の命令をmfc0 $k0 , $13とする．その後続の命令はinst ?と表記した．

1. bne命令のID stageで次サイクルの$PCを計算する加算器がOverflow
2. bne命令@ID, lw命令@IFがflushされる．※EX, MEM, WB stageの命令はflushされない
3. CC3で，例外ハンドラの最初の命令であるmfc0 $k0 , $13がIFされる．

	CC1	CC2	CC3	CC4	CC5	CC6	CC7
bne r1, r2, label	IF	ID	-> Ov exception
lw r1, 0(r1)		IF	flush
mfc0 \$k0 \$13			IF	ID	EX	MEM	WB
inst ?				IF	ID	EX	MEM
inst ?					IF	ID	EX

4.17.4

例外ハンドラのアドレスをメモリから取得する必要があり，これには１クロックサイクルを要する．
したがって，下記のように１クロックサイクルだけパイプラインをstallすると良い．

• 例外発生サイクル：発生した例外にしたがって，メモリ・アドレスを決定する．
• stallサイクル: 例外ハンドラのアドレスをメモリから取得する．このとき，取得した例外ハンドラのアドレスを直接$PCにセットする．また，IF stageの命令はflushする．(命令メモリから読み出されても, IF/IDレジスタにラッチされないようにする)
• 例外ハンドラ開始サイクル： 例外ハンドラの最初の命令がIFされる．

	CC1	CC2	CC3	CC4	CC5	CC6	CC7	CC8
bne r1, r2, label	IF	ID	-> Ov exception
lw r1, 0(r1)		IF	flush
stall cycle			IF -> flush
mfc0 \$ k0 \$13				IF	ID	EX	MEM	WB
inst ?					IF	ID	EX	MEM
inst ?						IF	ID	EX

※複数の例外が同時に発生するケースに対応しきれていないです．その場合，どの方法がベストかわかりませんでした．

4.17.5

下記のように，例外コードを見て，例外に対処するルーチンを呼び出す命令が必要．

mfc0 $k0, $14 // Causeレジスタを$k0に移す
srl $k0, 2 // 例外コードフィールドを抽出
andi $k0, 0x1F // 例外コードフィールドを抽出
beq $k0, $zero, ExcHdr_Int // ハードウェア割り込みの場合
ori $k1, $zero, 0x04
beq $k1, $zero, ExcHdr_AdEL // アドレス・エラー例外(load or i-fetch)の場合
ori $k1, $zero, 0x05
beq $k1, $zero, ExcHdr_AdES // アドレス・エラー例外(store)の場合
(以下略)

4.18 Parallelism and Advanced Instruction-Level Parallelism

4.18.1

指定がないため，変数は全てINT32とみなす．

      and r5, $zero, $zero // i = 0
      beq r5, r6, Done // if i == j then; goto Done
Loop: add r10, r5, r1 // address: a[i]
      lw r11, 0(r10) // a[i]
      lw r12, 4(r10) // a[i + 1]
      sub r11, r11, r12 // a[i] - a[i + 1]
      add r10, r5, r2 // address: b[i]
      sw r11, 0(r10) // b[i] = a[i] - a[i + 1]
      addi r5, r5, 2 // i += 2
      bne r5, r6, Loop // if i != j then; goto Loop
Done:

4.18.2

設問文の通り，”２つの命令を実行した直後にループが終了”とするなら，解答は下記のようになります．

		CC1	CC2	CC3	CC4	CC5	CC6	CC7
	and r5, \$zero, \$zero	IF	ID	EX	MEM	WB
	beq r5, r6, Done	IF	stall	stall	ID	EX	MEM	WB
Done:	inst?				IF	ID	EX	MEM
	inst?				IF	ID	EX	MEM

おそらく，”イテレーションが２回完了した後，ループが終了する”の誤記だと思われます．
この仮定で，解答を作成します．

		CC1	CC2	CC3	CC4	CC5	CC6	CC7	CC8	CC9	CC10	CC11	CC12	CC13	CC14	CC15	CC16	CC17	CC18	CC19	CC20	CC21	CC22	CC23	CC24	CC25	CC26	CC27
	and r5, \$zero, \$zero	IF	ID	EX	MEM	WB
	beq r5, r6, Done	IF	stall	stall	ID	EX	MEM	WB
Loop:	add r10, r5, r1				IF	ID	EX	MEM	WB
	lw r11, 0(r10)				IF	ID	stall	EX	MEM	WB
	lw r12, 4(r10)					IF	stall	ID	EX	MEM	WB
	sub r11, r11, r12					IF	stall	ID	stall	stall	EX	MEM	WB
	add r10, r5, r2							IF	stall	stall	ID	EX	MEM	WB
	sw r11, 0(r10)							IF	stall	stall	ID	stall	EX	MEM	WB
	addi r5, r5, 2										IF	stall	ID	EX	MEM	WB
	bne r5, r6, Loop										IF	stall	stall	stall	ID	EX	MEM	WB
Loop:	add r10, r5, r1														IF	ID	EX	MEM	WB
	lw r11, 0(r10)														IF	ID	stall	EX	MEM	WB
	lw r12, 4(r10)															IF	stall	ID	EX	MEM	WB
	sub r11, r11, r12															IF	stall	ID	stall	stall	EX	MEM	WB
	add r10, r5, r2																	IF	stall	stall	ID	EX	MEM	WB
	sw r11, 0(r10)																	IF	stall	stall	ID	stall	EX	MEM	WB
	addi r5, r5, 2																				IF	stall	ID	EX	MEM	WB
	bne r5, r6, Loop																				IF	stall	stall	stall	ID	EX	MEM	WB
Done:	inst?																								IF	ID	EX	MEM

4.18.3

      and r5, $zero, $zero // i = 0
      beq r5, r6, Done // if i == j then; goto Done
Loop: add r10, r5, r1 // address: a[i]
      add r12, r5, r2 // address: b[i]
      lw r11, 0(r10) // a[i]
      lw r10, 4(r10) // a[i + 1]
      addi r5, r5, 2 // i += 2
      sub r10, r11, r10 // a[i] - a[i + 1]
      sw r10, 0(r12) // b[i] = a[i] - a[i + 1]
      bne r5, r6, Loop // if i != j then; goto Loop
Done:

4.18.4

設問文が，”イテレーションが２回完了した後，ループが終了する”の誤記だとして，解答を作成します．

		CC1	CC2	CC3	CC4	CC5	CC6	CC7	CC8	CC9	CC10	CC11	CC12	CC13	CC14	CC15	CC16	CC17
	and r5, \$zero, \$zero	IF	ID	EX	MEM	WB
	beq r5, r6, Done	IF	stall	stall	ID	EX	MEM	WB
Loop:	add r10, r5, r1				IF	ID	EX	MEM	WB
	add r12, r5, r2				IF	ID	EX	MEM	WB
	lw r12, 4(r10)					IF	ID	EX	MEM	WB
	lw r10, 4(r10)					IF	ID	EX	MEM	WB
	sub r10, r11, r10						IF	ID	stall	EX	MEM	WB
	addi r5, r5, 2						IF	ID	EX	MEM	WB
	sw r10, 0(r12)							IF	stall	ID	EX	MEM	WB
	bne r5, r6, Loop							IF	stall	ID	EX	MEM	WB
Loop:	add r10, r5, r1									IF	ID	EX	MEM	WB
	add r12, r5, r2									IF	ID	EX	MEM	WB
	lw r12, 4(r10)										IF	ID	EX	MEM	WB
	addi r5, r5, 2										IF	ID	EX	MEM	WB
	lw r10, 4(r10)											IF	ID	stall	EX	MEM	WB
	sub r10, r11, r10											IF	ID	EX	MEM	WB
	addi r5, r5, 2												IF	stall	ID	EX	MEM	WB
	bne r5, r6, Loop												IF	stall	ID	EX	MEM	WB
Done	inst?														IF	ID	EX	MEM

4.18.5

• 1命令発行プロセッサの場合：

Loopの部分は下記のようになるので，
CPI = 14[cycle] / 8 [inst.] = 1.75

		CC1	CC2	CC3	CC4	CC5	CC6	CC7	CC8	CC9	CC10	CC11	CC12	CC13	CC14
Loop:	add r10, r5, r1	IF	ID	EX	MEM	WB
	lw r11, 0(r10)		IF	ID	EX	MEM	WB
	lw r12, 4(r10)			IF	ID	EX	MEM	WB
	sub r11, r11, r12				IF	ID	stall	EX	MEM	WB
	add r10, r5, r2					IF	stall	ID	EX	MEM	WB
	sw r11, 0(r10)							IF	ID	EX	MEM	WB
	addi r5, r5, 2								IF	ID	EX	MEM	WB
	bne r5, r6, Loop									IF	stall	ID	EX	MEM	WB

• 2命令発行プロセッサの場合：

4.18.1で翻訳したコードを使えと書いていますが，
２命令発行プロセッサは”任意の命令をフェッチできる”と書いてあります．
つまり，２命令プロセッサ側は，コードを自由に並び替えてチューニングして良いということです．

よって，4.18.3で組み直したコードの順でフェッチするとします．
Loopの部分は，4.18.4に示した通りとなるので，
CPI = 9 [cycle] / 8 [inst.] = 1.13

以上より，1.56倍の高速化となります．
※ 14 [cycle] / 9 [cycle] = 1.56

4.18.6

• 1命令発行プロセッサの場合：

4.18.5と同様です．
CPI = 14[cycle] / 8 [inst.] = 1.75

• 2命令発行プロセッサの場合：

メモリアクセス命令は，同時に１命令しか発行できないという条件がついたので，命令列を書き直します．

      and r5, $zero, $zero // i = 0
      beq r5, r6, Done // if i == j then; goto Done
Loop: add r10, r5, r1 // address: a[i]
      add r12, r5, r2 // address: b[i]
      lw r11, 0(r10) // a[i]
      addi r5, r5, 2 // i += 2
      lw r10, 4(r10) // a[i + 1]
      sub r10, r11, r10 // a[i] - a[i + 1]
      sw r10, 0(r12) // b[i] = a[i] - a[i + 1]
      bne r5, r6, Loop // if i != j then; goto Loop
Done:

パイプライン図は下記となります．

		CC1	CC2	CC3	CC4	CC5	CC6	CC7	CC8	CC9	CC10	CC11	CC12	CC13	CC14	CC15	CC16	CC17	CC18	CC19	CC20	CC21
	and r5, \$zero, \$zero	IF	ID	EX	MEM	WB
	beq r5, r6, Done	IF	stall	stall	ID	EX	MEM	WB
Loop:	add r10, r5, r1				IF	ID	EX	MEM	WB
	add r12, r5, r2				IF	ID	EX	MEM	WB
	lw r12, 4(r10)					IF	ID	EX	MEM	WB
	addi r5, r5, 2					IF	ID	EX	MEM	WB
	lw r10, 4(r10)							IF	ID	EX	MEM	WB
	sub r10, r11, r10							IF	ID	stall	stall	EX	MEM	WB
	sw r10, 0(r12)								IF	stall	stall	ID	EX	MEM	WB
	bne r5, r6, Loop								IF	stall	stall	ID	EX	MEM	WB
Loop:	add r10, r5, r1											IF	ID	EX	MEM	WB
	add r12, r5, r2											IF	ID	EX	MEM	WB
	lw r12, 4(r10)												IF	ID	EX	MEM	WB
	addi r5, r5, 2												IF	ID	EX	MEM	WB
	lw r10, 4(r10)														IF	ID	EX	MEM	WB
	sub r10, r11, r10														IF	ID	stall	stall	EX	MEM	WB
	addi r5, r5, 2															IF	stall	stall	ID	EX	MEM	WB
	bne r5, r6, Loop															IF	stall	stall	ID	EX	MEM	WB
Done	inst?																		IF	ID	EX	MEM

CPI = 11[cycle] / 8 [inst.] = 1.375

以上より， 1.27倍の高速化となります．
※14 [cycle] / 11 [cycle] = 1.27

4.19 Energy and Performance

各構成要素のレイテンシを示したに"命令メモリの読み出しまたは書き込み"という記述がありますが，
”データ・メモリの読み出しまたは書き込み”の誤記であるとして，解答を作成します．

4.19.1

140 + 70 x2 + 60 = 340[pJ]

4.19.2

lw命令: 140 + 70 x2 + 60 + 140 = 480[pJ]

4.19.3

設問の意図が汲み取れないのですが，下記２点を忖度して解答を作成します．

1. ”レジスタの読み出しまたは書き込み”のレイテンシがわざわざ明記されている点
2. 設問4.19.5"MemRead=1に固定しておける"という記述がある点

• 設計変更：lw命令や，即値を使う命令など，ソースレジスタを１つしかとらない命令を実行する際，レジスタを片方しか読み出さないようにする．また，nop命令は，レジスタを読み出さないようにする．

• lw命令実行時の消費エネルギー削減割合:
  lw命令により消費されるエネルギーは， 140 + 70 + 60 + 140 = 410[pJ]となる．
  したがって，70[pJ]/480[pJ] = 14.6%の消費エネルギー削減となる．

4.19.4

4.19.4の変更により，ID stageのレイテンシが，150[ps]から，240[ps]となる．
しかしながら，Cycle timeは250[ps]のまま変わらない．よって，性能への影響はない．

※本来，レジスタファイルから読み出すべきレジスタは，命令のフィールド中の固定された位置
(rs[25:21], rt[20:16],rd[15:11])を読み取れば済むため，
制御(150[ps])とレジスタ読み出し(90[ps])は並列に動作できる．
しかし，今回の変更により，命令をデコードして，nop命令ならレジスタを読み出さないようにし，
ソースレジスタを１つしかとらない命令ならレジスタを１つしかとらないようにする必要がある．
したがってID stageのレイテンシが増大する．(ということが，設問の意図だと思われる．)

4.19.5

• p.294の図4.51に示されている通り，RegWriteやMemtoRegが適切に生成されていれば，
  意図せずメモリから読み出してしまったデータをレジスタに書き込むことは無いから．

• この変更を行っても，Cycle Timeに影響を与えない．したがって，クロック周波数は変化しない．

• 全ての命令のMEM stageでデータ・メモリの読み出しが発生してしまうため，消費エネルギーは増大する．

4.19.6

アイドル状態時の消費エネルギーを考慮すると，命令メモリによって消費されるエネルギーは下記のようになる．
140 + 140 x0.1 x(250-200)/200 = 143.5[pJ]

よって，3.5[pJ]/143.5[pJ] = 2.4%