Overview of Pipelining
Notes
- This begins chapter 4.5 of the book.
- Pipelining is, in some real sense, using all of the parts of the CPU all of the time
- P&H state "Today pipelining is nearly universal."
- For our discussion we will use the division of the CPU into a 5 stage pipeline
- IF
- ID
- EX
- MEM
- WB
- In doing this we can
- Shorten the clock cycle to the length of the longest sub-unit time
- Utilize the entire CPU more completely
- Our goal is a CPI of one, with a much shorter clock cycle.
- We may not achieve this completely, but we will be fairly close.
- For a clock cycle of n, each instruction will still take 5n to complete.
- But we will complete an instruction every cycle
- The single cycle clock length will take just a bit longer
- We will add "pipeline latches" to store the data between pipeline sections
- And we will need some additional logic to accomplish other tasks.
- But we should come close to a speed up of 5.
- To understand pipelining and the problems we need a new tool
- Pipeline diagrams
- Show three items:
- time: usually in ps
- instruction: sometimes the instruction (load, store, ...) , sometimes an abstraction of the instruction (I0, I1)
- We will at some times go into real detail.
- pipeline stage: IF, ID, EX, MEM, WB
- Two of these will constitute the axis, the third will be the data in the chart.
- Which you pick depends on what you want to see
- Show three items:
- Time vs Instruction with stage as data
- Flow of instructions through a non-pipelined machine.
- Note in P&H they shorten ID and WB to be 100ps each.
- I don't like the time, I might just use Time (T1, T2...)
- For an idealized pipeline we might have
T1 T2 T3 T4 T5 T6 T7 I0 IF ID EX MEM WB I1 IF ID EX ALU WB I3 IF ID EX ALU WB I4 IF ID EX ALU - We will discuss this later, but for this to work, WB finishes in the first 1/2 of the cycle and Register File Access occurs in the second half, after WB.
0-200 200-400 400-600 600-800 800-1000 1000-1200 1200-1400 I0 IF ID EX MEM WB I1 IF ID - While P&H seem to use this format, I find the others useful as well
- Note
- The single instruction time could be reduced to 800ps if ID and WB both take 100ps
- But this can not happen in the pipeline
- So we would not have perfect speedup
- Single instruction 1,000 instructions x 800ps = 800,000 ps total
- 5 Stage Pipeline (1,000 + 4) pipeline stages x 200ps = 200,800
- Roughly a speedup of 4.
- But is it all this rosy?
- Well no, not it isn't
- A hazard occurs when the instructions in the pipeline interfere with each other.
- A structural hazard occurs when two instructions need the same hardware
- Different instruction and data memory is one example.
- Adders for the pc, vs using the ALU to do this is another
- Reading/Writing to the Register file:
- Accessing the register file is fairly fast.
- So we assume WB occurs in the first half of the cycle
- And Register File Read occurs in the second half.
- For the most part, we can build an architecture to avoid structural hazards.
- A data hazard occurs when the data an instruction needs is not available because another instruction has not yet produced it.
- Consider
I0: load r1, xxx I1: add r2, r1, xxx - When I1 needs the value for R1, (ID), I0 will still be in EX.
- An easy solution is to insert a bubble in the pipeline until the data is available.
- But there are more complex, but better solutions.
- Consider
- Finally a control hazard occurs when we take conditional branches
- We will have fetched 2-4 instructions before we know this.
- An easy approach is to insert bubbles into the pipeline.
- But there are more complex, but better solutions.