Domain Decomposition

Generally, to achieve a high parallelism with a favourable load balancing, employed algorithms should satisfy the following two goals

- most of the algorithms should be performed in parallel (preferably using all available processors),
- the total amount and number of interprocessor communications should be minimized.

Most of the parallelization strategies are based on some kind of decomposition in space or time. This is also true for the mesh generation algorithms with the space being the dominant dimension for the domain decomposition concept. To respect the above mentioned requirements for the effective parallelization, a domain decomposition should fulfill the following conditions

- the individual subdomains should be approximately of the same complexity (taking into account the performance of the processor),
- the interface between the subdomains should be minimized.

- the total amount of work load of subdomains processed on each processor should be approximately the same (taking into account the performance of the processor).

In the presented work, the actual parallelization strategy is also based on the domain decomposition concept. The domain decomposition has been considered on two levels - the model level and the model entity parametric tree level. The decomposition on the model level splits the model into subdomains on the model entity basis (Fig. 3.9a) where each non-boundary model entity constitutes an individual subdomain. The advantage of this approach consists in the fact that the decomposition is in agreement with the physical concept of the model (the interprocessor boundaries coincide with the model boundaries). The decomposition on the parametric tree level (Fig. 3.9b) may be compared, in some sense, with the orthogonal recursive bisection (ORB) in the parametric space of a given model entity. Since the splitting is done in the parametric space, its image in the real space does not generally result in subdomains of a similar size. The next bisection, however, may be applied to the larger (or more complex) from those subdomains. In this way, an arbitrary number of subdomains, with no one exceeding a prescribed value of complexity, may be created. This is a good starting point to achieve an acceptable parallel performance for various number of processors and a varying model complexity. An important fact is that all the subdomains on the model entity parametric tree level can be handled uniquely because they are described by the same model entity and differs only in the range of parametric coordinates. Note that in the current implementation, the domain decomposition has been realized only on the model entity level. This does not cause difficulties unless the model is consisting of a too small number of model entities, which effectively disables construction of the domain decomposition either in terms of the desirable quality or in terms of the number of subdomains. In most practical cases, however, the complexity of the model is usually large enough to construct a reasonable domain decomposition. This is the direct consequence of the topological representation employed for the model description.

*Daniel Rypl
2005-12-07*