A Partitioner-Centric Model for Structured Adaptive Mesh Refinement Partitioning Trade-Off Optimization: Part I

Abstract

Optimal partitioning of structured adaptive mesh applications necessitates dynamically determining and optimizing for the most time-inhibiting factor, such as load imbalance and communication volume. However, any trivial monitoring of an application evaluates the current partitioning rather than the inherent properties of the grid hierarchy. We present an analytical model that given a structured adaptive grid determines, ab initio, to what extent the partitioner should focus on optimizing load imbalance or communication volume to reduce execution time. This model contributes to the meta-partitioner, able to select and configure the optimal partitioner based on the mesh configuration, the simulation and computer characteristics. We validate the predictions of this model by comparing them with actual measurements (via traces) from four different adaptive simulations. The results show that the proposed model generally captures the inherent optimization-need in structured adaptive mesh refinement applications. We conclude that our model is a useful contribution, since tracking and adapting to the dynamic behavior of such applications potentially lead to a large decrease in execution times.

Keywords

Parallel structured adaptive mesh refinement dynamic partitioning and load balancing

Get full access to this article

View all access options for this article.

References

Baden, S. B. , Kohn, S. R. , and Fink, S. 1994. Programming with LPARX. Technical Report, University of California, San Diego, CA .

Balsara, D. and Norton, C. 2001. Highly parallel structured adaptive mesh refinement using language-based approaches . Journal of Parallel Computing 27: 37–70 .

Berger, M. J. and Colella, P. 1989. Local adaptive mesh refinement for shock hydrodynamics . Journal of Computational Physics 82: 64–84 .

Berger, M. J. and Oliger, J. 1984. Adaptive mesh refinement for hyperbolic partial differential equations . Journal of Computational Physics 53: 484–512 .

Berger, M. et al. 1983. Adaptive mesh refinement for onedimensional gas dynamics . Scientific Computing, 17: 43–47 .

Chandra, S. 2002. ARMaDA: a framework for adaptive application-sensitive run-time management of dynamic applications. Master's Thesis, Graduate School, Rutgers University, NJ.

Chandra, S. , Steensland, J. , and Parashar, M. 2001. An experimental study of adaptive application sensitive partitioning strategies for SAMR applications . Proceedings of Supercomputing 2001, Denver, CO, November, research poster presentation.

Choptuik, M. W. 1989. Experiences with an adaptive mesh refinement algorithm in numerical relativity. Frontiers in Numerical Relativity, C. R. Evans , L. S. Finn , and D. W. Hobill , editors, Cambridge University Press, Cambridge , pp. 206–221.

Fink, S. J. , Baden, S. B. , and Kohn, S. R. 1996. Flexible communication mechanisms for dynamic structured applications . Proceedings of the 3rd International Workshop on Parallel Algorithms for Irregularly Structured Problems (IRREGULAR '96),Santa Barbara, CA, August 19–21.

10.

Lan, Z. , Taylor, V. , and Bryan, G. 2001a. Dynamic load balancing for structured adaptive mesh refinement applications . Proceedings of the 2001 International Conference on Parallel Processing (ICPP 2001), Valencia, Spain, September.

11.

Lan, Z. , Taylor, V. , and Bryan, G. 2001b. Dynamic load balancing of SAMR applications on distributed systems . Proceedings of Supercomputing 2001, Denver, CO, November.

12.

Li, X. and Parashar, M. 2004. Hierarchical partitioning techniques for structured adaptive mesh refinement applications . Journal of Supercomputing, Kluwer Academic Publishers, Vol. 28(3), pp. 265-278 , 2004.

13.

MacNeice, P. , Olson, K. M. , Mobarry, C. , de Fainchtein, R. , and Packer, C. 2000. PARAMESH: a parallel adaptive mesh refinement community toolkit . Computer Physics Communications 126: 330–354 .

14.

Norman, M. and Bryan, G. 1998. Cosmological adaptive mesh refinement. Numerical Astrophysics 1998, S. Miyama and K. Tomisaka , editors, Tokyo, Japan, March 10–13.

15.

Parashar, M. and Browne, J. 2000. System engineering for high performance computing software: the HDDA/DAGH infrastructure for implementation of parallel structured adaptive mesh refinement. IMA Volume on Structured Adaptive Mesh Refinement (SAMR) Grid Methods, pp. 1–18.

16.

Parker, S. G. 2002. A component-based architecture for parallel multi-physics PDE simulations . Proceedings of the International Conference on Computational Science (ICCS 2002), Amsterdam, the Netherlands, April, Lecture Notes in Computer Science, Vol. 2331, Springer-Verlag, Berlin, pp. 719–734 .

17.

Rantakokko, J. 1998. Data Partitioning Methods and Parallel Block-Oriented PDE Solvers. Ph.D. Thesis, Uppsala University.

18.

Schloegel, K. , Karypis, G. , and Kumar, V. 1997. Multilevel diffusion schemes for repartitioning of adaptive meshes. Technical Report 97-013, Department of Computer Science, University of Minnesota, Minneapolis, MN .

19.

Shee, M. 2000. Evaluation and optimization of load balancing/distribution techniques for adaptive grid hierarchies. M.S. Thesis, Graduate School, Rutgers University, NJ (http://www.caip.rutgers.edu/TASSL/Thesis/msheethesis.pdf).

20.

Steensland, J. 2002. Efficient partitioning of dynamic structured grid hierarchies. Ph.D. Thesis, Uppsala University.

21.

Steensland, J. and Ray, J. 2003. A heuristic remapping algorithm reducing interlevel communication in SAMR applications . Proceedings of the 15th IASTED International Conference on Parallel and Distributed Computing and Systems PDCS03, Reno NV, August, Vol. 2, pp. 707–712 .

22.

Steensland, J. , Chandra, S. , and Parashar, M. 2002. An application-centric characterization of domain-based SFC partitioners for parallel SAMR . IEEE Transactions on Parallel and Distributed Systems 13(12): 1275–1289 .

23.

Steinthorsson, E. and Modiano, D. 1995. Advanced methodology for simulation of complex flows using structured grid systems, its Surface Modeling, Grid Generation, and Related Issues in Computational Fluid Dynamic (CFD) Solutions, pp 697–710.

24.

Thune, M. 1997. Partitioning strategies for composite grids . Parallel Algorithms and Applications 11: 325–348 .

25.

Wang, P. , Yotov, I. , Arbogast, T. , Dawson, C. , Parashar, M. , and Sepehrnoori, K. 1997. A new generation EOS compositional reservoir simulator: Part I – formulation and discretization . Proceedings of the Society of Petroleum Engineerings Reservoir Simulation Symposium, Dallas, TX, June.

26.

Wissink, A. M. et al. 2001. Large-scale parallel structured AMR calculations using the SAMRAI framework . Proceedings of Supercomputing 2001, Denver, CO, November.