Civil Engineering Reference
In-Depth Information
Mesh generation by parallel processing
More hands working together in an orderly manner can finish a job in a shorter time.
7.1 INTRODUCTION
With a rapid increase in the problem size from thousands of points to millions of points, it
is imperative to devise ever more efficient schemes for the FE mesh generation (MG). With
a steady but rapid pace of advancement and upgrading since the emergence of modern com-
puters, today's micro-computers, PCs, are all equipped with more than one processor, and
a standard machine with four cores and 16-GB memory is fairly common. Using one single
processor for MG represents a pitiful 25% usage of the total capacity of the machine, and
efficient parallel meshing schemes making full use of all the processors will simply boost the
speed by more than four times, cutting down the generation time to one quarter of that by
a serial process.
There are two quite different ways in parallelising the MG process: (i) domain partition -
the problem domain is first subdivided into a number of zones, each of which is handled
by one processor for MG; and (ii) the problem domain is taken as a whole in MG by several
processors operating simultaneously. The strategy by domain decomposition is more restric-
tive as we have to deal with the boundary between zones and a load balance among all the
zones for higher efficiency, but it comes with an advantage that existing MG techniques can
all be used directly for parallel meshing. A parallelisation of MG on the entire domain is
more general, as no artificial barrier is imposed to limit the shape and the structural con-
nections of the elements. Attempts for parallel meshing have been made on the two most
popular methods, namely, the DT and the AFT, for the generation of unstructured meshes.
By the nature of the evolution of the generation front that the resulting mesh will depend
on the process of how elements are created, it is in general much more difficult to formu-
late a robust parallelisation algorithm for ADF meshing, especially for large-scale problems
(Shostko and Lohner 1995; Wilson and Topping 1998; Lohner 2001). Alternatively, in view
of the boundary integrity inherent with ADF, a parallel meshing scheme was developed
by Ito et al. (2007) based on a domain decomposition into simpler regions. On the other
hand, DT is unique if all the points are in the general positions, and the resulting mesh only
depends on the points but not on their order of insertion. By the lemma of Delaunay, DT by
point insertion can be made a localised process, which lends itself to many possibilities for
parallelisation.
The merits of DT are its robustness with a sound mathematical basis and the availability
of an efficient generic insertion algorithm, which can triangulate large practical point sets
in linear time complexity. Owing to all these attractive properties of DT, there have been
385
