Next: Parallel Computing Scheme Up: Parallelization Strategy Previous: Parallelization Strategy


Domain Decomposition

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

  1. most of the algorithms should be performed in parallel (preferably using all available processors),
  2. the total amount and number of interprocessor communications should be minimized.
From this point of view, most of the sequential algorithms are inherently not suitable for the parallelization and it is necessary to compromise between the requirements stated above. This is also the case for classical unstructured mesh generation strategies which are essentially scalar and which exhibit a large variation in the number of operations required during each step of the calculation. Since the cost of the computation and communication differs from one hardware platform to another it is even more difficult to find an acceptable parallelization strategy portable to different platforms.

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

  1. the individual subdomains should be approximately of the same complexity (taking into account the performance of the processor),
  2. the interface between the subdomains should be minimized.
However, construction of an efficient domain decomposition for mesh generation algorithms is not straightforward. Firstly, some background data structure is required both for the domain complexity estimate and for the domain decomposition itself. And secondly, the application of sophisticated decomposition algorithms may become unsatisfactory when only a rough prediction of the domain complexity is available. From this point of view, the first condition is usually weakened (allowing for a dynamic load balancing [135]) to

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.



Next: Parallel Computing Scheme Up: Parallelization Strategy Previous: Parallelization Strategy

Daniel Rypl
2005-12-07