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

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

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

# 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

<!-- 2308 -->

# 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で判定しなければならない．

```verilog
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サイクルストールさせる．

```verilog
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`を下記に示す．


```verilog
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`を下記に示す．

```verilog
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%