```Pipelining, Parallelism,
and Simplified Circuits
Discrete Math
April 13, 2006
Harding University
Jonathan White
Outline

What Pipelining is
• Benefits
• Downsides
• How modern processors use Pipelining

Parallelism
• Circuits
• Pros/Cons
Pipelining

Definition:
• Pipelining is an implementation technique
where multiple instructions are overlapped in
execution on a processor.


Each stage completes part of an
instruction in parallel.
The stages are connected one to the next
to form a pipe - instructions enter at one
end, progress through the stages, and exit
at the other end.
Pipelining Laundry Example

4 loads of laundry that need to
washed, dried, and folded.
• 30 minutes to wash, 40 min. to dry, and
20 min. to fold.
• We have 1 washer, 1 dryer, and 1
folding station.

What’s the most efficient way to get
the 4 loads of laundry done?
Non Pipelined Laundry

Wash, dry, fold.
• Then wash, dry, fold.


Then wash, dry fold….
Takes a total of 6 hours; nothing is done
in parallel
Pipelined Laundry

A better idea would be start the next load
washing while the first is drying.
• Then, while the first load was being folded, the
put in the washer.

Using this method, the laundry would be
done at 9:30.
Processors

Computers, like laundry, typically
perform the exact same steps for
every instruction:
• Fetch an instruction from memory
• Decode the instruction
• Execute the instruction
• Read memory to get input
• Write the result back to memory
Example of a Basic Non-Pipelined
Instruction
Example of a Pipelined Architecture
Pipelining Aspects

The length of the longest step
dictates the length of the pipeline
stages.
• So, the slowest resource affects the
entire process.


What’s the slowest process in a processor’s
5 steps?
Pipelining improves performance by
increasing instruction throughput, as
opposed to decreasing the execution
time of any individual instruction.
Pipeline Video
Pipelining Benefits

For the right instruction language,
pipelining increases performance linearly
with the number of pipeline stages.
• Languages are designed to be pipelined now.

RISC
vs
CISC architectures
• Pipelining is easy to do with only a few

Pipelining makes efficient use of
resources.
• Circuits consume similar amounts of power
whether performing calculations or just
waiting.
Pipelining Downsides

• Every instruction must be able to be performed in each
of the stages

ie, some instruction require the ALU in more than one step.
• Registers to hold data between cycles
• More ALU’s are required.

For example, 1 ALU is needed just to increase the program
counter.
• Branch prediction and collision avoidance units are
required.

Often times, you will have to clear the pipeline
when you’ve written code that causes a hazard.
• X = Y +4
• Z=X+1
Branch Prediction

How many times will this loop execute?
• for(int x = 0; x<100; x++)
{
do something….
}
It would be nice for the processor to be able to predict that
this code will be executed more than once…
Some modern processors just assume
branch will never be taken.
Also, compilers will often do out of order
execution of commands to avoid stalling the
pipe.
More benefits of Pipelining

The parallelism is invisible to the
programmer.
Modern processors

Pentium 4’s have a 30 stage pipeline.
• If the pipeline gets too large, there is too much
overhead (flushing 300 stages is easier than
30).

However, new processors like the CELL
processor in the Playstation 3 are moving
to multicore architectures.
• The pipeline is much smaller; between 5 and
10.
• Multicore processors work best for applications
that run a lot of threaded applications that are
easily seperable.
Other Levels of Parallelism

• Way for an application to split itself into
• MS Word

Logic circuits
• These are naturally parallel
Pros of Parallelism

The average throughput is greatly
increased.
• Very little time is wasted.

A lot of things are naturally parallel.
Cons of Parallelism

• More power, more components
• For threaded computer programs, either the
kernel or your program must do some work to

At some point, more parallelism actually
makes things slower.
• You spend too much time switching between
```