11.5 Parallel Computing in CFD
363
than the computing time as the number of processors is increased. Therefore,
GC is the limiting factor in massive parallelism. Methods of measuring the
efficiency are discussed below.
11.5.3 Domain Decomposition in Time
Implicit methods are usually used for solving steady flow problems. Although
one is tempted t o think that these methods are not well suited to parallel computing, they can be effectively parallelized by using domain decomposition in
time as well as in space. This means that several processors simultaneously
perform work on the same sub-domain for different time steps. This technique
was first proposed by Hackbusch (1984).
Since none of the equations needs to be solved accurately within an outer
iteration, one can also treat the 'old' variables in the discretized equation as
unknowns. For a two-time-level scheme the equations for the solution at time
step n can be written:
Since we are considering implicit schemes, the matrix and source vector may
depend on the new solution, which is why they carry the index n. The simplest
iterative scheme for solving simultaneously for several time steps is to decouple the equations for each time step and use old values of the variables
where necessary. This allows one to start the calculation for the next time
step as soon as the first estimate for the solution at the current time step is
available, i.e. after one outer iteration is performed. The extra source term
containing the information from the previous time step(s) is updated after
each outer iteration, rather than being held constant as in serial processing.
When the processor k, working on time level t,, is performing its mth outer
iteration, the processor k - 1, working on time level tn-1, is performing its
(m + 1)th outer iteration. The equation system to be solved by processor k
in the mth outer iteration is then:
The processors need to exchange data only once per outer iteration, i.e. the
linear equation solver is not affected. Of course, much more data is transferred
each time than in the method based on domain decomposition in space. If
the number of time steps treated in parallel is not larger than the number
of outer iterations per time step, using the lagged old values does not cause
a significant increase in computational effort per time step. On the last time
step in a parallel sequence, the term (Bn4n-1)k-l is included in the source
term, as it does not change within iterations.
Figure 11.14 shows the structure of the matrix for a two-time-level scheme
with simultaneous solution on four time steps. Time-parallel solution methods
for CFD problems have been used by Burmeister and Horton (1991), Horton
(1991), and Seidl et al. (1995), among others. The method can also be applied
363
than the computing time as the number of processors is increased. Therefore,
GC is the limiting factor in massive parallelism. Methods of measuring the
efficiency are discussed below.
11.5.3 Domain Decomposition in Time
Implicit methods are usually used for solving steady flow problems. Although
one is tempted t o think that these methods are not well suited to parallel computing, they can be effectively parallelized by using domain decomposition in
time as well as in space. This means that several processors simultaneously
perform work on the same sub-domain for different time steps. This technique
was first proposed by Hackbusch (1984).
Since none of the equations needs to be solved accurately within an outer
iteration, one can also treat the 'old' variables in the discretized equation as
unknowns. For a two-time-level scheme the equations for the solution at time
step n can be written:
Since we are considering implicit schemes, the matrix and source vector may
depend on the new solution, which is why they carry the index n. The simplest
iterative scheme for solving simultaneously for several time steps is to decouple the equations for each time step and use old values of the variables
where necessary. This allows one to start the calculation for the next time
step as soon as the first estimate for the solution at the current time step is
available, i.e. after one outer iteration is performed. The extra source term
containing the information from the previous time step(s) is updated after
each outer iteration, rather than being held constant as in serial processing.
When the processor k, working on time level t,, is performing its mth outer
iteration, the processor k - 1, working on time level tn-1, is performing its
(m + 1)th outer iteration. The equation system to be solved by processor k
in the mth outer iteration is then:
The processors need to exchange data only once per outer iteration, i.e. the
linear equation solver is not affected. Of course, much more data is transferred
each time than in the method based on domain decomposition in space. If
the number of time steps treated in parallel is not larger than the number
of outer iterations per time step, using the lagged old values does not cause
a significant increase in computational effort per time step. On the last time
step in a parallel sequence, the term (Bn4n-1)k-l is included in the source
term, as it does not change within iterations.
Figure 11.14 shows the structure of the matrix for a two-time-level scheme
with simultaneous solution on four time steps. Time-parallel solution methods
for CFD problems have been used by Burmeister and Horton (1991), Horton
(1991), and Seidl et al. (1995), among others. The method can also be applied