Processor Pipelines

Question 1

Draw the CPU overview focusing on the data path

Answer 1

.

Question 2

? between stages keep the processes in different stages

Answer 2

Registers

Question 2

How is the address for the memory access generated?

Answer 2

From rs1 and immediate

Question 3

Which register holds data for the store?

Answer 3

rs2

Question 4

Why is it quicker to do things later and then decide if we need the result?

Answer 4

Because hardware is parallel

Question 5

Add control logic to the data path diagram

Answer 5

.

Question 6

What does the branch unit do?

Answer 6

Generates next PC value. If there is no branching just adds 4 to PC

Question 7

What does the mux after register file access do?

Answer 7

Selects either immediate or rf[rs2] as the second operator

Question 8

Why do we need a jump and link instruction?

Answer 8

Because we can’t specify a 32 bit immediate and instruction in 32 bits

Question 9

How does a store instruction work?

Answer 9

Starts out like an I-type instruction and does the address calculations: read register operands, calculate address rf[rs1] + sign_extended_immediate
Write register rf[rs2] value to this location in memory

Question 10

How does a load instruction work?

Answer 10

Starts out like an I-type instruction and does the address calculations: read register operands, calculate address rf[rs1] + sign_extended_immediate
Read memory and update destination register rf[rd]

Question 11

Draw the part of the data path corresponding to load/store instructions

Answer 11

.

Question 12

Draw the part of the data path corresponding to R-type instructions

Answer 12

.

Question 13

Draw the part of the data path corresponding to I-type instructions

Answer 13

.

Question 14

What happens with branch instructions?

Answer 14

1. Read register operands
2. Compare operands
   Use ALU, subtract and check outputs
3. Calculate target address
   Sign-extend displacement, shift left 1 place, add to PC value

Question 15

What is the data path?

Answer 15

Made up of elements that process data and addresses. Data flows through this path, with some of the data coming from the instruction. Fixed

Question 16

What is the control path?

Answer 16

Control path signals are determined by the instruction and other microarchitectural state (eg. result of ALU operation is zero or negative). Determines how each part of ther data path is used to perform each instruction

Question 17

Highlight the influence of control for R-type instructions on the data and control path diagram

Answer 17

.

Question 18

Highlight the influence of control for I-type arithmetic instructions on the data and control path diagram

Answer 18

.

Question 19

Highlight the influence of control for I-type load instructions on the data and control path diagram

Answer 19

.

Question 20

Highlight the influence of control for S-type store instructions on the data and control path diagram

Answer 20

.

Question 21

Highlight the influence of control for B-type instructions on the data and control path diagram

Answer 21

.

Question 22

List 3 performance issues with with the processor pipeline

Answer 22

1. Longest delay determines clock period
   Critical path = load instruction
   Instruction memory -> register file -> ALU -> data memory -> register file
2. Not feasible to very period for different instructions
3. Violates the design principle of making the common case fast

Question 23

What is the critical path through the processor pipeline?

Answer 23

Load instruction
Instruction memory -> register file -> ALU -> data memory -> register file

Question 24

Why do we need pipelining?

Answer 24

To overcome the 3 performance issues with the processor pipeline

Question 25

If we execute 1 instruction every x seconds, what improvement do we get if we use pipelining?

Answer 25

1 instruction every x/s seconds s = number of seconds

Question 26

List the 5 stages of the RISC-V processor pipeline

Answer 26

1. IF: instruction fetch 2. ID: instruction decode 3. EX: execute operation 4. MEM: memory access 5. WB: write back result to register

Question 27

What type of pipeline is the RISC-V pipeline?

Answer 27

Scalar pipeline Simple linear pipeline that fetches one instruction at a time and sends it down the pipeline to be executed

Question 28

How can we know we will always read updated data?

Answer 28

Can write registers in the first half of the clock cycle and read registers in the second half

Question 29

Draw a diagram of program execution order against time to show how pipelining improves performance for these instructions: ld x1, 100(x4) ld x2, 200(x4) ld x3, 300(x4)

Answer 29

.

Question 30

Assuming stages are balanced, give the equation for pipeline speedup

Answer 30

Time between instructions pipelined = time between instructions non-pipelined/number of stages So the speedup is near linear if the pipeline doesn't stall

Question 31

If stages are not balanced, is speedup more or less?

Answer 31

Less

Question 32

Does pipelining affect latency?

Answer 32

No, it does not decrease latency. Speedup is due to increased throughput

Question 33

What is latency?

Answer 33

Time for each instruction

Question 34

In which 3 ways is RISC-V ISA designed for pipelining?

Answer 34

1. All instructions are 32 bits Easier to fetch and decode in one cycle 2. Few and regular instruction formats Can decode and read registers in one step 3. Load/store addressing Can calculate address in 3rd stage, access memory in 4th stage

Question 35

List the 3 types of hazard

Answer 35

1. Structural hazard 2. Data hazard 3. Control hazard

Question 36

What is a hazard?

Answer 36

Situations that prevent starting the next instruction in the next cycle

Question 37

What is a structural hazard?

Answer 37

A required resource is busy This is a problem in a pipeline with a single memory. Load/store requires memory access, so does instruction fetch so it would have to stall for that cycle causing a pipeline bubble

Question 38

Give an example of a structural hazard

Answer 38

Can't do fetch and memory access at the same time in 1 memory

Question 39

How can we overcome structural hazards?

Answer 39

Pipelined paths need separate instructions/data memories so use separate instruction and data caches

Question 40

What is a data hazard?

Answer 40

An instruction depends on completion of data read/write by a previous instruction, so has to wait until this instruction has written back

Question 41

What is forwarding/bypassing?

Answer 41

Don't wait for result to be written back to the register file, use result when it is computed. Forwarded from write back directly to execute (back to the ALU)

Question 42

What is a load-use data hazard?

Answer 42

Stalls cannot always be avoided by forwarding, if the value hasn't been computed when needed Eg. load instruction need to load from memory, so even with data forwarding the next instruction will need to stall for one clock cycle

Question 43

Draw a diagram of program instruction order against time to show a load-use data hazard

Answer 43

.

Question 44

How can load-use data hazards be overcome?

Answer 44

Using code scheduling. Reorder code to avoid use of load result in the next instruction

Question 45

What is a control hazard?

Answer 45

Branch determines the flow of control. Fetching the next instruction depends on branch outcome so pipeline cannot always fetch the correct instruction because it is still working on ID stage of branch

Question 46

When can unconditional jumps happen in a RISC-V pipeline?

Answer 46

ID stage

Question 47

When can conditional branches happen in a RISC-V pipeline?

Answer 47

They are dependant on register comparisons typically done in the EX stage

Question 48

What is an indirect jump and when can it be handled?

Answer 48

Jumps to an address in a register, handled in EX stage

Question 49

What is a stall on branch?

Answer 49

Wait until branch outcome determined before fetching next instruction

Question 50

Draw a diagram of program instruction order against time to show a stall on branch

Answer 50

.

Question 51

What is branch prediction?

Answer 51

Predict the outcome of the branch. Only stall if prediction is wrong. If wrong, state must be cleaned up to preserve sequential execution model

Question 52

State the 2 types of branch prediction

Answer 52

1. Static 2. Dynamic

Question 53

Why do we need branch prediction?

Answer 53

To stall on branch in longer pipelines causes an unacceptable stall penalty

Question 54

What is static branch prediction? Give an example

Answer 54

Based on typical branch prediction Eg. Loop and if statement branches which predict backwards branches taken and forward branches not taken

Question 55

What is dynamic branch prediction?

Answer 55

Hardware measures actual branch behaviour and assume future behaviour will continue the trend