# Pipelining

Next: Branch Prediction

Pipelining is like a car assembly line. In a car assembly line, there are many people working at the same time, but they are not all working on the same car. Each person is working on a different car. Assume there are four stations for working on a car: put in engine, put on doors and hood, put on wheels, and paint car. Also assume that each station takes 5 minutes to complete its action. Each car has to go through each station.
 Time Engine Doors Wheels Paint 5 min Car 1 10 min Car 1 15 min Car 1 20 min Car 1
Suppose there was only one person working on the assembly line. Then this person would have to do the work at all the stations. The person would move along with the car to each new station. In this case, it would take 20 minutes to complete one car.
 Time Engine Doors Wheels Paint 5 min Car 1 10 min Car 1 15 min Car 1 20 min Car 1 25 min Car 2 30 min Car 2 35 min Car 2 40 min Car 2
Again, suppose there is only one person making cars, but now there are two cars to be made, then it would take 40 minutes to complete 2 cars. When the first car was finished, the worker would have to walk back to the start of the assembly line to start work on the second car. If there were 4 cars, then it would take 80 minutes to complete them. If someone were looking at the output of the assembly line, they would see a car produced avery 20 minutes.
 Time Engine Doors Wheels Paint 5 min Car 1 10 min Car 2 Car 1 15 min Car 3 Car 2 Car 1 20 min Car 4 Car 3 Car 2 Car 1 25 min Car 4 Car 3 Car 2 30 min Car 4 Car 3 35 min Car 4
Now, suppose there are four people working on the assembly line, one at each station. As soon as a car is done at one station, it moves to the next station. For instance, once a car is done at the Engine station, it moves to the Doors station. This allows the next car to move into the Engine station. Because each station can work on a different car, it is possible to be working on four cars at the same time. It still takes 20 minutes to complete a car. However, if someone is observing the output of the assembly line, it would appear that the first car takes 20 minutes, but then each succeeding car would only takes 5 minutes to complete. It would take only 35 minutes to complete 4 cars.

An instruction pipeline works the same way. Each station in the pipeline represents a different step in the fetch-decode-execute cycle. As a simple example, assume there are only 4 stages in the pipeline (the Pentium II has a 12 stage pipeline): Fetch, Decode, Execute, Save.
 Cycles Fetch Decode Execute Save 1 Inst 1 2 Inst 2 Inst 1 3 Inst 3 Inst 2 Inst 1 4 Inst 4 Inst 3 Inst 2 Inst 1 5 Inst 4 Inst 3 Inst 2 6 Inst 4 Inst 3 7 Inst 4
As each instruction is completed at one stage, it moves to the next stage. Then a new instruction is started. Each instruction takes 4 cycles to complete. However, it appears that the first instruction takes 4 cycles to complete, but that all subsequent instructions take 1 cycle to complete. The overall time to execute all these instructions is 7 cycles. Without a pipeline, it would take 28 cycles to complete theses four instructions.

Next: Branch Prediction