CSC 334 – Parallel and Distributed Computing

Instructor: Dr. M. Hasan Jamal

Lecture# 04: Designing Parallel Programs

1
Agenda
• Automatic vs. Manual Parallelization
• Understand the Problem and the Program
• Partitioning
• Communications
• Synchronization
• Data Dependencies
• Load Balancing
• Granularity
• I/O
• Performance Analysis and Tuning
• Limits and Costs of Parallel Programming 2
Automatic vs. Manual Parallelization
• Designing and developing parallel programs has characteristically been a very
manual process. The programmer is typically responsible for both identifying
and actually implementing parallelism.

• Very often, manually developing parallel codes is a time consuming, complex,

error-prone and iterative process.

• Various tools have been available over the years to assist the programmer with
converting serial programs into parallel programs. The most common type of
tool used to automatically parallelize a serial program is a parallelizing compiler
or pre-processor.
3
Automatic vs. Manual Parallelization
• A parallelizing compiler generally works in two different ways:
• Fully Automatic
• The compiler analyzes the source code and identifies opportunities for parallelism.
• The analysis includes identifying inhibitors to parallelism and possibly a cost weighting on
whether or not the parallelism would actually improve performance.
• Loops (do, for) loops are the most frequent target for automatic parallelization.
• Programmer Directed
• Using "compiler directives" or possibly compiler flags, the programmer explicitly tells the
compiler how to parallelize the code.
• May be able to be used in conjunction with some degree of automatic parallelization also.
• The most common compiler generated parallelization is done using on-node shared
memory and threads (such as OpenMP).

4
Automatic vs. Manual Parallelization
• If you are beginning with an existing serial code and have time or budget
constraints, then automatic parallelization may be the answer. However, there
are several important caveats that apply to automatic parallelization:
• Wrong results may be produced
• Performance may actually degrade
• Much less flexible than manual parallelization
• Limited to a subset (mostly loops) of code
• May actually not parallelize code if the analysis suggests there are inhibitors, or the
code is too complex
• Most automatic parallelization tools are for Fortran

• The remainder of the lecture applies to the manual method of developing

5
parallel codes.
Understand the Problem and the Program
• Undoubtedly, the first step in developing parallel software is to first understand
the problem that you wish to solve in parallel. If you are starting with a serial
program, this necessitates understanding the existing code also.

• Before spending time in an attempt to develop a parallel solution for a problem,

determine whether or not the problem is one that can actually be parallelized.

6
Understand the Problem and the Program
• Example of Parallelizable Problem: Calculate the potential energy for each of
several thousand independent conformations of a molecule. When done, find
the minimum energy conformation.

• Solution: This problem is able to be solved in parallel. Each of the molecular

conformations is independently determinable. The calculation of the minimum
energy conformation is also a parallelizable problem.

• Example of Non-Parallelizable Problem: Calculation of the Fibonacci series

(1,1,2,3,5,8,13,21,...) by use of the formula: 𝐹 𝑘 + 2 = 𝐹 𝑘 + 1 + 𝐹(𝑘)

• Solution: This is a non-parallelizable problem because the calculation of the

Fibonacci sequence as shown would entail dependent calculations rather than
independent ones. The calculation of the 𝑘 + 2 value uses those of both 𝑘 + 1 7
and 𝑘. These three terms cannot be calculated independently and therefore, not
in parallel.
Understand the Problem and the Program
• Identify the program’s hotspots
• Know where most of the real work is being done. The majority of scientific and technical
programs usually accomplish most of their work in a few places.
• Profilers and performance analysis tools can help here.
• Focus on parallelizing the hotspots and ignore those sections of the program that account
for little CPU usage.
• Identify bottlenecks in the program
• Are there areas that are disproportionately slow, or cause parallelizable work to halt or be
deferred? For example, I/O is usually something that slows a program down.
• May be possible to restructure the program or use a different algorithm to reduce or
eliminate unnecessary slow areas.
• Identify inhibitors to parallelism. One common class of inhibitor is data dependence,
as demonstrated by the Fibonacci sequence above.
8
• Investigate other algorithms if possible. This may be the single most important
consideration when designing a parallel application.
Partitioning
• One of the first steps in designing a parallel program is to break the problem
into discrete "chunks" of work that can be distributed to multiple tasks. This is
known as decomposition or partitioning.

• There are two basic ways to partition computational work among parallel tasks:
• Domain Decomposition
• Functional Decomposition

9
Partitioning
• Domain Decomposition: In this type of partitioning, the data associated with a
problem is decomposed. Each parallel task then works on a portion of the data.

• There are different ways to partition data

10
Partitioning
• Functional Decomposition: In this approach, the focus is on the computation
that is to be performed rather than on the data manipulated by the
computation. The problem is decomposed according to the work that must be
done. Each task then performs a portion of the overall work.

• Functional decomposition lends itself well to problems that can be split into
different tasks. For example:
• Ecosystem Modeling
• Signal Processing
• Climate Modeling

11
Partitioning
• Ecosystem Modeling Example: Each program calculates the population of a
given group, where each group's growth depends on that of its neighbors. As
time progresses, each process calculates its current state, then exchanges
information with the neighbor populations. All tasks then progress to calculate
the state at the next time step.

12
Partitioning
• Signal Processing Example: An audio signal data set is passed through four
distinct computational filters. Each filter is a separate process. The first segment
of data must pass through the first filter before progressing to the second. When
it does, the second segment of data passes through the first filter. By the time,
the fourth segment of data is in the first filter, all four tasks are busy.

13
Partitioning
• Climate Modeling Example: Each model
component can be thought of as a
separate task. Arrows represent
exchanges of data between components
during computation: the atmosphere
model generates wind velocity data that
are used by the ocean model, the ocean
model generates sea surface
temperature data that are used by the
atmosphere model, and so on.

• Combining these two types of problem

decomposition is common and natural.
14
Who Needs Communications?
• The need for communications between tasks depends upon your problem

• You DON’T need communications

• Some types of problems can be decomposed
and executed in parallel with virtually no need
for tasks to share data. These types of
problems are often called embarrassingly
parallel as little, or no communication is
required.
• For example, imagine an image processing
operation where every pixel in a black and
white image needs to have its color reversed.
The image data can easily be distributed to
15
multiple tasks that then act independently of
each other to do their portion of the work.
Who Needs Communications?
• You DO need communications
• Most parallel applications are not quite so
simple and do require tasks to share data
with each other.
• For example, a 2-D heat diffusion problem
requires a task to know the temperatures
calculated by the tasks that have neighboring
data. Changes to neighboring data has a
direct effect on that task's data.

16
Factors to Consider (1)
• There are several important factors to consider when designing your program's
inter-task communications

• Cost of Communications:
• Inter-task communication virtually always implies overhead.
• Machine cycles and resources that could be used for computation are instead used to
package and transmit data.
• Communications frequently require some type of synchronization between tasks,
which can result in tasks spending time "waiting" instead of doing work.
• Competing communication traffic can saturate the available network bandwidth,
further aggravating performance problems.

17
Factors to Consider (2)
• Latency vs. Bandwidth:
• Latency is the time it takes to send a minimal (0 byte) message from point A to point
B. Commonly expressed as microseconds.
• Bandwidth is the amount of data that can be communicated per unit of time.
Commonly expressed as megabytes/sec.
• Sending many small messages can cause latency to dominate communication
overheads. Often it is more efficient to package small messages into a larger
message, thus increasing the effective communications bandwidth.

• Visibility of Communications:
• With the Message Passing Model, communications are explicit and generally quite
visible and under the control of the programmer.
• With the Data Parallel Model, communications often occur transparently to the
programmer, particularly on distributed memory architectures. The programmer may 18
not even be able to know exactly how inter-task communications are being
accomplished.
Factors to Consider (3)
• Synchronous vs. Asynchronous Communications:
• Synchronous communications require some type of "handshaking" between tasks
that are sharing data. This can be explicitly structured in code by the programmer, or
it may happen at a lower-level unknown to the programmer.
• Synchronous communications are often referred to as blocking communications
since other work must wait until the communications have completed.
• Asynchronous communications allow tasks to transfer data independently from one
another. For example, task 1 can prepare and send a message to task 2, and then
immediately begin doing other work. When task 2 actually receives the data doesn't
matter.
• Asynchronous communications are often referred to as non-blocking
communications since other work can be done while the communications are taking
place.
19
• Interleaving computation with communication is the single greatest benefit for using
asynchronous communications.
Factors to Consider (4)
• Scope of Communications:
• Knowing which tasks must communicate with each other is critical during the design
stage of a parallel code. Both of the two scopings described below can be
implemented synchronously or asynchronously.
• Point-to-point – involves two tasks with one task acting as the sender/producer of
data, and the other acting as the receiver/consumer.
• Collective – involves data sharing between more than two tasks, which are often
specified as being members in a common group, or collective. Some common
variations (there are more):

20
Factors to Consider (5)
• Efficiency of Communications:
• Oftentimes, the programmer has choices that can affect communications
performance. Only a few are mentioned here.
• Which implementation for a given model should be used? Using the Message
Passing Model as an example, one MPI implementation may be faster on a given
hardware platform than another.
• What type of communication operations should be used? As mentioned previously,
asynchronous communication operations can improve overall program performance.
• Network media – different platforms use different networks. Some networks perform
better than others. Choosing a platform with a faster network may be an option.

21
Factors to Consider (6)
• Overhead and Complexity:

22
Factors to Consider (7)
• Finally, realize that this is only a partial list of things to consider!!!

23
Types of Synchronization
• Barrier:
• Usually implies that all tasks are involved
• Each task performs its work until it reaches the barrier. It then stops, or "blocks".
• When the last task reaches the barrier, all tasks are synchronized and released.
• Locks/Semaphore:
• Can involve any number of tasks
• Typically used to “protect” access to the critical section of code. Only one task at a time may
use (own) the lock / semaphore / flag.
• The first task to acquire the lock "sets" it and then safely access the critical section.
• Other tasks attempting to acquire the lock must wait until the task owning the lock releases it.
• Can be blocking or non-blocking
• Synchronous Communication Operations:
• Involves only those tasks executing a communication operation
24
• Tasks performing a communication operation between them require some form of coordination.
For example, before a task can perform a send operation, it must first receive an
acknowledgment from the receiving task that it is OK to send.
Data Dependencies
• A dependence exists between
program statements when the order
of statement execution affects the
results of the program.

• A data dependence results from

multiple use of the same location(s)
in storage by different tasks.

• Dependencies are important to

parallel programming because they
are one of the primary inhibitors to
25
parallelism.
Example 1: Loop Carried Data Dependence
DO 500 J = MYSTART,MYEND
A(J) = A(J-1) * 2.0500
CONTINUE

• The value of A(J-1) must be computed before the value of A(J); therefore
A(J) exhibits a data dependency on A(J-1). Parallelism is inhibited.
• If Task 2 has A(J) and task 1 has A(J-1), computing the correct value of
A(J) necessitates:
• Distributed memory architecture - task 2 must obtain the value of A(J-1) from task 1
after task 1 finishes its computation
• Shared memory architecture - task 2 must read A(J-1) after task 1 updates it

26
Example 2: Loop Independent Data Dependence
task 1 task 2
------ ------
X = 2 X = 4
. .
. .
Y = X**2 Y = X**3

• As with the previous example, parallelism is inhibited. The value of Y is

dependent on:
• Shared memory architecture - which task last stores the value of X.
• Distributed memory architecture – if or when the value of X is communicated between
the tasks.

• Although all data dependencies are important to identify when designing parallel 27
programs, loop carried dependencies are particularly important since loops are
possibly the most common target of parallelization efforts.
How to Handle Data Dependencies?
• Distributed memory architectures – communicate required data at
synchronization points.

• Shared memory architectures -synchronize read/write operations between tasks.

28
Load Balancing
• Load balancing refers to the practice of distributing work among tasks so that
all tasks are kept busy all the time. It can be considered a minimization of task
idle time.
• Load balancing is important to parallel programs for performance reasons. For
example, if all tasks are subject to a barrier synchronization point, the slowest
task will determine the overall performance.

29
How to Achieve Load Balance? (1)
• Equally partition the work each task receives
• For array/matrix operations where each task performs similar work, evenly distribute
the data set among the tasks.
• For loop iterations where the work done in each iteration is similar, evenly distribute
the iterations across the tasks.
• If a heterogeneous mix of machines with varying performance characteristics are
being used, be sure to use some type of performance analysis tool to detect any load
imbalances. Adjust work accordingly.

30
How to Achieve Load Balance? (2)
• Use dynamic work assignment
• Certain classes of problems result in load imbalances even if data is evenly
distributed among tasks:
• Sparse arrays – some tasks have actual data to work on while others have mostly "zeros".
• Adaptive grid methods - some tasks may need to refine their mesh while others don't.
• N-body simulations - where some particles may migrate to/from their original task domain
to another task's; where the particles owned by some tasks require more work than those
owned by other tasks.
• When the amount of work each task will perform is intentionally variable, or is unable
to be predicted, it may be helpful to use a scheduler – task pool approach. As
each task finishes its work, it queues to get a new piece of work.
• It may become necessary to design an algorithm which detects and handles load
imbalances as they occur dynamically within the code.
31
Granularity
• Computation/Communication Ratio:
• In parallel computing, granularity is a qualitative measure of the ratio of computation
to communication.
• Periods of computation are typically separated from periods of communication by
synchronization events.

• Fine-grain Parallelism
• Coarse-grain Parallelism

32
Fine-grain Parallelism
• Relatively small amounts of computational
work are done between communication events

• Low computation to communication ratio

• Facilitates load balancing

• Implies high communication overhead and less

opportunity for performance enhancement

• If granularity is too fine, it is possible that the

overhead required for communications and
synchronization between tasks takes longer
than the computation. 33
Coarse-grain Parallelism
• Relatively large amounts of computational work are done between
communication/synchronization events

• High computation to communication ratio

• Implies more opportunity for performance increase

• Harder to load balance efficiently

34
Which is Best?
• The most efficient granularity is dependent on the algorithm and the hardware
environment in which it runs.

• In most cases the overhead associated with communications and

synchronization is high relative to execution speed, so it is advantageous to
have coarse granularity.

• Fine-grain parallelism can help reduce overheads due to load imbalance.

35
I/O
• The bad News:
• I/O operations are generally regarded as inhibitors to parallelism
• Parallel I/O systems are immature or not available for all platforms
• In an environment where all tasks see the same filespace, write operations will result
in file overwriting
• Read operations will be affected by the fileserver's ability to handle multiple read
requests at the same time
• I/O that must be conducted over the network (NFS, non-local) can cause severe
bottlenecks

36
I/O
• The good News: Some parallel file systems are available. For example:
• GPFS: General Parallel File System for AIX (IBM)
• Lustre: for Linux clusters (Cluster File Systems, Inc.)
• PVFS/PVFS2: Parallel Virtual File System for Linux clusters (Clemson/Argonne/Ohio
State/others)
• PanFS: Panasas ActiveScale File System for Linux clusters (Panasas, Inc.)
• HP SFS: HP StorageWorks Scalable File Share. Lustre based parallel file system
(Global File System for Linux) product from HP

• The parallel I/O programming interface specification for MPI has been available
since 1996 as part of MPI-2. Vendor and "free" implementations are now
commonly available.
37
Some Options
• Rule #1: Reduce overall I/O as much as possible
• Writing large chunks of data rather than small chunks is usually significantly more
efficient.
• Fewer, larger files performs better than many small files.
• Confine I/O to specific serial portions of the job and then use parallel communications to
distribute data to parallel tasks; e.g., Task 1 could read an input file and then
communicate required data to other tasks. Likewise, Task 1 could perform write
operation after receiving required data from all other tasks.
• For distributed memory systems with shared filespace, perform I/O in local, non-shared
filespace. For example, each processor may have /tmp filespace which can used. This
is usually much more efficient than performing I/O over the network to one's home
directory.
• Create unique filenames for each tasks' input/output file(s)
38
• Aggregate I/O operations across tasks - rather than having many tasks perform I/O,
have a subset of tasks perform it.
Performance Analysis and Tuning
• Analyzing and tuning parallel program performance can be much more
challenging than for serial programs.

• Fortunately, there are a number of excellent tools for parallel program

performance analysis and tuning.
• TAU: [Link]
• HPCToolkit: [Link]
• Open|Speedshop: [Link]
• Vampir / Vampirtrace: [Link]
• Valgrind: [Link]
• PAPI: [Link]
• mpiP: [Link] 39
• memP: [Link]
Limits and Costs of Parallel Programming
• Complexity: In general, parallel applications are much more complex than
corresponding serial applications, perhaps an order of magnitude. Not only do
you have multiple instruction streams executing at the same time, but you also
have data flowing between them.
• The costs of complexity are measured in programmer time in virtually every
aspect of the software development cycle:
• Design
• Coding
• Debugging
• Tuning
• Maintenance

• Adhering to "good" software development practices is essential when working

with parallel applications - especially if somebody besides you will have to work 40
with the software.
Limits and Costs of Parallel Programming
• Portability: Thanks to standardization in several APIs, such as MPI, POSIX
threads, HPF and OpenMP, portability issues with parallel programs are not as
serious as in years past. However...

• All of the usual portability issues associated with serial programs apply to
parallel programs. For example, if you use vendor "enhancements" to Fortran,
C or C++, portability will be a problem.

• Even though standards exist for several APIs, implementations will differ in a
number of details, sometimes to the point of requiring code modifications in
order to effect portability.

• Operating systems can play a key role in code portability issues.

41
• Hardware architectures are characteristically highly variable and can affect
portability.
Limits and Costs of Parallel Programming
• Resource Requirement: The primary intent of parallel programming is to
decrease execution wall clock time, however in order to accomplish this, more
CPU time is required. For example, a parallel code that runs in 1 hour on 8
processors actually uses 8 hours of CPU time.

• The amount of memory required can be greater for parallel codes than serial
codes, due to the need to replicate data and for overheads associated with
parallel support libraries and subsystems.

• For short running parallel programs, there can actually be a decrease in

performance compared to a similar serial implementation. The overhead costs
associated with setting up the parallel environment, task creation,
communications and task termination can comprise a significant portion of the
total execution time for short runs. 42
Limits and Costs of Parallel Programming
• Scalability: Two types of scaling based on time to solution:

• Strong Scaling
• The total problem size stays fixed as more
processors are added.
• Goal is to run the same problem size faster
• Perfect scaling means problem is solved in 1/N time
(compared to serial)

• Weak Scaling
• The problem size per processor stays fixed as more
processors are added. The total problem size is
proportional to the number of processors used.
• Goal is to run larger problem in same amount of time
• Perfect scaling means problem runs in same time as 43
single processor run
Limits and Costs of Parallel Programming
• The ability of a parallel program's performance to scale is a result of various
interrelated factors. Simply adding more machines is rarely the answer.

• The algorithm may have inherent limits to scalability. At some point, adding more
resources causes performance to decrease. Most parallel solutions demonstrate
this characteristic at some point.

• Hardware factors play a significant role in scalability. Examples:

• Memory-CPU bus bandwidth on an SMP machine
• Communications network bandwidth
• Amount of memory available on any given machine or set of machines
• Processor clock speed

• Parallel support libraries and subsystems software can limit scalability 44

independent of your application.
Limits and Costs of Parallel Programming
• Dark Grey: Time spent on computation, decreasing
with # of processors

• White: Time spent on communication, increasing

with # of processors

• Operations in a parallel program:

• Computation that must be performed sequentially
• Computations that can be performed in parallel
• Parallel overhead including communication and
redundant computations

45
Limits and Costs of Parallel Programming
• How can we quantify the possible gains from parallelization?

• Amdahl’s Law (strong scaling)

• Analyze whether a program merits parallelization

• Gustafson-Barsis’s Law (weak scaling)

• Evaluate performance of a parallel program

• Karp-Flatt metri
• Calculates the serial fraction for a given parallel configuration and determines
whether the principal barrier to speedup is due to inherently sequential code or
parallelization overhead
46
• Isoefficiency metric
• Evaluate the scalability of a parallel program executing on a parallel computer
Amdahl’s Law
• Formulized in 1967, it analyzes whether a program merits parallelization by showing
an upper-bound on the maximum speedup that can be achieved by a parallel
algorithm of a problem.

• Amdahl’s Law states that that potential program speedup is defined by the fraction
of code (P) that can be parallelized:
𝟏
𝑺𝒑𝒆𝒆𝒅𝒖𝒑 =
𝟏−𝑷

• If none of the code can be parallelized, 𝑷 = 𝟎

and speedup = 1 (no speedup). If all the code
is parallelized, 𝑷 = 𝟏 and the speedup is
infinite (in theory).
47
• If 50% of the code can be parallelized,
maximum speedup = 2, meaning the code will
run twice as fast.
Amdahl’s Law
• Introducing the number of processors performing the parallel fraction of work,
the relationship can be modeled by:
𝟏
𝑺𝒑𝒆𝒆𝒅𝒖𝒑 =
𝑷
𝑺+𝑵

• where 𝑷 = parallel fraction, 𝑵 = number of processors and 𝑺 = serial fraction.

• What if you have infinite number of processors?

𝟏 𝟏
Upper Limit: as 𝑵 → ∞, 𝑺𝒑𝒆𝒆𝒅𝒖𝒑 ≤ 𝑺+𝑷Τ𝑵 < 𝑺

48
• What do you have to do for further speedup?
Speedup vs. P
• Amdahl’s law assumes that the problem size is fixed. It provides an upper bound
on the speedup achievable by applying a certain number of processors.

49
Amdahl’s Law
• Example 1: If 90% of the computation can be parallelized, what is the maximum
speedup achievable using 8 processors?

• Solution:
𝑃 = 90%
𝟏
𝑺𝒑𝒆𝒆𝒅𝒖𝒑 ≤ ≈ 𝟒. 𝟕
Τ
𝟏 − 𝟎. 𝟗 + 𝟎. 𝟗 𝟖

50
Amdahl’s Law
• Example 2: Suppose 25% of a sequential algorithm is the parallelizable portion.
The remaining part must be calculated sequentially. Calculate maximum
theoretical speedup for parallel variant of this algorithm using:
• 5 processors

• Little challenge: Determine, according to Amdahl’s law, how many processors

are needed to achieve maximum theoretical speedup while sequential portion
remains the same?
• That is why we say actual achievable speedup is always less than or equal to
theoretical speedups

51
Amdahl’s Law: Remarks
• Amdahl’s law shows how execution time decreases as no. of processors
increases up to a certain limit.

• Parallelization overhead is ignored by Amdahl’s law

• Optimistic estimate of speedup

• Amdahl’s Effect:
• Typically, parallelization overhead has lower complexity than 𝑷Τ𝑵 . For a fixed number
of processors, speedup is usually an increasing function of the problem size 𝒏.
• As 𝒏 increases,𝑷Τ𝑵 >> parallelization overhead and speedup increases

• The inherently sequential portion S may decrease when n increases

• Amdahl’s law (𝒔𝒑𝒆𝒆𝒅𝒖𝒑 < 1Τ𝑆) can overestimate speedup for larger problems
52
• Problems that increase the percentage of parallel time with their size are more
scalable than problems with a fixed percentage of parallel time.
Gustafson-Barsis’s Law
• Gustafson-Barsis’s Law is a scalability principle that challenges Amdahl’s Law
by considering how increasing problem sizes affect parallel performance.

• Statement: Given a parallel program of size 𝑛 using N processors, let S be the

fraction of total execution time spent in serial code. The maximum speedup
achieved by the program is:
𝒔𝒑𝒆𝒆𝒅𝒖𝒑 ≤ 𝑵 + 𝟏 − 𝑵 𝑺

• Unlike Amdahl’s Law, which assumes a fixed problem size and shows
diminishing speedup due to the serial portion, Gustafson-Barsis’s Law argues
that as problem sizes grow, the parallel portion grows as well.

• This means parallel systems can scale effectively, making high-performance 53

computing feasible.
Gustafson-Barsis’s Law: Remarks
• Gustafson-Barsis’s law allows to solve larger problems using more processors.
The speedup is called scaled speedup.

• Since parallelization overhead is ignored, Gustafson-Barsis’s law may

overestimate the speedup.

• The best achievable speedup is ≤ 𝑵

• If 𝑠 = 1, then there is no speedup.

• Gustafson-Barsis’s Law explains why supercomputers remain highly effective

for solving large-scale problems despite inherent serial portions. It shows that as
the problem size increases, the relative impact of the serial portion shrinks.
54
Gustafson-Barsis’s Law: Remarks
• Example: An application executing on 64 processors using 5% of the total time
on non-parallelizable computations. What is the scaled speedup?

• Solution:
𝑆 = 0.05
𝑆𝑝𝑒𝑒𝑑𝑢𝑝 ≤ 𝑁 + 1 − 𝑁 𝑆
= 64 + 1 − 64 (0.05) ≈ 𝟔𝟎. 𝟖𝟓

55
Karp-Flatt Metric
• Both Amdahl’s law and Gustafson-Barsis’s law ignore the parallelization
overhead and overestimate the achievable speedup.
• Karp-Flatt metric is used to measure the effectiveness of parallel computing
by analyzing how much serial overhead affects speedup. It helps determine
whether a parallel system is limited by inherent sequential portions or by
inefficiencies like parallelization overhead.
• Process startup time
• Process synchronization time
• Communication overhead
• Imbalanced workload
• Architectural overhead
56
Karp-Flatt Metric
• Given a parallel program exhibiting a speedup 𝜳(N) while using N processing
units, then experimentally determined serial fraction e can be determined as:
1ൗ − 1ൗ
𝜳(𝑵) 𝑁
𝑒=
1 − 1ൗ𝑁
• Interpretation of 𝑒:
• If 𝑒 is small  The problem is highly parallelizable, meaning the slowdown is not due
to serial work.
• If 𝑒 is large  The speedup is being significantly limited by sequential execution or
parallel inefficiencies (e.g., communication, synchronization overhead).
• May either stay constant as N increases (system constrained by Amdahl’s Law due to
inherent sequential bottleneck and parallelization overhead is negligible) or increase
as N increases (parallelization overhead dominates the speedup) 57
Karp-Flatt Metric
• Example 1: Suppose in a parallel program, for 5 processors, you gained a
speedup of 1.25x, determine sequential fraction of your program

• Solution:
1ൗ − 1ൗ
𝟏. 𝟐𝟓 5
𝑒= 1ൗ
≈ 0.75
1− 5

58
Karp-Flatt Metric
• Example 2: Benchmarking a parallel program on 1, 2,…, 8 processors produces the
following speedup results:
N 2 3 4 5 6 7 8
𝜳 𝑵 1.82 2.50 3.08 3.57 4.00 4.38 4.71

• What is the primary reason for the parallel program achieving a speedup of only 4.71 on
8 processors?

• Solution: Compute 𝒆 𝑵 corresponding to each data point:

N 2 3 4 5 6 7 8
𝜳 𝑵 1.82 2.50 3.08 3.57 4.00 4.38 4.71
𝒆 𝑵 0.1 0.1 0.1 0.1 0.1 0.1 0.1

• Since the experimentally determined serial fraction 𝒆 𝑵 is not increasing with N, the 59
primary reason for the poor speedup is the 10% of the computation that is inherently
sequential. Parallel overhead is not the reason for the poor speedup.
Karp-Flatt Metric
• Example 3: Benchmarking a parallel program on 1, 2,…, 8 processors produces the
following speedup results:
N 2 3 4 5 6 7 8
𝜳 𝑵 1.87 2.61 3.23 3.73 4.14 4.46 4.71

• What is the primary reason for the parallel program achieving a speedup of only 4.71 on
8 processors?

• Solution: Compute 𝒆 𝑵 corresponding to each data point:

N 2 3 4 5 6 7 8
𝜳 𝑵 1.87 2.61 3.23 3.73 4.14 4.46 4.71
𝒆 𝑵 0.07 0.075 0.08 0.085 0.09 0.095 0.1

• Since the experimentally determined serial fraction 𝑒 is steadily increasing with N, 60

parallel overhead also contributes to the poor speedup.
Isoefficiency Metric
• Scalability of a parallel system is a measure of its ability to increase
performance as the number of processors increases. Isoefficiency metric is
used to evaluate the scalability of a parallel system.
• A scalable system should maintain efficiency as # of processors (N) is
increased. Isoefficiency metric tells us how much we need to increase the
problem size or computational work (W) to maintain a constant efficiency (E)
as we add more processors.
• Isoefficiency function (W) describes how W should grow relative to N. A lower
value of W means better scalability.
𝜳 𝑵 𝑊
𝐸= =
𝑵 𝑾 + 𝑻𝟎 𝑵
61
• 𝑻𝟎 𝑵 = Parallelization overhead (communication, synchronization, etc.)
Isoefficiency Metric
• For a system to be scalable, the problem size (W) must grow at least as fast as the total
parallelization overhead 𝑻𝟎 𝑵 .
𝑊 ≥ Θ(𝑻𝟎 𝑵 )

• Remarks on Isoefficiency:
• Determines if adding more processors is beneficial.
• Helps in designing scalable parallel algorithms.
• Shows the cost of parallelization overhead (communication, load balancing, etc.).

Isoefficiency Function Problem Size

W = O(1) (constant) Perfect scalability (ideal but unrealistic)
W = O(log 𝑁) Excellent scalability
W = O(𝑁) Good scalability
W = O(𝑁 2 ) Poor scalability 62
W = O(𝑒 𝑁 ) Extremely poor scalability (unscalable)
Isoefficiency Metric
• Example: The Explicit Finite Difference problem is solved on a 𝒎 × 𝒎 grid using 𝑵
processors. Each processor is responsible for a subgrid of size 𝒎Τ 𝑵) × (𝒎Τ 𝑵 .
During each time step, every processor sends boundary values to its four neighbors for
which the required communication time is O(𝒎Τ 𝑵). Find the isoefficiency function.
• Solution:
O(𝑚2 )
𝐸=
O(𝑚2 ) + O(𝒎Τ 𝑵)

• For constant efficiency, we require:𝑚2 ≥ Θ(𝒎 𝑵)

𝑚2 ≥ Θ(𝒎 𝑵) ⟹ 𝑚 ≥ Θ( 𝑵) ⟹ 𝑚2 = O(𝑵)

• Thus, the isoefficiency function is: 𝑊 = O(𝑵)

63
• Therefore, to maintain efficiency, the problem size 𝑚2 must grow at least as fast as O(𝑵).