11.5 Parallel Computing in CFD
357
tiple processors i.e., parallel computers. The advantage of parallel computers
over classical vector supercomputers is scalability. They also use standard
chips and are therefore cheaper to produce. Commercially available parallel computers may have thousands of processors, terabytes of memory and
computing power measured in teraflops. However, algorithms designed for
traditional serial machines may not run efficiently on parallel computers.
If parallelization is performed at the loop level (as is the case with autoparallelizing compilers), Amdahl's law, which essentially says that the speed
is determined by the least efficient part of the code, comes into play. To
achieve high efficiency, the portion of the code that cannot be parallelized
has to be very small.
A better approach is to subdivide the solution domain into sub-domains
and assign each sub-domain to one processor. In this case the same code runs
on all processors, on its own set of data. Since each processor needs data that
resides in other sub-domains, exchange of data between processors and/or
storage overlap is necessary.
Explicit schemes are relatively easy to parallelize, since all operations are
performed on data from preceding time steps. It is only necessary t o exchange
the data a t the interface regions between neighboring sub-domains after each
step is completed. The sequence of operations and the results are identical on
one and many processors. The most difficult part of the problem is usually
the solution of the elliptic Poisson-like equation for the pressure.
Implicit methods are more difficult to parallelize. While calculation of
the coefficient matrix and the source vector uses only 'old' data and can
be efficiently performed in parallel, solution of the linear equation systems
is not easy to parallelize. For example, Gauss elimination, in which each
computation requires the result of the previous one, is very difficult to perform
on parallel machines. Some other solvers can be parallelized and perform the
same sequence of operations on n processors as on a single one, but they are
either not efficient or the communication overhead is very large. We shall
describe two examples.
11.5.1 Iterative Schemes for Linear Equations
The red-black Gauss-Seidel method is well suited for parallel processing. It
was briefly described in Sect. 5.3.9 and consists of performing Jacobi iterations on two sets of points in an alternating manner. In 2D, the nodes are
colored as on a checkerboard; thus, for a five point computational molecule,
Jacobi iteration applied to a red point calculates the new value using data
only from black neighbor nodes, and vice versa. The convergence properties
of this solver are exactly those of the Gauss-Seidel method, which gave the
method its name.
Computation of new values on either set of nodes can be performed in
parallel; all that is needed is the result of the previous step. The result is
exactly the same as on a single processor. Communication between processors
357
tiple processors i.e., parallel computers. The advantage of parallel computers
over classical vector supercomputers is scalability. They also use standard
chips and are therefore cheaper to produce. Commercially available parallel computers may have thousands of processors, terabytes of memory and
computing power measured in teraflops. However, algorithms designed for
traditional serial machines may not run efficiently on parallel computers.
If parallelization is performed at the loop level (as is the case with autoparallelizing compilers), Amdahl's law, which essentially says that the speed
is determined by the least efficient part of the code, comes into play. To
achieve high efficiency, the portion of the code that cannot be parallelized
has to be very small.
A better approach is to subdivide the solution domain into sub-domains
and assign each sub-domain to one processor. In this case the same code runs
on all processors, on its own set of data. Since each processor needs data that
resides in other sub-domains, exchange of data between processors and/or
storage overlap is necessary.
Explicit schemes are relatively easy to parallelize, since all operations are
performed on data from preceding time steps. It is only necessary t o exchange
the data a t the interface regions between neighboring sub-domains after each
step is completed. The sequence of operations and the results are identical on
one and many processors. The most difficult part of the problem is usually
the solution of the elliptic Poisson-like equation for the pressure.
Implicit methods are more difficult to parallelize. While calculation of
the coefficient matrix and the source vector uses only 'old' data and can
be efficiently performed in parallel, solution of the linear equation systems
is not easy to parallelize. For example, Gauss elimination, in which each
computation requires the result of the previous one, is very difficult to perform
on parallel machines. Some other solvers can be parallelized and perform the
same sequence of operations on n processors as on a single one, but they are
either not efficient or the communication overhead is very large. We shall
describe two examples.
11.5.1 Iterative Schemes for Linear Equations
The red-black Gauss-Seidel method is well suited for parallel processing. It
was briefly described in Sect. 5.3.9 and consists of performing Jacobi iterations on two sets of points in an alternating manner. In 2D, the nodes are
colored as on a checkerboard; thus, for a five point computational molecule,
Jacobi iteration applied to a red point calculates the new value using data
only from black neighbor nodes, and vice versa. The convergence properties
of this solver are exactly those of the Gauss-Seidel method, which gave the
method its name.
Computation of new values on either set of nodes can be performed in
parallel; all that is needed is the result of the previous step. The result is
exactly the same as on a single processor. Communication between processors