Information Technology Reference
In-Depth Information
Algorithm 10.1
Explicit Scheme for Solving the 1D Diffusion Problem (7.82)-(7.85)ona
Distributed-Memory Computer.
Given
n C 1
as the total number of global mesh points,
x D 1=n
,
t
as the time step size,
m
as the number of time steps,
˛ D t =x
2
,
and
P
as the total number of processors.
On processor
p
(
0 p P 1
):
if
p<
mod
.n 1; P /
then
n
p
n
P
˘
D
C 1
else
D
n
P
˘
n
p
D p
n
P
˘
C
i
start
;p
min
.p;
mod
.n 1; P //
Allocate local arrays
u
p
and
u
`C1
p
both of length
n
p
C 2
Initial condition:
u
p;i
D I..i
start
;p
C i/x/
,for
i
D 0; 1; : : : ; n
p
C 1
for
` D 0; 1; : : : ; m 1
for
i
D 1;2;:::;n
p
u
`C1
p;i
u
p;i
C ˛
u
p;i1
2
u
p;i
u
p;iC1
D
C
Ctf ..i
start
;p
C i/x;t
`
/
if
p D 0
then
u
`C1
p;0
D D
0
.t
`C1
/
else
receive value from processor
p 1
into
u
`C1
p;0
send value of
u
`C1
p;1
to processor
p 1
if
p D P
1
then
u
p;n
p
C1
C 2˛
u
p;n
p
u
p;n
p
C1
C N
1
.t
`
/x
u
`C1
p;n
p
C1
D
Ctf .1; t
`
/
else
send value of
u
`C1
p;n
p
to processor
p C 1
receive value from processor
p C 1
into
u
`C1
p;n
p
C1
Data copy before next time step:
u
p
u
`C1
p
D
end for
For instance, an addition operation between two scalar values is obviously not
a subject for parallelization, whereas adding two long vectors is embarrassingly
parallel. Solving a single ordinary differential equation (ODE), even if a huge num-
ber of time steps are employed, is normally serial by nature. This is because each
time step contains too little work and the time steps have to be carried out one after
another. For a system of ODEs, the situation with respect to parallel computing can
be improved, especially when the number of involved ODEs is large. Parallelism
can be found within each time step, either because the ODEs are handled sepa-
rately in an explicit scheme, or because an implicit scheme solves a linear system
that has some level of parallelism. Nevertheless, the number of ODEs in a system
is normally not as many as the number of available processors, so exploiting such
limited parallelism can be challenging. The best situation arises in an ODE-PDE
