# Quiz 5 Annotation

### Quiz5 Links
https://hackmd.io/@sysprog/arch2021-quiz5-sol
<!--
Reference
https://hackmd.io/@shauming1020/ca-quiz5

[Quiz-5_marks.xlsx](https://www.youtube.com/watch?v=dQw4w9WgXcQ)
-->
## Problem A

Consider the G circuit, depicted on the following.


Since the G circuit is currently only combinational, you know exactly what to do: Pipeline it.

1. For your first iteration, you decide to start small with a two-stage pipeline. Using the diagram below, please show a two-stage pipeline with maximal throughput using a minimum number of registers. Calculate the overall throughput and latency of your circuit.

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

- A01 = 24
- A02 = 1/12
### 📝 Annotate
:::info
#### Why the stages is arrange like this?
To create a pipeline with maximal throughput, we need to split the circuit into stages while trying to reduce the differences of latency within stages.


In the split above, the maxmium latency of stage 1 (on the left side of the circuit) is:
**2 + 5 + 3 + 1 = 11ns**

And the maxmium latency of stage 2 is:
**7 + 1 + 4 = 12ns**.

The difference of maxmium latency between two stage is 1, which is small enough to maximized this pipeline throughput.

#### How to calculate Latency and Throughput?
Latency = Maxmium value of slowest path in all stages * number of stages

If we split the stage into two as follows:

**The Latency is equal to 12 * 2 = 24 ns**

Throughput is equal to 1 over the Maxmium value of slowest path in all stage (which is 12 in this case), hence the value of throughput in this circuit is

**Throughput = 1/12 ns**

:::

2. Now, you decide to add an additional stage. Using the diagram below, please show a three-stage pipeline with maximal throughput using a minimum number of registers. Calculate the overall throughput and latency of your circuit.

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

- A03 = 30
- A04 = 1/10

### 📝 Annotate
:::info
The three stage is draw like followings.

Then we can calculate the maximum latency in each stage as follows.

**Latency = Max(10, 8, 5) * 3 = 10 * 3 = 30ns**
**Throughtput = 1/10 ns**

Also notes that if you split the stages like so, it will not work as some stage output is pointing to the previous stage.
:::

3. Then, think of the maximalthroughput pipeline. Using the diagram below, please show a pipeline that maximizes the throughput using a minimum number of registers. Calculate the latency and throughput of your circuit. For full credit you pipelined circuit should use the smallest number of pipeline stages required to achieve maximum throughput.

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

- A05 = 28
- A06 = 1/7

### 📝 Annotate
:::info
The stages are arranged as follows.

The maxmium latency in each stage is as follows.

**Latency = Max(7, 7, 5, 4) * 4 = 7 * 4 = 28ns**
**Throughtput = 1/7 ns**
:::

## Problem B
Assume that we are trying to build a RISC-V processor. For the reference purpose, there are two 5 stage (IF, DEC, EXE, MEM, WB) bypassing processors. However, they are a little broken. The processors are as follows:

Processor 1: A defective 5 stage bypassing processor which does not annul instructions following branches.
Processor 2: A defective 5 stage bypassing processor that reads all values bypassed back as 0 but reads correctly from the register file.

Known properties:

Both processors always predict that branches are not taken (they always fetch from PC + 4).
Both processors determine the direction of the branch in the EXE stage.

We try this simple RISC-V looping code on both of these processors. Assume at the start of the code that x2 is set to some number greater than 0 and that all the other registers are set to 0.

L1: addi x1, x2, -4
    bnez x1, L1
    slli x3, x1, 1
    lw x2, 0x100(x0)
. = 0x100
    .word 0x4

1. If we had a fully working 5 stage bypassing processor, which always fetches from PC + 4 and annuls instructions following taken branches, how many cycles would it take for one iteration of the loop? Assume that the bnez is taken. Provide the number of cycles per loop iteration.

- B01 = 4

### 📝 Annotate
:::info
Under normal conditions, the bnez will flush the instruction in EXE and DEC stage and replace it with NOP


:::

2. If we pass the number 0x10 into x2, by the time the second iteration’s addi reaches EXE, what value will be passed to x1 for each of the two defective processors? If the loop does not make it to a second iteration’s addi, write N/A.

- B02 = 0

### 📝 Annotate
:::info
In processor 1, as the instructions following bnez will not be replaced with NOP, the cycle will continue without jumping to the start of the loop.

Tthe slli and lw instructions are not annulled thus x2 = 4 in the second iteration of the loop and the addi then sets x1 = x2 – 4 = 0.

:::

- B03 = N/A
### 📝 Annotate
In processor 2, on the first iteration of the loop the ```bnez``` reads the bypassed value of ```x1``` which is incorrectly bypassed back as a ```0``` so it immediately exits the loop and never gets to the second iteration


addi x1, x2, -4
bnez x1, L1 <-- x1 is read as 0 when exec

## Problem C
Since having full bypassing can be very costly, we attempt to reorder the instructions in this loop so that we can minimize the total number of cycles per loop iteration while using a single bypass path.

loop:
    slli a4, a3,5
    or a5, a0, a7
    xor a3, a4, a2
    add a1, a2, a3
    sub a6, a5, a2
    blt a6, a2, loop

We can change the order of the instructions in the program as long as it does not change the final result. In what order would you execute the 6 instructions in the loop so that you only need a single bypass path?

1. Here, we select EXE → DEC bypass path. Please list the opcodes in order of execution: __ C01 __ (split in comma)

Acceptable Answers:
- slli, xor, add, or, sub, blt
- or, slli, xor, add, sub, blt
- or, sub, slli, xor, add, blt

### 📝 Annotate
:::info
Let say we have the EXE → DEC bypass path. That means for any operations that involve arithmetic can follow each other during execution as soon as it did not change the execution sequence that involve registers that has been edited in the previous instructions.

Hence, any sequence that satisfy the followings should be correct.

slli → xor
or → sub
xor → add
sub → blt

:::

2. Now, suppose we are offered another processor. This processor is identical to the processor used above with full bypassing, except that it can make branch decisions in the decode stage rather than the execute stage. The disadvantage is that this increases the clock period from 400 ps (before) to 450 ps (with the branch calculated in decode).

Which processor is faster (old: branch decision in EXE and tCLK = 400ps, new: branch decision in DEC and tCLK = 450ps)? __ C02 __

- C02 = new

### 📝 Annotate
:::info
The number of cycle count reduced from 8 to 7 as the ```blt``` instruction is being done in one stage eariler in the new processor.

Old: 8 (400 ps) = 8 * 400 = 3200 ps to execute the loop.
New: 7 (450 ps) = 7 * 450 = 3150 ps to execute the loop.
Thus, new is faster.
:::

## Problem D
Consider the following C code:

int price[6] = {7, 5, 8, 10, 15, 7};
int maximum = 10, c = 3, t = 5;
for (int i = 0; i < 6; i++) {
   if (price[i] > maximum)
       maximum = price[i];
}
int total_cost = maximum + c + t;

Then, the translated RISC-V assembly:

// x4 = 0x24 - length of price in bytes
// x5 = 0x3 - c
// x6 = 0x5 - t
// x7 = 0xA - maximum
// x1 = 0x400 - address of price[0]
start: addi x2, x0, 0
       slli x2, x2, 2
loop:  add x8, x2, x1
       lw x3, 0(x8)
       bge x7, x3, skip
       mv x7, x3
       ori x7, x7, 0
skip:  addi x2, x2, 4
       blt x2, x4, loop
       add x7, x7, x5
       add x7, x7, x6

Assume the registers are initialized to the values specified in the assembly code comments.

In the following five-stage pipelined RISC-V
processor (IF, DEC, EXE, MEM, WB):

- All branches are predicted not-taken. (Always fetch from PC + 4).
- Branch decisions are made in the EXE stage.
- The pipeline has full bypassing.
- The processor annuls instructions following taken branches.
- Assume that in the first iteration of the loop both branches are taken.

1. How many cycles did it take to execute the first loop iteration on this processor? Make sure not to include the first two instructions at label start in your cycle count.

Cycles to execute first iteration of the loop on this processor: __ D01 __

- D01 = 11

### 📝 Annotate
:::info
Following the logic of the instruction, when executing the bge instruction, the register values are as follows.


Hence, it skips to the "skip:" label and end the first loop at cycle 11.


:::
2. If you could modify your fetch stage to always fetch the correct next instruction instead of predicting all branches not taken, how many cycles will it now take to execute the first iteration of the loop on this modified processor? __ D02 __

- D02 = 7

### 📝 Annotate
:::info
There are totally 4 NOP inserted into the pipeline during the execution of first loop. There are inserted after ```bge``` and ```blt``` instruction.

Removes both branch annulments, so the total of 4 cycles can be saved, making the cycles per iteration 11−4=7.
:::
3. Now, let’s change this processor without bypassing. That is, all data hazards are resolved by stalling. How many cycles did it take to execute the first loop on this processor? __ D03 __

- D03 = 24

### 📝 Annotate
:::info
If all data hazards are resolved by stalling, the following pipeline diagram will appears

Without bypasses, there is a 3-cycle penalty for each EXE → DEC bypass used in the bypassed pipeline, and a 1-cycle penalty for every WB → DEC bypass used. In previous question, there were 4 EXE → DEC bypasses and 1 WB → DEC bypass, so cycles=11+4×3+1×1=24.

And it will takes 24 cycles to finish the first loop.
:::

## Problem E
Given the standard RISC-V datapath, determine if the following is implementable or not without any additional functional units? Assume the instruction is not a pseudoinstruction encoding.


1. Consider the new instruction isnull rd, rs1 which check if an input given through rs1 is considered NULL or not by C standard. The result is returned through rd as a bit. Is it Implementable? __ E01 __ (Answer in Yes or No)

- E01 = Yes

2. What changes would you need to make in order for the instruction to be able to execute correctly? Assume all modifications and additions are done on top of the existing single cycle datapath. Select all that apply. __ E02 __ (Anwser in the items and use comma to split)

- a. Modify Branch Comparator logic.
- b. Modify the control signals to the ALU.
- c. Modify the control logic for the Branch Comparator.
- d. Modify ALU buses.
- e. Modify the control logic for WBSel.
- f. Add additional control signals for the writeback mux.
- g. Modify control logic for ALU/ALUSel.
- h. Modify the control logic for parsing instr[31:0].
- i. Add an additional comparator.
- j. None of the above.

- E02 = c,e,h

### 📝 Annotate
:::info

The pipeline needs the following modification in order to support the new instruction.
(Read more over [here](https://inst.eecs.berkeley.edu/~cs61c/sp21/pdfs/exams/Sp21_Final_Solutions.pdf))
:::

3. ```isnull rd, rs1``` is not in a standard RISC-V instruction format; as we are attempting to reduce the number of hardware changes in our datapath. We instead choose to implement our instruction as a pseudoinstruction in the following format. Which of the following statements is true? Assume earlier changes propagate. Select all that apply __ E03 __ (Anwser in the items and use comma to split)

- a. We need to provide a second argument x0 when calling the instruction and modify the control signals
- b. We need to provide a second argument x0 as a comparator for all branch comparisons.
- c. It is impossible to represent as an R-Type instruction
- d. We need to wire x0 as a comparator for all branch comparisons.
- e. We need to wire x0 as rs2 and modify the control signals.

- E03 = e

### 📝 Annotate
:::info
Null is ```\0``` in C which is equal to all 0 in a byte. Hence, to check rs1 is Null, you just need to check if the rs1 bytes are all 0.
:::

## Problem F
Much of the assembly code she writes involves iterating through arrays of integers. Instead of using several instructions to calculate the address of the next element, we propose a new instruction, iarrn rd, rs1, rs2 which places into rd the address of the rs2-th element of the array pointed to by rs1. This instruction does not do bounds checking and it assumes the size of an integer is 4B (32 bits). Do not assume this instruction belongs to a specific type.
In verilog, the instruction is described as follows:

R[rd] = R[rs1] + (4 * R[rs2])

1. We are interested in modifying our RISC-V datapath to support this instruction. Assume we have introduced a new control bit “IArrN” which is 1 when the current instruction is iarrn and 0 otherwise. Using the datapath below, fill in the following table with the rest of the control bits for this instruction. If the control bit can be set to *, please draw an X in the table below.

| IArrN | PCSel | RegWEn | MemRW | WBSel | BrUn | ALUSel |
|:-----:|:-----:|:------:|:-----:|:-----:|:----:|:------:|
| 1 | F01 | F02 | F03 | F04 | F05 | ADD |

- F01 = 0
- F02 = 1
- F03 = 0
- F04 = 1
- F05 = X

### 📝 Annotate
:::info
- ```PCSel``` = 0 because it is executing a non jump / branch instruction
- ```RegWEn``` = 1 because this instruction contain a write target rd
- ```MemRW``` = 0 because it is not writing into the data memory, its result is outputting from ALU instead of Data Memory after the ```4 * R[rs2]``` operation
- ```WBSel``` = 1 because it is writing back to rd from ALU result
- ```BrUn``` = X because this is not a branching operation
:::
2. This instruction involves changing a few hardware pieces on the datapath in addition to changing control bits above. We propose modifying the ASel and BSel muxes, and their associated control bits (circled below).

How should we change ```BSel``` to allow our new instruction, and all other RISC-V instructions, to execute correctly? Select one __ F06 __


- F06 = A

### 📝 Annotate
:::info
By transforming the description to sequential logic block diagram, you can easily spot either A or D is the correct solution as other circuit combination cannot produce the desire output.

:::
3. Following the previous quetion, how should we change ``ASel`` to allow our new instruction, and all other RISC-V instructions, to execute correctly? Select one __ F07 __
![](https://i.imgur.com/jA3t6ZQ.png)

- F07 = A

### 📝 Annotate
:::info
We don't need to change the ```ASel``` for the new instruction. Hence, A is the correct answer.

Notes: The original block diagram's ```rs1``` (0) and ```PC```(1) is flipped upsidedown compare to the one shown in A, but they behave the same.
:::