DOI: https://doi.org/10.26089/NumMet.v20r108

Load balancing using Hilbert space-filling curves for parallel shallow water simulations

Authors

  • A.V. Chaplygin
  • N.A. Diansky
  • A.V. Gusev

Keywords:

shallow water equations
domain decomposition method
parallel computing
load balancing
Hilbert space-filling curves

Abstract

This paper presents a method of load balancing using Hilbert space-filling curves applied to a parallel algorithm for solving shallow water equations. We consider the system of shallow water equations in the form presented in the ocean general circulation sigma-model INMOM (Institute of Numerical Mathematics Ocean Model). This system of equations is one of the basic blocks of the model. Due to land points in the computational grid, the load balancing is an especially urgent task. The method of load balancing using Hilbert space-filling curves is chosen as one of such methods. The paper demonstrates the greater efficiency of this method in comparison with the uniform partitioning without load balancing. It is shown that this method is a good alternative to the METIS standard library. Moreover, the optimality of the implemented partition for the shallow water equations exactly corresponds to the optimality for the INMOM three-dimensional sigma-model due to the same number of vertical levels in the entire computational domain.

New computational technologies

Downloads

Published

2019-03-10

Issue

Vol. 20 (2019): Issue 1.

Section

Section 1. Numerical methods and applications

Author Biographies

A.V. Chaplygin

Lomonosov Moscow State University
• Student

N.A. Diansky

Lomonosov Moscow State University,
Faculty of Physics
• Chief Researcher

A.V. Gusev

Institute of Numerical Mathematics of RAS (INM RAS)
• Senior Researcher

References

  1. N. A. Diansky, Modeling of Ocean Circulation and Analysis of Its Reaction on Short- and Long-Term Atmospheric Effects (Fizmatlit, Moscow, 2013) [in Russian].
  2. A. V. Chaplygin, “Parallel Implementation of the INMOM General Model of Ocean Circulation,” in Collection of the Best Qualification Works in the Faculty of Computational Mathematics and Cybernetics, Moscow State University (Maks Press, Moscow, 2017), pp. 27-28.
  3. V. B. Sukhov, Solving Some Problems of Modeling the Large-Scale Dynamics of Ocean , Candidate’s Dissertation in Mathematics and Physics (Moscow State Univ., Moscow, 2009).
  4. F. Imamura, A. C. Yalciner, and G. Ozyurt, Tsunami Modelling Manual (TUNAMI Model) (Tohoku Univ. Press, Sendai, Japan, 2006).
  5. P. Roach, Computational Fluid Dynamics (Hermosa Publ., Albuquerque, 1972; Mir, Moscow, 1980).
  6. A. Arakawa and V. R. Lamb, “Computational Design of the Basic Dynamical Processes of the UCLA General Circulation Model,” in Methods in Computational Physics: Advances in Research and Applications (Academic Press, New York, 1977), Vol. 17, pp. 173-265.
  7. F. Mesinger and A. Arakawa, Numerical Methods Used in Atmospheric Models (GAPR Publ., Geneva, 1976), Vol. 1.
  8. G. I. Marchuk, Methods of Numerical Mathematics (Nauka, Moscow, 1989; Springer, New York, 1982).
  9. G. L. Mellor, User’s Guide for a Three-dimensional, Primitive Equation, Numerical Ocean Model (Princeton Univ. Press, Princeton, 1993).
  10. G. Wang, F. Qiao, and C. Xia., “Parallelization of a Coupled Wave-Circulation Model and Its Application,” Ocean Dyn. 60 (2), 331-339 (2010).
  11. A. V. Chaplygin, N. A. Diansky, and A. V. Gusev, “Parallel Modeling of Nonlinear Shallow Water Equation,” in Proc. 60th All-Russia Conf. on Applied Mathematics and Informatics, Moscow Institute of Physics and Technology, Dolgoprudny, Russia, November 20-26, 2017 (Moscow Inst. Phys. Technol., Dolgoprudny, 2017), pp. 192-194.
  12. H. Liu, K. Wang, B. Yang, et al., Load Balancing Using Hilbert Space-Filling Curves for Parallel Reservoir Simulations , arXiv preprint: 1708.01365v1 [cs.DC] (Cornell Univ. Library, Ithaca, 2017), available at
    https://arxiv.org/abs/1708.01365.
  13. J. M. Dennis, “Inverse Space-Filling Curve Partitioning of a Global Ocean Model,” in IEEE Int. Parallel and Distributed Processing Symposium, Rome, Italy, March 26-30, 2007 (IEEE Press, New York, 2007),
    doi 10.1109/IPDPS.2007.370215
  14. H. Sagan, Space-Filling Curves (Springer, New York, 1994).
  15. R. Smith, P. Jones, B. Briegleb, et al., The Parallel Ocean Program (POP) Reference Manual: Ocean Component of the Community Climate System Model (CCSM) and Community Earth System Model.
    http://www.cesm.ucar.edu/models/cesm1.0/pop2/doc/sci/POPRefManual.pdf . Cited February 28, 2019.
  16. T. Wilhelmsson, Parallelization of the HIROMB Ocean Model.
    https://pdfs.semanticscholar.org/ee95/be1a6bb90becdc31c84f83c343ca8daf5bdc.pdf . Cited February 28, 2019.
  17. J. Rantakokko, “A Framework for Partitioning Domains with Inhomogeneous Workload,” Parallel Algorithms Appl. 13 (2), 135-151 (1998).
  18. Vl. V. Voevodin, S. A. Zhumatii, S. I. Sobolev, et al., “Practice of Lomonosov Supercomputer,” Otkrytye Sistemy, No. 7, 36-39 (2012).
  19. G. Karypis, METIS: A Software Package for Partitioning Unstructured Graphs, Partitioning Meshes, and Computing Fill-Reducing Orderings of Sparse Matrices (Univ. of Minnesota, Minneapolis, 2013), Version 5.1.0.
  20. B. van Werkhoven, J. Maassen, M. Kliphuis, et al., “A Distributed Computing Approach to Improve the Performance of the Parallel Ocean Program,” Geosci. Model Dev. 7 (1), 267-281 (2014).
  21. V. V. Fomin, N. A. Dianskii, and A. V. Chaplygin, “Simulation of Extreme Surges in the Taganrog Bay and the Usage of Atmosphere and Ocean Circulation Models of Various Spatial Resolution,” in Proc. VI Int. Conf. on Marine Studies and Education, Moscow, Russia, October 30-November 2, 2017 (PoliPRESS, Tver, 2017),
    https://www.maresedu.com/materials . Cited February 28, 2019.
  22. E. M. Volodin, N. A. Diansky, and A. V. Gusev, “Simulation and Prediction of Climate Changes in the 19th to 21st Centuries with the Institute of Numerical Mathematics, Russian Academy of Sciences, Model of the Earth’s Climate System,” Izv. Akad. Nauk, Fiz. Atmos. Okeana 49 (4), 379-400 (2013) [Izv., Atmos. Ocean. Phys. 49 (4), 347-366 (2013)].
  23. V. V. Fomin and N. A. Diansky, “Simulation of Extreme Surges in the Taganrog Bay with Atmosphere and Ocean Circulation Models,” Meteorol. Gidrol., No. 12, 69-80 (2018) [Russ. Meteorol. Hydrol. 43 (12), 843-851 (2018)].
  24. A. F. Shchepetkin and J. C. McWilliams, “The Regional Oceanic Modeling System (ROMS): A Split-Explicit, Free-Surface, Topography-Following-Coordinate Oceanic Model,” Ocean Model. 9 (4), 347-404 (2005).
  25. K. V. Ushakov, R. A. Ibrayev, and V. V. Kalmykov, “Simulation of the World Ocean Climate with a Massively Parallel Numerical Model,” Izv. Akad. Nauk, Fiz. Atmos. Okeana 51 (4), 416-436 (2015) [Izv., Atmos. Ocean. Phys. 51 (4), 362-380 (2015)].