Pipelining

Pipelining

implementation technique in which multiple instructions are overlapped in execution

5 steps

1. Fetch instruction from memory
2. Read registers while decoding instruction
3. Execute operation or calculate address
4. Access an operand in data memory


1. Write result into a register

If stages are perfectly balanced, then the time between instructions = ?

(Time between non-pipelined instruction)/(number of pipe stages)

Since stages may be imperfectly balanced, the time per instruction will ____ the minimum possible, and the speed-up will be ____ than the number of pipeline stages.

exceed, less

How does pipelining improve performance?

By increasing instruction throughput

Why is it easier to fetch instructions in first stage and decode them in the second stage?

All MIPS instructions are the same length

Since the source register fields are located in the same place in every instruction, what can happen?

The second stage can begin reading the register file at the same time that the hardware is determining what type of instruction was fetched

We can use the execute stage to calculate the memory address and then access memory in the following stage because of what?

Memory operands only appear in loads or stores

Since operands must be aligned in memory, we don’t have to worry about what?

A single data transfer instruction requiring two data memory accesses

Situations when the next instruction cannot execute in the following clock cycle are called what?

hazards

What is a structural hazard?

The hardware cannot support the combination of instructions that we want to execute in the same clock cycle

When do data hazards occur?

When the pipeline must be stalled because one step must wait for another to finish. Data hazards arise from the dependence of one instruction on an earlier one that is still in the pipeline

One method of resolving data hazards is what?

Forwarding- adding extra hardware to retrieve the missing item early from the internal resources

When are forwarding paths valid?

If the destination stage is later in time than the source stage

What is a load-use data hazard?

When the data being loaded by a load instruction has not yet become available when it is needed by another instruction

A stall initiated to resolve a hazard is called a what?

Pipeline stall/bubble

What type of hazard arises from the need to make a decision based on the results of one instruction while the others are executing?

Control hazard

2 solutions to control hazards?

Stall, predict

What is branch prediction?

assumes a given outcome for the branch and proceeds from that assumption rather than waiting for the actual outcome

What are the 5 stages of instruction execution?

1. Instruction Fetch (IF)
2. Instruction decode and register file read (ID)
3. Execution or address calculation (EX)
4. Data memory access (MEM)
5. Write back (WB)

2 exceptions to left-right flow of instructions

WB- places result back into register file in the middle of the datapath

Selection of next PC value and the branch address from the MEM stage

Do the reverse data movements affect the current instruction?

No, only the later instructions in the pipeline

First right to left can lead to data hazards, what can the second lead to?

Control hazards

What needs to be done to specify control for the pipeline?

Only set control values during each pipeline stage

The control signals to read instruction memory and write PC are always asserted, so there is nothing special to control in which stages?

Instruction fetch and instruction decode/register file read

Which signals need to be set in the Execution/address calculation stage?

RegDst, ALUOp, ALUSrc. The signals select Result register, ALU operation, and Read data 2 or a sign extended immediate for the ALU

The control lines Branch, MemRead, and MemWrite, set by branch equal, load, and store instructions are set in which stage?

Memory Access

What control lines are set in the Write Back stage?

MemToReg (decides between sending ALU result or memory value to the register file) and RegWrite (writes the chosen value)

What is the simplest way to implement control by setting the 9 control lines to the right values in each stage for each instruction?

Extend pipeline registers to include control information

When can we create the control information?

During instruction decode