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