Partitioning of Structured Adaptive Grid Hierarchies

Johan Steensland
Sandia National Laboratories

Funded by : Mathematics, Information and Computer Science Division and
ASCI Problem Solving Environments

Project Description

This project aims at decreasing execution time for large-scale structured adaptive mesh refinement (SAMR) applications executing on general parallel computers. Both in academia and industry, computer simulations of physical phenomena are becoming increasingly popular as they constitute an important complement to real-life testing. Often, such simulations are based on solving partial differential equations by numerical methods. Adaptive methods are crucial to efficiently use computer resources such as memory and CPU. But even with adaptation, the simulations are computationally demanding and yield huge data sets. Thus, parallelization is a necessity, demanding the next level of wise resource utilization --- the partitioning of data. Adaptation causes the workload to change dynamically, calling for dynamic (re-) partitioning to maintain efficient resource utilization.
Figure 1: The conceptual meta-partitioner incorporating an absolute and continuous classification space. The most appropriate partitioner is selected and configured, based on the current application and system state.
Structured adaptive mesh refinement (SAMR) methods for the numerical solution of partial differential equations yield highly advantageous ratios for cost/accuracy as compared to methods based on static uniform approximations. These techniques are being effectively used in many domains including computational fluid dynamics, numerical relativity, astrophysics, subsurface modeling and oil reservoir simulation. Distributed implementations of these methods however, lead to significant challenges in dynamic data-distribution, load-balancing, and runtime management.
Figure 2: Nature+Fable, a partitioning tool implementing the greater part of the involved components of a meta-partitioner, with the goal to provide good scalability for general SAMR applications with deep, complex grid hierarchies executing on general parallel computers.

To enable realistic simulations of critical three-dimensional phenomena, the challenge --- and the goal of this project --- is to enable consistently effective use of all involved resources. Significantly improving the scalability of large structured adaptive mesh refinement (SAMR) applications requires sophisticated capabilities for utilizing the underlying parallel computer's resources in the most efficient way. The meta-partitioner (Figure 1) is a tool providing such capabilities.

The primary motivation for the present project is twofold, viz. (1) No single partitioning technique performs the best for all applications and computer systems, and (2) No established partitioning technique copes efficiently with large-scale SAMR applications with deep grid hierarchies executing on general parallel computers.

We are developing a hybrid partitioner implemented as the software tool Nature+Fable (Figure 2), involving both domain-based and patch-based components. All involved parts are engineered as components conforming to the meta-partitioner. Thus, they are capable of changing behavior to adapt to the dynamics of SAMR applications. Moreover, they are ready to operate in a hierarchical and incremental scheme necessary for supercomputer simulations. Such a scheme localizes communications and avoids costly multi-processor synchronizations and long partitioning times.

Nature+Fable separates homogeneous, un-refined (Hue) and complex, refined (Core) domains of the grid hierarchy and clusters refinement levels into bi-levels. The Hues contain the portions of the grid hierarchy without refinements; consequently they contain only parts of the base grid (refinement level 0). The Cores contain the portions of the grid where refinements are present. The Cores are separated from the Hues in a strictly domain-based fashion, meaning that each Core contains a portion of the base grid and all its overlaid, refined grids. Expert blocking algorithms are used for the Hues. The Cores are subjected to a coarse partitioning, creating ``easy-to-block'' bi-levels. Then the same expert algorithms operating on the Hues are used for these bi-levels.

Contacts

Collaborators

Publications, Theses, Reports, and Presentations

Within the present project:

  • Johan Steensland, A hybrid and flexible data partitioner for paralel SAMR, Advanced Computational Infrastructures for Parallel and Distributed Adaptive Applications, Wiley Book Series on Parallel and Distributed Computing, to appear 2006.
  • Lois Curfman McInnes, Jaideep Ray, Rob Armstrong, Tamara L. Dahlgren, Allen Malony, Boyana Norris, Sameer Shende, Joseph P. Kenny, and Johan Steensland, Computational Quality of Service for Scientific CCA Applications: Composition, Substitution, and Reconfiguration, Technical report, Argone national laboratories, ANL-P1326, 2006.
  • Henrik Johansson and Johan Steensland, A performance characterization of load balancing algorithms for parallel SAMR applications, Technical report 2006-047, Uppsala University, Information techmology, To appear Fall 2006.
  • Johan Steensland, Jaideep Ray, Henrik Johansson, and Ralf Deiterding, An improved bi-level algorithm for partitioning dynamic structured grid hierarchies, Sandia technical report, SAND-2006-2487, May 2006.
  • Johan Steensland, Jaideep Ray, and Ralf Deiterding, An improved bi-level algorithm for partitioning dynamic structured grid hierarchies, Presentation at the SIAM Parallel Processing for Scientific Computing 2006 conference, San Francisco, California.
  • Johan Steensland, Irregular buffer-zone partitioning reducing synchronization cost in SAMR, International Journal of Computational Science and Engineering (IJCSE), InderScience Publishers, special issue, to appear 2006.
  • Johan Steensland and Jaideep Ray, A Partitioner-Centric Model for SAMR Partitioning Trade-Off Optimization: Part I, The International Journal of High Performance Computing Applications, Sage Publications, Volume 19 (2), pp 1--14, Summer 2005.
  • Johan Steensland, Irregular buffer-zone partitioning reducing synchronization cost in SAMR, In the proceedings of The 6th Workshop on Parallel and Distributed Scientific and Engineering Computing (PDSEC-05) held in conjunction with The 19th International Parallel and Distributed Processing Symposium (IPDPS-05). One of the 7 out of 22 papers selected to appear as full papers in a special issue of The International Journal of Computational Science and Engineering (IJCSE).
  • Johan Steensland and Jaideep Ray, Using run-time state to improve scalability of SAMR applications, Presentation at the SIAM SC&E 2005 Conference, Orlando, Florida.
  • Henrik Johansson and Johan Steensland, A Characterization of a Hybrid and Dynamic Partitioner for SAMR Applications, Technical Report 2004-009, Department of Information Technology, Uppsala University, Sweden.
  • Henrik Johansson and Johan Steensland, A Characterization of a Hybrid and Dynamic Partitioner for SAMR Applications, In the proceedings of 16th IASTED International Conference Parallel and Distributed Computing and Systems 2004 (PDCS 2004), Acta Press.
  • Johan Steensland and Jaideep Ray, A Partitioner-Centric Model for SAMR Partitioning Trade-Off Optimization: Part II, Sandia Technical Report SAND2003-8725, 2004.
  • Johan Steensland and Jaideep Ray, A Partitioner-Centric Model for SAMR Partitioning Trade-Off Optimization: Part II, In the proceedings of The 6th International Workshop on High Performance Scientific and Engineering Computing (HPSEC-04), held in conjunction with The 2004 International Conference On Parallel processing (ICPP-04), in Montreal, Canada, Aug. 15-18, 2004.
  • Johan Steensland and Jaideep Ray Partitioning dynamic structured grid hierarchies, Presentation at the SIAM Conference on Parallel Processing for Scientific Computing February 25-27, 2004.
  • Johan Steensland and Jaideep Ray, A Partitioner-Centric Model for SAMR Partitioning Trade-Off Optimization: Part I, In the Proceedings of The Fourth Los Alamos Computer Science Institute Symposium 2003 (LACSI 2003) on CD-Rom.
  • Johan Steensland and Jaideep Ray, A Heuristic Re-Mapping Algorithm Reducing Inter-Level Communication in SAMR Applications , Sandia Technical Report SAND2003-8310, June 2003.
  • Johan Steensland and Jaideep Ray, A Heuristic Re-Mapping Algorithm Reducing Inter-Level Communication in SAMR Applications , In the proceedings of the 15th IASTED International Conference Parallel and Distributed Computing and Systems 2003 (PDCS 2003) volume 2, pages 707--712, ACTA Press, 2003. (Received the Best Paper Award in the area of "Dynamic run-time environments".

Previously published:

  • Johan Steensland, Efficient partitioning of structured dynamic grid hierarchies, Ph D thesis 2002, Uppsala University, IT, Dept of Scientific Computing, Uppsala, Sweden. Uppsala dissertations from the faculty of science and technology 44.
  • Johan Steensland, Sumir Chandra and Manish Parashar, An Application-Centric Characterization of Domain-Based Inverse Space-Filling Curve Partitioners for Parallel SAMR Applications, In Transactions on Parallel and Distributed Systems, IEEE Society Press, Vol. 13, No. 12, pp. 1275-1289, December 2002.
  • Sumir Chandra, Johan Steensland, Julian C Cummings and Manish Parashar, An experimental study of adaptive application sensitive partitioning strategies for SAMR applications. In proceedings of LACSI Symposium 2001, October Santa Fe, NM, USA.
  • Sumir Chandra, Johan Steensland and Manish Parashar, An experimental study of adaptive application sensitive partitioning strategies for SAMR applications. Presented at Super Computing 2001 (SC2001). Judged as Best Research Poster.
  • Johan Steensland, Domain-based partitioners for SAMR applications, Licentiate thesis, IT-series 2001-002, Uppsala University. 2001.
  • Johan Steensland, Dynamic structured grid hierarchy partitioners using space-filling cuves, Technical report, IT-series 2001-002, Uppsala University. 2001.
  • Johan Steensland, VAMPIRE, a brief presentation of the partitioning tool.
  • Johan Steensland, Sumir Chandra, manish Parashar, Characterization of Domain-Based Partitioners for Parallel SAMR Applications, in Proceedings of Parallel and Distributed Computing and Systems (PDCS2000), volume 2, pages 425--430, ACTA Press. 2000.
  • Johan Steensland, Stefan Söderberg, Michael Thuné, Comparison of dynamic load balancing techniques for a parallel SAMR algorithm , in Proceedings of PARA2000, Workshop on Applied Parallel Computing, volume 1947 of LNCS. Springer Verlag.
  • Johan Steensland, Sumir Chandra, Michael Thuné, Manish Parashar, Towards an adaptive meta-partitioner for SAMR applications, submitted to SC2000.