360
11. Efficiency and Accuracy Improvement
11.5.2 Domain Decomposition in Space
Parallelization of implicit methods is usually based on data parallelism or
domain decomposition, which can be performed both in space and time. In
spatial domain decomposition, the solution domain is divided into a certain
number of sub-domains; this is similar to block-structuring of grids. In blockstructuring the process is governed by the geometry of the solution domain,
while, in domain decomposition, the objective is to maximize efficiency by
giving each processor the same amount of work to do. Each sub-domain is
assigned to one processor but more than one grid block may be handled by
one processor; if so, we may consider all of them as one logical sub-domain.
As already noted, one has t o modify the iteration procedure for parallel
machines. The usual approach is to split the global coefficient matrix A into
a system of diagonal blocks Aii, which contain the elements connecting the
nodes that belong to the ith sub-domain, and off-diagonal blocks or coupling
matrices Aij (i f j ) , which represent the interaction of blocks i and j . For
example, if a square 2D solution domain is split into four sub-domains and
the CVs are numbered so that the members of each sub-domain have consecutive indices, the matrix has the structure shown in Fig. 11.12; a five-point
molecule discretization is used in this illustration. The method described below is applicable to schemes using larger computational molecules; in this
case, the coupling matrices are larger.
Solution domain
\ Sybdomain boundaries
Fig. 11.12. Structure of the global coefficient matrix when a square 2D solution
domain is subdivided into 4 sub-domains
For efficiency, the iterative solver for the inner iterations should have as
little data dependency (data provided by the neighbors) as possible; data
dependency may result in long communication and/or idle times. Therefore,
the global iteration matrix is selected so that the blocks are de-coupled, i.e.
Mij = 0 for i # j . The iteration scheme on sub-domain i is then:
11. Efficiency and Accuracy Improvement
11.5.2 Domain Decomposition in Space
Parallelization of implicit methods is usually based on data parallelism or
domain decomposition, which can be performed both in space and time. In
spatial domain decomposition, the solution domain is divided into a certain
number of sub-domains; this is similar to block-structuring of grids. In blockstructuring the process is governed by the geometry of the solution domain,
while, in domain decomposition, the objective is to maximize efficiency by
giving each processor the same amount of work to do. Each sub-domain is
assigned to one processor but more than one grid block may be handled by
one processor; if so, we may consider all of them as one logical sub-domain.
As already noted, one has t o modify the iteration procedure for parallel
machines. The usual approach is to split the global coefficient matrix A into
a system of diagonal blocks Aii, which contain the elements connecting the
nodes that belong to the ith sub-domain, and off-diagonal blocks or coupling
matrices Aij (i f j ) , which represent the interaction of blocks i and j . For
example, if a square 2D solution domain is split into four sub-domains and
the CVs are numbered so that the members of each sub-domain have consecutive indices, the matrix has the structure shown in Fig. 11.12; a five-point
molecule discretization is used in this illustration. The method described below is applicable to schemes using larger computational molecules; in this
case, the coupling matrices are larger.
Solution domain
\ Sybdomain boundaries
Fig. 11.12. Structure of the global coefficient matrix when a square 2D solution
domain is subdivided into 4 sub-domains
For efficiency, the iterative solver for the inner iterations should have as
little data dependency (data provided by the neighbors) as possible; data
dependency may result in long communication and/or idle times. Therefore,
the global iteration matrix is selected so that the blocks are de-coupled, i.e.
Mij = 0 for i # j . The iteration scheme on sub-domain i is then: