|
Parralel Computing Turorial |
|
|
|
|
Written by Hemanshu Patel
|
|
Sunday, 23 December 2007 |
|
Page 18 of 18
Parallel Examples1-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:
o the amplitude on the y axis
o i as the position index along the x axis
o node points imposed along the string
o update of the amplitude at discrete time steps.
Wave equation
* The equation to be solved is the one-dimensional wave equation:
A(i,t+1) = (2.0 * A(i,t)) - A(i,t-1)
+ (c * (A(i-1,t) - (2.0 * A(i,t)) + A(i+1,t)))
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.
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.
Wave equation partition
* Pseudo code solution:
find out number of tasks and task identities
#Identify left and right neighbors
left_neighbor = mytaskid - 1
right_neighbor = mytaskid +1
if mytaskid = first then left_neigbor = last
if mytaskid = last then right_neighbor = first
find out if I am MASTER or WORKER
if I am MASTER
initialize array
send each WORKER starting info and subarray
else if I am WORKER
receive starting info and subarray from MASTER
endif
#Update values for each point along string
#In this example the master participates in calculations
do t = 1, nsteps
send left endpoint to left neighbor
receive left endpoint from right neighbor
send right endpoint to right neighbor
receive right endpoint from left neighbor
#Update points along line
do i = 1, npoints
newval(i) = (2.0 * values(i)) - oldval(i)
+ (sqtau * (values(i-1) - (2.0 * values(i)) + values(i+1)))
end do
end do
#Collect results and write to file
if I am MASTER
receive results from each WORKER
write results to file
else if I am WORKER
send results to MASTER
endif
This completes the tutorial.
References and More Information
* Author: Blaise Barney, Livermore Computing.
* A search on the WWW for "parallel programming" will yield a wide variety of information.
* These materials were primarily developed from the following sources, some of which are no longer maintained or available.
o Tutorials located in the Maui High Performance Computing Center's "SP Parallel Programming Workshop".
o Tutorials located at the Cornell Theory Center's "Education and Training" web page.
o "Designing and Building Parallel Programs". Ian Foster.
|
|
Last Updated ( Sunday, 23 December 2007 )
|
Technology 
