# Quiz4 of Computer Architecture (2020 Fall)
:::info
:information_source: General Information
* You are allowed to read [lecture materials](http://wiki.csie.ncku.edu.tw/arch/schedule).
* That is, an open book exam.
* You shall not disclose your answer during the quiz.
* Each answer has **3 points**.
* :timer_clock: 09:10 ~ 10:20AM on Nov 17, 2020
:::
## Question `A`
For each of the questions below, create a valid [N-stage pipeline](https://en.wikipedia.org/wiki/Instruction_pipelining) of the given circuit. Each component in the circuit is annotated with its [propagation delay](https://en.wikipedia.org/wiki/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 __
> * A01 = ?
> * A02 = ?
(2) Show the maximum-throughput 2-stage pipeline using a minimal number of registers.
Latency (ns): __ A03 __
Throughput (ns^-1^): __ A04 __
> * A03 = ?
> * A04 = ?
(3) Show the maximum-throughput pipeline using a minimal number of registers.
Latency (ns): __ A05 __
Throughput (ns^-1^): __ A06 __
> * A05 = ?
> * A06 = ?
(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 = ?
> * A08 = ?
---
## Question `B`
For each of the questions below, create a valid [N-stage pipeline](https://en.wikipedia.org/wiki/Instruction_pipelining) of the given circuit. Each component in the circuit is annotated with its [propagation delay](https://en.wikipedia.org/wiki/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 = ?
> * B02 = ?
(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 + 1 ns, 2 ns + 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. Your solution should use the minimum possible number of pipeline stages.
Latency (ns): __ B03 __
Throughput (ns^-1^): __ B04 __
> * B03 = ?
> * B04 = ?
---
## Question `C`
For each of the questions below, create a valid [N-stage pipeline](https://en.wikipedia.org/wiki/Instruction_pipelining) of the given circuit. Each component in the circuit is annotated with its [propagation delay](https://en.wikipedia.org/wiki/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 = ?
> * C02 = ?
(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 = ?
> * C04 = ?
---
## Question `D`
Consider the below 5-Stage Pipeline processor.
(1) Even a simple [in-order](https://en.wikipedia.org/wiki/Out-of-order_execution#In-order_processors) pipelined processor would make use of [speculative execution](https://en.wikipedia.org/wiki/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 specify the cycles in which the second add is being executed speculatively. For example, if one stage F is being executed speculatively, use the notation `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 = ?
> * D02 = ?
> * D03 = ?
> * D04 = ?
> * D05 = ?
> * D06 = ?
> * D07 = ?
> * D08 = ?
> * D09 = ?
> * D10 = ?
(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 = ?
---
## 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**?
```c
loop: lw x10, 0x100(x0)
beqz x10, loop
add x12, x10, x11
sub x13, x12, x1
```
Number of cycles per loop iteration: __ E01 __
> * E01 = ?
(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 = ?
(3) 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?
Number of cycles per loop iteration on processor P3: __ E03 __
> * E03 = ?
---
## 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](https://en.wikipedia.org/wiki/Classic_RISC_pipeline#Solution_A._Bypassing), annulment of instructions in branch delay slots, or pipeline stalls.
```c
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 code snip on above is a sample of the program to be converted. It does not 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 snip 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 = ?
> * F02 = ?
> * F03 = ?
> * F04 = ?
(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 = ?
---
## Question `G`
The following programs are being executed on the 5-stage pipelined RISC-V processor with full [bypassing](https://en.wikipedia.org/wiki/Classic_RISC_pipeline#Solution_A._Bypassing). For each code listing, the pipeline diagram shows the state of the pipeline for cycle `1000` of execution. Please fill in the diagram for cycle `1001`; use `UNKNOWN` if you cannot tell what opcode to write into a stage.
(1) Program below
```c
...
sw x1, 0(x0)
lw x17, 0xC(x1)
addi x2, x2, -4
slli x11, x17, 2
sw x11, 0(x2)
jal ra, factorial
...
```
| Cycle | 1000 | 1001 |
| ----- | ---- | ---- |
| IF | `sw` | G01 |
| ID | `slli` | G02 |
| IE | `addi` | G03 |
| MEM | `lw` | G04 |
| WB | `sw` | G05 |
> * G01 = ?
> * G02 = ?
> * G03 = ?
> * G04 = ?
> * G05 = ?
(2) Program below
```c
...
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 = ?
> * G07 = ?
> * G08 = ?
> * G09 = ?
> * G10 = ?
---
Sign in with Wallet
Connect another wallet