×

zbMATH — the first resource for mathematics

A scalable RBF-FD method for atmospheric flow. (English) Zbl 1349.86014
Summary: Radial basis function-generated finite difference (RBF-FD) methods have recently been proposed as very interesting for global scale geophysical simulations, and have been shown to outperform established pseudo-spectral and discontinuous Galerkin methods for shallow water test problems. In order to be competitive for very large scale simulations, the RBF-FD methods needs to be efficiently implemented for modern multicore based computer architectures. This is a challenging assignment, because the main computational operations are unstructured sparse matrix-vector multiplications, which in general scale poorly on multicore computers due to bandwidth limitations. However, with the task parallel implementation described here we achieve 60-100% of theoretical speedup within a shared memory node, and 80-100% of linear speedup across nodes. We present results for global shallow water benchmark problems with a 30 km resolution.

MSC:
86-08 Computational methods for problems pertaining to geophysics
65M06 Finite difference methods for initial value and initial-boundary value problems involving PDEs
76M20 Finite difference methods applied to problems in fluid mechanics
86A10 Meteorology and atmospheric physics
PDF BibTeX Cite
Full Text: DOI
References:
[1] Augonnet, C.; Thibault, S.; Namyst, R.; Wacrenier, P.-A., Starpu: a unified platform for task scheduling on heterogeneous multicore architectures, Concurr. Comput., Pract. Exp., 23, 2, 187-198, (2011)
[2] Baumgardner, J. R.; Frederickson, P. O., Icosahedral discretization of the two-sphere, SIAM J. Numer. Anal., 22, 6, 1107-1115, (1985) · Zbl 0601.65084
[3] Bayona, V.; Moscoso, M.; Carretero, M.; Kindelan, M., RBF-FD formulas and convergence properties, J. Comput. Phys., 229, 22, 8281-8295, (2010) · Zbl 1201.65038
[4] Bayona, V.; Moscoso, M.; Kindelan, M., Gaussian RBF-FD weights and its corresponding local truncation errors, Eng. Anal. Bound. Elem., 36, 9, 1361-1369, (2012) · Zbl 1352.65560
[5] Bayona, V.; Moscoso, M.; Kindelan, M., Optimal variable shape parameter for multiquadric based RBF-FD method, J. Comput. Phys., 231, 6, 2466-2481, (2012) · Zbl 1429.65267
[6] Bollig, E. F.; Flyer, N.; Erlebacher, G., Solution to PDEs using radial basis function finite-differences (RBF-FD) on multiple gpus, J. Comput. Phys., 231, 21, 7133-7151, (2012)
[7] Buttari, A.; Langou, J.; Kurzak, J.; Dongarra, J., A class of parallel tiled linear algebra algorithms for multicore architectures, Parallel Comput., 35, 1, 38-53, (2009)
[8] Davydov, O.; Oanh, D. T., Adaptive meshless centres and RBF stencils for Poisson equation, J. Comput. Phys., 230, 2, 287-304, (2011) · Zbl 1207.65136
[9] Davydov, O.; Oanh, D. T., On optimal shape parameter for Gaussian RBF-FD approximation of Poisson equation, Comput. Math. Appl., 62, 2143-2161, (2011) · Zbl 1231.65199
[10] Ding, H.; Shu, C.; Tang, D. B., Error estimates of local multiquadric-based differential quadrature (LMQDQ) method through numerical experiments, Int. J. Numer. Methods Eng., 63, 11, 1513-1529, (2005) · Zbl 1089.65119
[11] Divo, E.; Kassab, A. J., An efficient localized radial basis function meshless method for fluid flow and conjugate heat transfer, J. Heat Transf., 129, 2, 124-136, (2006)
[12] Driscoll, T. A.; Fornberg, B., Interpolation in the limit of increasingly flat radial basis functions, Comput. Math. Appl., 43, 3-5, 413-422, (2002) · Zbl 1006.65013
[13] Duran, A.; Ayguadé, E.; Badia, R. M.; Labarta, J.; Martinell, L.; Martorell, X.; Planas, J., Ompss: a proposal for programming heterogeneous multi-core architectures, Parallel Process. Lett., 21, 2, 173-193, (2011)
[14] Erlebacher, G.; Saule, E.; Flyer, N.; Bollig, E., Acceleration of derivative calculations with application to radial basis function: finite-differences on the intel mic architecture, (Proceedings of the 28th ACM International Conference on Supercomputing, ICS ’14, (2014), ACM New York, NY, USA), 263-272
[15] Flyer, N.; Fornberg, B., Radial basis functions: developments and applications to planetary scale flows, Comput. Fluids, 46, 1, 23-32, (2011) · Zbl 1272.65078
[16] Flyer, N.; Lehto, E., Rotational transport on a sphere: local node refinement with radial basis functions, J. Comput. Phys., 229, 6, 1954-1969, (2010) · Zbl 1303.76128
[17] Flyer, N.; Lehto, E.; Blaise, S.; Wright, G. B.; St-Cyr, A., A guide to RBF-generated finite differences for nonlinear transport: shallow water simulations on a sphere, J. Comput. Phys., 231, 11, 4078-4095, (2012) · Zbl 1394.76078
[18] Flyer, N.; Wright, G. B., Transport schemes on a sphere using radial basis functions, J. Comput. Phys., 226, 1, 1059-1084, (2007) · Zbl 1124.65097
[19] Flyer, N.; Wright, G. B., A radial basis function method for the shallow water equations on a sphere, Proc. R. Soc. Lond., Ser. A, Math. Phys. Eng. Sci., 465, 2106, 1949-1976, (2009) · Zbl 1186.76664
[20] Fornberg, B.; Larsson, E.; Flyer, N., Stable computations with Gaussian radial basis functions, SIAM J. Sci. Comput., 33, 2, 869-892, (2011) · Zbl 1227.65018
[21] Fornberg, B.; Lehto, E., Stabilization of RBF-generated finite difference methods for convective pdes, J. Comput. Phys., 230, 2270-2285, (2011) · Zbl 1210.65154
[22] Fornberg, B.; Lehto, E.; Powell, C., Stable calculation of Gaussian-based RBF-FD stencils, Comput. Math. Appl., 65, 4, 627-637, (2013) · Zbl 1319.65011
[23] Fornberg, B.; Piret, C., A stable algorithm for flat radial basis functions on a sphere, SIAM J. Sci. Comput., 30, 1, 60-80, (2007) · Zbl 1159.65307
[24] Fornberg, B.; Wright, G., Stable computation of multiquadric interpolants for all values of the shape parameter, Comput. Math. Appl., 48, 5-6, 853-867, (2004) · Zbl 1072.41001
[25] Galewsky, J.; Scott, R.; Polvani, L., An initial-value problem for testing numerical models of the global shallow-water equations, Tellus A, 56, 5, 429-440, (2004)
[26] Kosec, G.; Šarler, B., Solution of thermo-fluid problems by collocation with local pressure correction, Int. J. Numer. Methods Heat Fluid Flow, 18, 7/8, 868-882, (2008)
[27] Kosec, G.; Trobec, R.; Depolli, M.; Rashkovska, A., Multicore parallelization of a meshless PDE solver with openmp, (Haase, G.; Liebmann, M., Parallel Numerics, vol. 11, Leibnitz, Austria, (2011)), 58-69
[28] Kurzak, J.; Dongarra, J., Implementing linear algebra routines on multi-core processors with pipelining and a look ahead, (Kågström, B.; Elmroth, E.; Dongarra, J.; Waśniewski, J., Applied Parallel Computing. State of the Art in Scientific Computing, Lecture Notes in Computer Science, vol. 4699, (2007), Springer Berlin, Heidelberg), 147-156
[29] Larsson, E.; Fornberg, B., Theoretical and computational aspects of multivariate interpolation with increasingly flat radial basis functions, Comput. Math. Appl., 49, 1, 103-130, (2005) · Zbl 1074.41012
[30] Larsson, E.; Lehto, E.; Heryudono, A.; Fornberg, B., Stable computation of differentiation matrices and scattered node stencils based on Gaussian radial basis functions, SIAM J. Sci. Comput., 35, 4, A2096-A2119, (2013) · Zbl 1362.65026
[31] Lee, Y. J.; Yoon, G. J.; Yoon, J., Convergence of increasingly flat radial basis interpolants to polynomial interpolants, SIAM J. Math. Anal., 39, 2, 537-553, (2007) · Zbl 1132.41303
[32] Persson, P.-O.; Strang, G., A simple mesh generator in Matlab, SIAM Rev., 46, 2, 329-345, (2004) · Zbl 1061.65134
[33] Schaback, R., Multivariate interpolation by polynomials and radial basis functions, Constr. Approx., 21, 3, 293-317, (2005) · Zbl 1076.41003
[34] Shu, C.; Ding, H.; Yeo, K. S., Local radial basis function-based differential quadrature method and its application to solve two-dimensional incompressible Navier-Stokes equations, Comput. Methods Appl. Mech. Eng., 192, 941-954, (2003) · Zbl 1025.76036
[35] Tillenius, M., Leveraging multicore processors for scientific computing, (Sep. 2012), Department of Information Technology, Uppsala University, Licentiate thesis
[36] Tillenius, M., Superglue: a shared memory framework using data-versioning for dependency-aware task-based parallelization, (Apr. 2014), Department of Information Technology, Uppsala University, Tech. Rep. 2014-010
[37] Tillenius, M.; Larsson, E., An efficient task-based approach for solving the n-body problem on multicore architectures, (PARA 2010: State of the Art in Scientific and Parallel Computing, (2010), University of Iceland Reykjavík), 4 pp
[38] Tillenius, M.; Larsson, E.; Badia, R. M.; Martorell, X., Resource-aware task scheduling, ACM Trans. Embed. Comput. Syst., 14, 1, (2015), 25 pp
[39] Tillenius, M.; Larsson, E.; Lehto, E.; Flyer, N., A task parallel implementation of a scattered node stencil-based solver for the shallow water equations, (Proc. 6th Swedish Workshop on Multi-Core Computing, (2013), Halmstad University Halmstad, Sweden), 33-36
[40] Tolstykh, A. I., On using RBF-based differencing formulas for unstructured and mixed structured-unstructured grid calculations, (Proceedings of the 16th IMACS World Congress on Scientific Computation, Applied Mathematics and Simulation, Lausanne, Switzerland, (2000)), 6 pp
[41] Williamson, D. L.; Drake, J. B.; Hack, J. J.; Jakob, R.; Swarztrauber, P. N., A standard test set for numerical approximations to the shallow water equations in spherical geometry, J. Comput. Phys., 102, 1, 211-224, (1992) · Zbl 0756.76060
[42] Womersley, R. S.; Sloan, I. H., How good can polynomial interpolation on the sphere be?, Adv. Comput. Math., 14, 3, 195-226, (2001) · Zbl 0980.41003
[43] Womersley, R. S.; Sloan, I. H., Interpolation and cubature on the sphere, (2003), website · Zbl 0952.65013
[44] Wright, G. B., Radial basis function interpolation: numerical and analytical developments, (2003), University of Colorado Boulder, Ph.D. thesis
[45] Wright, G. B.; Flyer, N.; Yuen, D. A., A hybrid radial basis function-pseudospectral method for thermal convection in a 3-d spherical shell, Geochem. Geophys. Geosyst., 11, 7, Q07003, (2010)
[46] Wright, G. B.; Fornberg, B., Scattered node compact finite difference-type formulas generated from radial basis functions, J. Comput. Phys., 212, 1, 99-123, (2006) · Zbl 1089.65020
[47] Zafari, A.; Tillenius, M.; Larsson, E., Programming models based on data versioning for dependency-aware task-based parallelisation, (Proc. 15th International Conference on Computational Science and Engineering, (2012), IEEE Computer Society), 275-280
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.