# Quiz4 of Computer Architecture (term project)
> Solutions

## Question `A`

For each of the questions below, create a valid K-stage pipeline of the given circuit. Each component in the circuit is annotated with its propagation delay. Give the latency and throughput of each design, assuming ideal registers (t~PD~ = 0, t~SETUP~ = 0). Remember that our convention is to place a pipeline register on each output.

(1) Show the maximum-throughput 1-stage pipeline.

Latency (ns): __ A01 __
Throughput (ns^-1^): __ A02 __

> 
> $C \to 3 \to 4 \to 2 \to 2$

> t~CLK~ = 3 + 4 + 2 + 2 = 11 ns
> A01 = ==11== ns
> A02 = ==$\frac{1}{11}$== ns
> #說明：1-stage 的pipeline 所以 最長的路徑為3-4-2-2 = 11
> throughput則為1/11

(2) Show the maximum-throughput 2-stage pipeline using a minimal number of registers.

Latency (ns): __ A03 __
Throughput (ns^-1^): __ A04 __

> 
> A03 = ==14==
> A04 = ==$\frac{1}{7}$==
> t~CLK~ = 3 + 4 = 7 ns
> latency = 2 * 7 = 14 ns
> #說明：propagation delay is 4ns, but there is no way to narrow critical path to 4ns just by 2-stage pipeline.

(3) Show the maximum-throughput pipeline using a minimal number of registers.

Latency (ns): __ A05 __
Throughput (ns^-1^): __ A06 __

> 
> A05 = ==12==
> A06 = ==$\frac{1}{4}$==
> t~CLK~ = 4 ns
> latency = 3 * 4 = 12 ns
> ＃說明： the maximum-throughput means the critical path in a single stage needs to be the smallest 4ns.

(4) You manage to reimplement the slowest combinational component in the previous circuit (the one with a propagation delay of 4 ns) using two components with propagation delays of 2 ns, as shown below. Show the maximum-throughput pipeline using a minimal number of registers.

Latency (ns): __ A07 __
Throughput (ns^-1^): __ A08 __

> 
> A07 = ==12==
> A08 = ==$\frac{1}{3}$==
> t~CLK~ = 3 ns
> latency = 4 * 3 = 12
＃說明：propagation delay is 3ns, so our goal is making the critical path in a single stage to be 3ns.

---

## Question `B`

For each of the questions below, please create a valid K-stage pipeline of the given circuit. Each component in the circuit is annotated with its propagation delay in nanoseconds. Give the latency and throughput of each design, assuming ideal registers (t~PD~ = 0, t~SETUP~ = 0). Remember that our convention is to place a pipeline register on each output.

(1) Show a maximum-throughput pipeline that uses the smallest possible number of pipeline stages.

Latency (ns): __ B01 __
Throughput (ns^-1^): __ B02 __

> 
> B01 = ==12==
> B02 = ==$\frac{1}{4}$==
> t~CLK~ = 4 ns
> latency = 3 * 4 = 12 ns
> #說明：maximum throughput = critical path in a single stage = 4ns
> latency is 4 * 3 = 12ns

(2) You reimplement the 4 ns combinational component in the previous circuit using two faster components connected in series, shown in **grey** below. You can choose the propagation delays of these two components, as long as their delays add to 4 ns (e.g., they could be 3 ns and 1 ns, 2 ns and 2 ns, etc.) Choose the propagation delays of both components in a way that lets you pipeline the circuit for maximum throughput while minimizing the number of pipeline stages. Then, find the maximum-throughput pipeline. For full credit, your solution should use the minimum possible number of pipeline stages.

Latency (ns): __ B03 __
Throughput (ns^-1^): __ B04 __

> 
> B03 = ==9==
> B04 = ==$\frac{1}{3}$==
> t~CLK~ = 3 ns
> latency = 3 * 3 = 9 ns
>

---

## Question `C`

For each of the questions below, please create a valid K-stage pipeline of the given circuit. Each component in the circuit is annotated with its propagation delay in nanoseconds. Give the latency and throughput of each design, assuming ideal registers (t~PD~ = 0, t~SETUP~ = 0). Remember that our convention is to place a pipeline register on each output.

(1) Show the maximum-throughput 2-stage pipeline using a minimal number of registers. What are the latency and throughput of the resulting circuit?

Latency (ns): __ C01 __
Throughput (ns^-1^): __ C02 __

> 
> C01 = ==20==
> C02 = ==$\frac{1}{10}$==
> t~CLK~ = 6 + 4 = 10 ns
> latency = 2 * 10 = 20 ns
> ＃說明： longest propagation delay is 6ns, so 2-stage pipeline -> 6 + 4 = 10
> latency = 10*2 = 20
> throughput = 1/10 ns
>

(2) Show the maximum-throughput pipeline using a minimal number of registers. What are the latency and throughput of the resulting circuit?

Latency (ns): __ C03 __
Throughput (ns^-1^): __ C04 __

> 
> C03 = ==24==
> C04 = ==$\frac{1}{6}$==
> t~CLK~ = 6 ns
> latency = 4 * 6 = 24 ns
> The maximum-throughput = smallest critical path = 6ns
> latency = 6 * 4 = 24 ns

---

## Question `D`

Consider the below 5-Stage Pipeline processor.

(1) Even a simple, in-order pipelined processor makes use of speculative execution. For the 5-stage pipeline above, assume that there is no virtual memory, and that misaligned accesses are checked in the Execute stage. For the instruction sequence below, complete the execution diagram and mention the cycles in which the second add is being executed speculatively. For example, if one stage F is being executed speculatively, use the remark `F (S)`.

| Clock Cycle | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| ----------- | - | - | - | - | - | - | - | - | - | - |
| `add x1, x2, x0` | F | D | X | M | W | - | - | - | - | - |
| `lw x3, 0(x2)` | - | D01 | D02 | D03 | D04 | D05 | - | - | - | - |
| `add x3, x4, x5` | - | - | D06 | D07 | D08 | D09 | D10 | - | - | - |

> D01 = ==F==
> D02 = ==D==
> D03 = ==X==
> D04 = ==M==
> D05 = ==W==
> D06 = ==F (S)==
> D07 = ==D (S)==
> D08 = ==X==
> D09 = ==M==
> D10 = ==W==
> * It is speculative until it is known that neither the add nor either preceding instruction will cause an exception.
> * The `lw` can except through the end of the Execute stage, so any execution of following instructions is speculative while the lw is in the Fetch, Decode, or Execute stages.
> * The `add` cannot except after it is decoded, as there are no arithmetic condition exceptions in RISC-V.

(2) Given the 5-stage pipeline above, how long is the load-use delay? Answer in terms of how many bubbles must be added between a load and a dependent register-register instruction that is fetched right after the load.
How many bubble(s) must be added? __ D11 __
> D11 = ==1==
> One bubble must be added; this means that the load-use delay is one cycle.
> #說明： CPU above has bypass in MEM stage, we should only add one bubble.

---

## Question `E`

Consider the 5-Stage pipeline RISC-V processor.

(1) How many cycles does it take to run each iteration of the following loop on a standard 5-stage pipelined RISC-V processor (P1)?

loop: lw x10, 0x100(x0)
      beqz x10, loop
      add x12, x10, x11
      sub x13, x12, x1

Number of cycles per loop iteration: __ E01 __
> E01 = ==6==
> 
>

(2) Consider a modified processor, P2, which has extra hardware for the special case of checking if a register is equal to zero or not in the decode stage. What would be the number of cycles per loop iteration in this case?
Number of cycles per loop iteration on processor P2: __ E02 __
> E02 = ==5==
> 

(3) Now consider a third processor, P3, whose instruction and data memories are pipelined and take 2 clock cycles to respond. Assume that P3 also has the extra hardware for checking if a register is equal to zero or not in the decode stage. What would be the number of cycles per loop iteration using P3?
NOP Number of cycles per loop iteration on processor P3: __ E03 __
> E03 = ==7==
> 

---

## Question `F`

You have been given a 5-stage pipelined RISC-V processor. Unfortunately, the processor you hve been given is defective: it has no bypass paths, annulment of instructions in branch delay slots, or pipeline stalls.

      nop
      nop
      nop
      nop
Loop: lw x10, 0x0(x10)
AAA:
      sll x14, x10, x11
BBB:
      bnez x10, loop
CCC:
      add x13, x10, x13
      nop
      nop
      nop
      nop

You undertake to convert some existing code, designed to run on an unpipelined RISC-V, to run on your defective pipelined processor. The scrap of code on above is a sample of the program to be converted. It doesn’t make much sense to you, but you are to add the minimum number of NOP instructions at the various tagged points in this code to make it give the same results on your defective pipelined RISC-V as it gives on a normal, unpipelined RISC-V.

Note that the code scrap begins and ends with sequences of NOPs; thus, you do not need to worry about pipeline hazards involving interactions with instructions outside of the region shown.

(1) Specify the minimal number of NOP instructions (defined as `add x0, x0, x0`) to be added at each of the labeled points in the above program.
NOPs at Loop: __ F01 __
NOPs at AAA: __ F02 __
NOPs at BBB: __ F03 __
NOPs at CCC: __ F04 __
> F01 = ==0==
> F02 = ==3==
> F03 = ==0==
> F04 = ==2==
> Below is a diagram of the instruction flow for this program. Note that nextPC is available in the execute stage of the bnez instruction even without bypassing.
> 

(2) On a fully functional 5-stage pipeline (with working bypass, annul, and stall logic), the above code will run fine with no added NOPs. How many clock cycles of execution time are required by the fully functional 5-stage pipelined RISC-V for each iteration through the loop?

Clocks per loop iteration: __ F05 __
> F05 = ==7==
> Below is a diagram of the instruction flow for this program.
> 

---

## Question `G`

The following programs are being executed on the 5-stage pipelined RISC-V processor with full bypassing. For each fragment, the pipeline diagram shows the state of the pipeline for cycle 1000 of execution. Please fill in the diagram for cycle 1001; use `?` if you cannot tell what opcode to write into a stage.

(1) Program

    ...
sw   x1, 0(x0)
lw   x17, 0xC(x1)
addi x2, x2, -4
slli x11, x17, 2
sw   x11, 0(x2)
jal  ra, fact
    ...

| Cycle | 1000 | 1001 |
| ----- | ---- | ---- |
| IF | sw | G01 |
| ID | slli | G02 |
| IE | addi | G03 |
| MEM | lw | G04 |
| WB | sw | G05 |

> G01 = ==sw==
> G02 = ==slli==
> G03 = ==NOP==
> G04 = ==addi==
> G05 = ==lw==
> Reverse form for each instruction. For both cycles use arrows to indicate any bypassing from the EXE/MEM/WB stages back to the instruction decoding (DEC) stage.
> 
>
> To figure out if we need to add a NOP, we look at the instruction we are decoding: `slli x11, x17, 2`. Not all of these values are available to us by cycle 1000. Specifically, `x17` was modified by the lw instruction. Notice from the pipeline diagram that lw is still in the MEM stage at cycle 1000, meaning that it has just sent a request to the data memory. However, the data memory does not return the data until one clock cycle later. Therefore, we need to insert a `NOP` to wait for the lw to reach the WB stage. At the end of cycle 1001, the lw has reached the WB stage which means the data has been retrieved from memory and can be bypassed up to the DEC instruction to decode the slli instruction that has been stalled there for one cycle.

:warning:Here to explain why we can't use the bypass in MEM stage to avoid the stall in EXE stage :
reference video:https://www.youtube.com/watch?v=TMpjvAvQCWA&t=1657s
At the time [32:44]，you can see the **lw** data is forward at the write back stage.
At the time [31:39], you can see the pipeline logic，and the memory **has no output port** in the MEM stage, we just can get the data in write back stage. However, there is a bypass wire from MEM stage(green line) ,what's the function of the wire?I think that the video has answered the question at [30:20] ，the bypass wire is for the situation that if there are two instructions(not load-use) with data dependency,and there is a instruction(without dependency) between the two instructions like:

addi x13 x12 x11
add  x17 x15 x16 
xor  x10 x13 x14

(2) Program

    ...
xor  x11, x11, x12
slli x12, x12, 3
sub  x13, x12, x11
and  x12, x13, x11
add  x13, x12, x13
sw   x13, 0x100(x0)
    ...

| Cycle | 1000 | 1001 |
| ----- | ---- | ---- |
| IF | add | G06 |
| ID | and | G07 |
| IE | sub | G08 |
| MEM | slli | G09 |
| WB | xor | G10 |

> G06 = ==sw==
> G07 = ==add==
> G08 = ==and==
> G09 = ==sub==
> G10 = ==slli==
>
> For both cycles use arrows to indicate any bypassing from the EXE/MEM/WB stages back to the instruction decoding (DEC) stage.
> 
>
> In cycle 1000, the and instruction is being decoded in the DEC stage. The and instruction relies on registers `x11` and `x13`. Both of these registers were updated within 3 cycles of the and instruction, so the results of these registers have not yet been written back into the register files. The value of `x13` is set by the sub instruction which is currently in the EXE stage. Similarly, the value for `x11` needs to be bypassed from the WB stage since it is set by the `xor` instruction.
>
> Since all required register values could be retrieved in cycle 1000, there is no need for a `NOP`. We process the next instruction which is a `sw` instruction. The `add` instruction is now being decoded and requires the values in `x12` and `x13`. These were modified by the `and` and `sub` instructions, so we need to bypass from the EXE and MEM stages.

---