Data processing: structural design – modeling – simulation – and em – Modeling by mathematical expression
Reexamination Certificate
1998-05-14
2003-02-11
Frejd, Russell (Department: 2123)
Data processing: structural design, modeling, simulation, and em
Modeling by mathematical expression
C703S022000, C709S241000
Reexamination Certificate
active
06519553
ABSTRACT:
BACKGROUND OF THE INVENTION
This invention relates to the field of multiprocessor computer operation, specifically efficient operation of multiprocessor computers using overset grids.
The overset grid approach for computing field simulations around geometrically complex configurations has been widely used since its inception in the early 1970s. The overset grid approach is attractive because a complex geometry can be divided into its inherently simpler parts while maintaining the overall complex geometry. Each part can then be gridded separately, a less complicated process than gridding the entire complex geometry. The grid can be computationally re-combined in a solver to yield a smooth solution within and across each grid domain. The overset grid approach has continued to mature in the serial computing environment, for example, seeing use in well-known compressible and incompressible Navier-Stokes flow solvers.
An overset grid application typically begins with a background grid. The background grid can cover the whole problem space. Other grids covering portions of the problem space can also be defined. For example, a fine grid can be defined covering a portion of the problem space where higher resolution is desired. The background and other grids can each be called an “overset grid”.
FIG. 1
illustrates these concepts. Overset grid G
1
encompasses a problem space and corresponds to simulation of phenomena throughout the problem space. Overset grid G
2
encompasses a region of the problem space near object J where higher resolution simulation is required. Interpolation transformations (not shown) allow values from one overset grid (for example, G
1
) to be used to establish values in the other overset grid (for example, G
2
), assuring that the simulation is consistent across both overset grids G
1
, G
2
. Overset grid G
2
allows high resolution where high resolution is required, while overset grid G
1
allows low resolution (and consequently low execution time) where low resolution is acceptable.
In operation, a computer determines values for points in a first overset grid. Boundary conditions for a second overset grid can be determined by interpolating selected values from the first overset grid or from other overset grids. The computer then determines values for the other points in the second overset grid. Selected values from the second overset grid can then be used in interpolations to determine boundary conditions for other overset grids. The process can repeat until a terminal condition is reached, such as, for example, convergence of a simulation.
Overset grid applications are well-suited for problems where varying resolution or varying problem complexity indicate different grids. Unfortunately, overset grids have not fared well on multiprocessor computers. The wide range of possible overset grid sizes can lead to poor load balance, limiting the multiprocessor computer's performance. Also, communication and interpolation of boundary conditions can be problematic when overset grids are subdivided amongst multiple processors.
Accordingly, there is a need for a multiprocessor computer overset grid method and apparatus that maintains substantial load balance and efficient communication and interpolation of boundary conditions in overset grid applications.
SUMMARY OF THE INVENTION
The present invention provides a multiprocessor computer overset grid method and apparatus that maintains substantial load balance and efficient communication and interpolation of boundary conditions in overset grid applications. The present method comprises associating points in each overset grid with processors and using mapped interpolation transformations to communicate intermediate values between processors associated with base and target points of the interpolation transformations.
Each point in each overset grid is first associated with a processor. An initial overset grid is then selected, and values for points in the initial overset grid are determined (for example, by computational simulation of physical phenomena). A second overset grid is then selected. Values can then be determined for points in the second overset grid that are target points of interpolation transformations from base points in the initial overset grid. Values can then be determined for the remaining points in the second overset grid. The process can be repeated, using the second overset grid as the initial overset grid, until a terminal condition is reached.
Static load balance can be fostered in the association of overset grid points with processors. Each overset grid can have a certain number of points assigned to each of the processors, for example, each processor can be assigned a substantially equal number of points from each overset grid if the workload associated with the points is substantially similar. Each processor will consequently have substantially the same workload during operation, assuring effective load balance. Additionally, the points in each overset grid can be assigned to processors to maximize efficiency, for example, by minimizing the surface area to volume ratio of each processor's assigned points if communication costs are of concern.
Advantages and novel features will become apparent to those skilled in the art upon examination of the following description or may be learned by practice of the invention. The objects and advantages of the invention may be realized and attained by means of the instrumentalities and combinations particularly pointed out in the appended claims.
REFERENCES:
patent: 5371852 (1994-12-01), Attanasio et al.
Silver et al., D. Tracking and Visualizing Turbulent 3D Features, IEEE Transactions on Visualization and Computer Graphics, vol. 3, No. 2, pp. 129-141.*
Blake et al., D.C. Electromagnetic Scattering Simulations Using Overset Grids on Massively Parallel Computing Platforms, Antennas and Propagation Society International Symposium, IEEE, 1997, pp. 106-109, Jan. 1997.*
Barnard et al., S. Large-Scale Distributed Computational Fluid Dynamics on the Information Power Grid Using Globus, The Seventh Symposium on the Frontiers of Massively Parallel Computation, Frontier's '99, 1999, pp. 60-67, Jan. 1999.*
Biswas et al., R. Portable Parallel Programming for the Dynamic Load Balancing of Unstructured Grid Applications, 13th International and 10th Symposium on Parallel and Distributed Processing, 1999, IPPS/SPDP Proceedings, pp. 338-342, Jan. 1999.*
Minyard et al., T. Partitioning and Dynamic Load Balancing of Adaptive Hybrid Grids for Large-Scale Turbulent Flow Simulations, Proceedings of the 29th Hawaii International Conference on System Sciences, 1996, pp. 575-584, Jan. 1996.*
Van Driessche et al., R. Dynamic Load Balancing with an Improved Spectral Bisection Algorithm, Proceedings of the Scalable High-Performance Computing Conference, 1994, pp. 494-500, Aug. 1994.*
Daniel W. Barnette,A User's Guide for Breakup: a Computer Code for Parallelizing the Overset Grid Approach, Sandia National Laboratory SAND Report, Mar. 1998.
N. E. Suhs and R. W. Tramel,Pegsus 4.0 User's Manual, Nov. 1991, Final Report for Period Mar. 1, 1990 through Jun. 30, 1991, AEDC-TR-91-8.
S. E. Rogers, D. Kwak, C. Kiris,Steady and Unsteady Solutions of the Incompressible Navier-Stokes Equations, AIAA Journal, vol. 29, No. 4, Apr. 1991, pp. 603-610.
Barnette Daniel W.
Ober Curtis C.
Frejd Russell
Grafe V. Gerald
Libman George H.
Sandia Corporation
LandOfFree
Multiprocessor computer overset grid method and apparatus does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Multiprocessor computer overset grid method and apparatus, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multiprocessor computer overset grid method and apparatus will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3181324