Microsoft PowerPoint – Chapter 5 – Analytical Modeling of Parallel Algorithms
Introduction to
Parallel Computing
George Karypis
Analytical Modeling of Parallel
Algorithms
Sources of Overhead in Parallel
Programs
The total time spent by a parallel
system is usually higher than that
spent by a serial system to solve
the same problem.
Overheads!
Interprocessor Communication &
Interactions
Idling
Load imbalance,
Synchronization, Serial
components
Excess Computation
Sub-optimal serial algorithm
More aggregate computations
Goal is to minimize these
overheads!
Performance Metrics
Parallel Execution Time
Time spent to solve a problem on p
processors.
Tp
Total Overhead Function
To = pTp – Ts
Speedup
S = Ts/Tp
Can we have superlinear speedup?
exploratory computations, hardware
features
Efficiency
E = S/p
Cost
p Tp (processor-time product)
Cost-optimal formulation
Working example: Adding n elements on
n processors.
Effect of Granularity on
Performance
Scaling down the number of processors
Achieving cost optimality
Naïve emulations vs Intelligent scaling
down
adding n elements on p processors
Scaling Down by Emulation
Intelligent Scaling Down
Scalability of a Parallel System
The need to predict the
performance of a parallel algorithm
as p increases
Characteristics of the To function
Linear on the number of
processors
serial components
Dependence on Ts
usually sub-linear
Efficiency drops as we increase
the number of processors and
keep the size of the problem fixed
Efficiency increases as we
increase the size of the problem
and keep the number of
processors fixed
Scalable Formulations
A parallel formulation is called scalable if
we can maintain the efficiency constant
when increasing p by increasing the size
of the problem
Scalability and cost-optimality are related
Which system is more scalable?
Measuring Scalability
What is the problem size?
Isoefficiency function
measures the rate by which the problem size
has to increase in relation to p
Algorithms that require the problem size to
grow at a lower rate are more scalable
Isoefficiency and cost-optimality
What is the best we can do in terms of
isoefficiency?