Parallel algorithms for three-dimensional automatic meshing and hierarchical substructuring
Mukul Saxena · 1990
This dissertation addresses two key problems for the development of automatic 3-D FEM analysis systems: (i) automatic mesh generation for solids represented in a solid modeling system, and (ii) analysis of such meshes in the context of a self-adaptive incremental process. The objective is threefold, namely: (1) the design and implementation of a general purpose, rigorously automatic, and computationally efficient algorithm for meshing of solid models in parallel computational environments; (2) the development and implementation of a 3-D analysis procedure designed for integration with the meshing algorithm; (3) the design and evaluation of parallel processing configurations for automatic meshing and for integrated meshing-analysis procedures. In the first stage of this research, a novel, two-stage algorithm for automatic meshing of solids, described in modern solid modeling systems, is introduced. The algorithm combines the concepts of recursive spatial decomposition (RSD), mapping, and element extraction. In stage 1, the solid is approximated by a collection of variably-sized, RSD generated cells which are stored in a hierarchical tree. In stage 2 the approximating cell structure, which includes cells that are wholly inside the solid (IN) as well as cells that are neither inside nor outside (NIO), is transformed into a finite element model. IN cells are directly mapped into finite elements while NIO cells are decomposed, according to their topological complexity, through either template mapping or recursive element extraction. The meshing algorithm is specifically designed for parallel computation and is shown to be general purpose, rigorously automatic and computationally efficient. In the second stage of this dissertation, the concept of hierarchical substructuring, previously developed at the University of Rochester in the context of 2-D problems, is adopted to develop and implement a 3-D analysis procedure. To allow for close integration between meshing and analysis, this procedure is designed to operate on a hierarchical tree structure virtually identical to the one used to store the RSD cells and the mesh. The hierarchical substructuring procedure is inherently suitable for parallel processing and is shown to exhibit asymptotic optimality for worst-case time and space complexity. Finally, a systematic simulation of parallel computational environments is performed to provide guidelines for the development of an integrated FEM analysis system. Fine- and coarse-grain parallel configurations for implementing the present meshing algorithms are formulated and evaluated through simulation. Hierarchical substructuring is studied in the context of coarse-grain parallelism and vectorization. A coarse-grain implementation based on workstations is found to be advantageous in terms of global efficiency, machine availability, and meshing-analysis integration.