Solutions
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.
Latency (ns): __ A01 __
Throughput (ns-1): __ A02 __
tCLK = 3 + 4 + 2 + 2 = 11 ns
A01 = 11 ns
A02 = ns
(2) Show the maximum-throughput 2-stage pipeline using a minimal number of registers.
Latency (ns): __ A03 __
Throughput (ns-1): __ A04 __
A03 = 14
A04 =
tCLK = 3 + 4 = 7 ns
latency = 2 * 7 = 14 ns
(3) Show the maximum-throughput pipeline using a minimal number of registers.
Latency (ns): __ A05 __
Throughput (ns-1): __ A06 __
A05 = 12
A06 =
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.
Latency (ns): __ A07 __
Throughput (ns-1): __ A08 __
A07 = 12
A08 =
tCLK = 3 ns
latency = 4 * 3 = 12 ns
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.
Latency (ns): __ B01 __
Throughput (ns-1): __ B02 __
B01 = 12
B02 =
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.
Latency (ns): __ B03 __
Throughput (ns-1): __ B04 __
B03 = 9
B04 =
tCLK = 3 ns
latency = 3 * 3 = 9 ns
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?
Latency (ns): __ C01 __
Throughput (ns-1): __ C02 __
C01 = 20
C02 =
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?
Latency (ns): __ C03 __
Throughput (ns-1): __ C04 __
C03 = 24
C04 =
tCLK = 6 ns
latency = 4 * 6 = 24 ns
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.
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)?
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
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.
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.
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
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 aNOP
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.
(2) Program
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 = slliFor 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
andx13
. 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 ofx13
is set by the sub instruction which is currently in the EXE stage. Similarly, the value forx11
needs to be bypassed from the WB stage since it is set by thexor
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 asw
instruction. Theadd
instruction is now being decoded and requires the values inx12
andx13
. These were modified by theand
andsub
instructions, so we need to bypass from the EXE and MEM stages.