Parallel Grid Generation

SUMMARY

The purpose of this project is to design and implement parallel algorithms and software modules for structured and unstructured static and adaptive grids that are necessary for the scalability of the existing parallel Partial Differential Equation (PDE) solvers. Our modules will provide support to high performance software and simulation environments such as High Performance Fortran (HPF), Parallel ELLPACK (PELLPACK), and National Grid Project (NGP).

PARTICIPANTS

Northeast Parallel Architectures Center
National Science Foundation Engineering Research Center for Computational Field Simulation (ERC-CFS) : Mississippi State University.

KEY CONTACTS

Dr. Nikos Chrisochoides, phone : (315) 443 3794, e-mail : nikos@npac.syr.edu

IMPACT

The long term goal of the project is to provide portable and efficient software components and tools for grid generation that can be part of parallel software simulation environments for complex applications in science and engineering.

PROJECT DESCRIPTION

An essential element for the numerical approximation of PDEs defined on complex regions is the tessellation of the continuous regions using grids (or meshes) which are used for the discrete representation of the partial differential equations. NPAC in collaboration with National Science Foundation - Engineering Center for Computational Field Simulation at Mississippi State University (NSF/ERC-MSU) will deliver the first state-of-the-art parallel grid generation software on current parallel machines.

In this project we investigate the development of parallel grid generation modules (PGGM) for static and adaptive 2-dimensional (2D) and 3-dimensional (3D) structured grids based on composite block structures :

1. a module for parallel 2D and 3D static and adaptive Algebraic and Elliptic grids for general domains,
2. a module for parallel 2D and 3D Multi-Level Multi-Component Curvilinear Grid Refinement for general domains
3. static and adaptive unstructured meshes for 2D and 3D complex domains. Specifically, in this module we will develop parallel mesh generation methods based on a combination of Delaunay triangulation and Domain Decomposition Methods,
4. a library of templates for the load balancing of composite block structures and
5. a run time support system based on a priority based multilist multithread system.

The parallel grid generation modules will be designed and implemented to be

1. integrated with a High Performance Fortran (HPF) language and compiler, FORTRAN 90D, that is under development at Northeast Parallel Architectures Center (NPAC) at Syracuse University in collaboration with Center for Research on Parallel Processing (CRPC),
2. interfaced with a problem solving environment for parallel processing of PDEs, Parallel ELLPACK (PELLPACK) that is under development at Purdue University and
3. used by a state-of-the-art sequential simulation environment, National Grid Project (NGP) for CFD that is under development at NSF/ERC-MSU.

The above modules are under development within the Mapping Environment for Numerical Unstructured & Structured - Parallel Grid Generation (MENUS-PGG). MENUS-PGG is a problem solving environment (PSE) for developing parallel algorithms that generate structured and unstructured static and adaptive grids (or meshes). Whereas the first generation PSEs for the numerical solution of PDEs on distributed memory multiprocessor systems are based on the data mapping of sequentially generated grids (or meshes) and support only the single threaded data parallel programming model, MENUS-PGG generates and maintains grids on the processors of parallel/distributed systems and combines the most valuable aspects of the data parallel programming model with the flexibility of the multi-thread parallel programming model. MENUS-PGG assumes a machine model that consists of homogeneous and heterogeneous clusters of processors operating in a distributed address space implemented on remote memory modules via message passing through a high-speed interconnection network.

Software Architecture

The software infrastructure of MENUS-PGG consists of three major subsystems namely the front-end subsystem, the grid generation subsystem and the back-end subsystem. The front-end subsystem provides the functionality and operations required for (i) the domain definition, (ii) the decomposition of the continuous domain by a set of non-overlapping subdomains with simpler shape (i.e., four or six-sided polygons for 2 or 3-dimensional spaces), and (iii) the partition and placement of the subdomains to the processors of the target machine so that certain criteria are satisfied. The grid generation subsystem provides a portable and scalable scheduling mechanism and software modules for the efficient and independent grid generation on the subdomains and maintenace of grid conformity and continuity on the interfaces of the subdomains so that the work load of the processors is balanced. The back-end subsystem provides the tools for the visualizationof the grid and performance data. The figure below describes MENUS-PGG software architecture. For more information on the modules click on the corresponding boxes in the figure.

REFERENCES

1. N.P. Chrisochoides, E. Houstis and J. Rice, Mapping Algorithms and Software Environment for Data Parallel PDE Iterative Solvers, to appear in the Special Issue of the Journal of Parallel and Distributed Computing on Data-Parallel Algorithms and Programming, 1993.
2. N.P. Chrisochoides, An alternative to data-mapping for scalable iterative PDE solvers : Parallel Grid Generation, To appear in the Proceedings of the Scalable Parallel Libraries Conference, National Science Foundation Engineering Research Center for Computational Field Simulation, Mississippi State, Mississippi, October 6-8, 1993.
3. N.P. Chrisochoides, A unified appoach for static and dynamic load balancing of computations for parallel numerical grid generation. To appear in the Proceedings of the 4th International Conference on Numerical Grid Generation in Computational Fluid Dynamics and Related Fields, Swansea, UK, April 6-8, 1994.
4. N.P. Chrisochoides, G. C. Fox and J. F. Thompson, MENUS-PGG: Mapping Environment for Numerical Unstructured and Structured - Parallel Grid Generation. To appear in the Proceedings of the Seventh International Conference on Domain Decomposition Methods in Scientific and engineering computing, November 27-30, 1993.
5. N.P. Chrisochoides, G. C. Fox and J.F. Thompson, Elliptic Grid Generation on Distributed Memory MIMD Machines. To appear in the International Conference on Parallel Computational Fluid Dynamics, Paris, France, May 10-12, 1993.
6. J. F. Thompson, The National Grid Project, NSF Engineering Research Center for Computational Field Simulation, 1991.