程序代写代做代考 algorithm Microsoft PowerPoint – Chapter 5 – Analytical Modeling of Parallel Algorithms

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?