Try   HackMD

Quiz4 of Computer Architecture (2020 Fall)

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 (tPD = 0, tSETUP = 0). Remember that our convention is to place a pipeline register on each output.

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

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

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

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

C3422

tCLK = 3 + 4 + 2 + 2 = 11 ns
A01 = 11 ns
A02 =
111
ns

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

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

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

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

A03 = 14
A04 =
17

tCLK = 3 + 4 = 7 ns
latency = 2 * 7 = 14 ns

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

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

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

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

A05 = 12
A06 =
14

tCLK = 4 ns
latency = 3 * 4 = 12 ns

(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.

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

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

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

A07 = 12
A08 =
13

tCLK = 3 ns
latency = 4 * 3 = 12 ns


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 (tPD = 0, tSETUP = 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.

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

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

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

B01 = 12
B02 =
14

tCLK = 4 ns
latency = 3 * 4 = 12 ns

(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.

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

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

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

B03 = 9
B04 =
13

tCLK = 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 (tPD = 0, tSETUP = 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?

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

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

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

C01 = 20
C02 =
110

tCLK = 6 + 4 = 10 ns
latency = 2 * 10 = 20 ns

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

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

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

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

C03 = 24
C04 =
16

tCLK = 6 ns
latency = 4 * 6 = 24 ns


Question D

Consider the below 5-Stage Pipeline processor.

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

(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.


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.

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →
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.
Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

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.