Parallel Programing - Examples
Understand the Problem and the Program
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.
Page 2 Introduction to High Performance Computing
Example
Calculate the potential energy for each of several
thousand independent conformations of a molecule.
When done, find the minimum energy conformation.
Page 3 Introduction to High Performance Computing
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.
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.
Page 4 Introduction to High Performance Computing
Example
Calculation of the Fibonacci series
(1,1,2,3,5,8,13,21,...) by use of the formula:
F(k + 2) = F(k + 1) + F(k)
Page 5 Introduction to High Performance Computing
Example of a Non-parallelizable Problem
Calculation of the Fibonacci series
(1,1,2,3,5,8,13,21,...) by use of the formula:
F(k + 2) = F(k + 1) + F(k)
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 k + 2 value
uses those of both k + 1 and k. These three terms
cannot be calculated independently and therefore,
not in parallel.
Page 6 Introduction to High Performance Computing
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.
Page 7 Introduction to High Performance Computing
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
Page 8 Introduction to High Performance Computing
Examples (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:
Page 9 Introduction to High Performance Computing
Examples (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.
Although all data dependencies are important to identify when
designing parallel programs, loop carried dependencies are
particularly important since loops are possibly the most common
target of parallelization efforts.
Page 10 Introduction to High Performance Computing
Examples (3): Loop independent data dependence
Page 11 Introduction to High Performance Computing
Examples (3): Loop independent data dependence
Page 12 Introduction to High Performance Computing
Examples (3): Loop independent data dependence
Page 13 Introduction to High Performance Computing
Parallel Examples
PI Calculation
Simple Heat Equation
1-D Wave Equation
Page 14 Introduction to High Performance Computing
Pi Calculation
The value of PI can be calculated in a number of
ways. Consider the following method of
approximating PI
– Inscribe a circle in a square
– Randomly generate points in the square
– Determine the number of points in the square that are also in
the circle
– Let r be the number of points in the circle divided by the
number of points in the square
– PI ~ 4 r
Note that the more points generated, the better the
approximation
Page 15 Introduction to High Performance Computing
Discussion
In the above pool of tasks example, each task
calculated an individual array element as a job. The
computation to communication ratio is finely granular.
Finely granular solutions incur more communication
overhead in order to reduce task idle time.
A more optimal solution might be to distribute more
work with each job. The "right" amount of work is
problem dependent.
Page 16 Introduction to High Performance Computing
Algorithm
npoints = 10000
circle_count = 0
do j = 1,npoints
generate 2 random numbers between
0 and 1
xcoordinate = random1 ;
ycoordinate = random2
if (xcoordinate, ycoordinate)
inside circle then circle_count =
circle_count + 1
end do
PI = 4.0*circle_count/npoints
Note that most of the time in running this program
would be spent executing the loop
Leads to an embarrassingly parallel solution
- Computationally intensive
- Minimal communication
- Minimal I/O
Page 17 Introduction to High Performance Computing
PI Calculation
Parallel Solution
Parallel strategy: break the loop into
portions that can be executed by the
tasks.
For the task of approximating PI:
– Each task executes its portion of the
loop a number of times.
– Each task can do its work without
requiring any information from the
other tasks (there are no data
dependencies).
– Uses the SPMD model. One task
acts as master and collects the
results.
Pseudo code solution: red highlights
changes for parallelism.
Page 18 Introduction to High Performance Computing
Simple Heat Equation
Most problems in parallel computing require communication
among the tasks. A number of common problems require
communication with "neighbor" tasks.
The heat equation describes the temperature
change over time, given initial temperature
distribution and boundary conditions.
A finite differencing scheme is employed to
solve the heat equation numerically on a
square region.
The initial temperature is zero on the
boundaries and high in the middle.
The boundary temperature is held at zero.
For the fully explicit problem, a time stepping
algorithm is used. The elements of a 2-dimensional array
represent the temperature at points on the square.
Page 19 Introduction to High Performance Computing
Simple Heat Equation
The calculation of an element is dependent upon
neighbor element values.
A serial program would contain code like:
Page 20 Introduction to High Performance Computing
Parallel Solution 1
Implement as an SPMD model
The entire array is partitioned and distributed
as subarrays to all tasks. Each task owns a
portion of the total array.
Determine data dependencies
– interior elements belonging to a task are independent of other tasks
– border elements are dependent upon a neighbor task's data,
necessitating communication.
Master process sends initial info to workers, checks for
convergence and collects results
Worker process calculates solution, communicating as
necessary with neighbor processes
Pseudo code solution: red highlights changes for parallelism.
Page 21 Introduction to High Performance Computing
Parallel Solution 2
Overlapping Communication and Computation
In the previous solution, it was assumed that blocking
communications were used by the worker tasks. Blocking
communications wait for the communication process to
complete before continuing to the next program instruction.
In the previous solution, neighbor tasks communicated border
data, then each process updated its portion of the array.
Computing times can often be reduced by using non-blocking
communication. Non-blocking communications allow work to be
performed while communication is in progress.
Each task could update the interior of its part of the solution
array while the communication of border data is occurring, and
update its border after communication has completed.
Pseudo code for the second solution: red highlights changes for
non-blocking communications.
Page 22 Introduction to High Performance Computing
1-D Wave Equation
In this example, the amplitude along a uniform,
vibrating string is calculated after a specified amount
of time has elapsed.
The calculation involves:
– the amplitude on the y axis
– i as the position index along the x axis
– node points imposed along the string
– update of the amplitude at discrete time steps.
Page 23 Introduction to High Performance Computing
1-D Wave Equation
The equation to be solved is the one-dimensional
wave equation:
where c is a constant
Note that amplitude will depend on previous
timesteps (t, t-1) and neighboring points (i-1, i+1).
Data dependence will mean that a parallel solution
will involve communications.
Page 24 Introduction to High Performance Computing
1-D Wave Equation
Parallel Solution
Implement as an SPMD model
The entire amplitude array is partitioned and distributed as
subarrays to all tasks. Each task owns a portion of the total
array.
Load balancing: all points require equal work, so the points
should be divided equally
A block decomposition would have the work partitioned into the
number of tasks as chunks, allowing each task to own mostly
contiguous data points.
Communication need only occur on data borders. The larger the
block size the less the communication.
Page 25 Introduction to High Performance Computing