×

A stencil-based implementation of parareal in the C++ domain specific embedded language STELLA. (English) Zbl 1411.65173

Summary: In view of the rapid rise of the number of cores in modern supercomputers, time-parallel methods that introduce concurrency along the temporal axis are becoming increasingly popular. For the solution of time-dependent partial differential equations, these methods can add another direction for concurrency on top of spatial parallelization. The paper presents an implementation of the time-parallel Parareal method in a C++ domain specific language for stencil computations (STELLA). STELLA provides both an OpenMP and a CUDA backend for a shared memory parallelization, using the CPU or GPU inside a node for the spatial stencils. Here, we intertwine this node-wise spatial parallelism with the time-parallel Parareal. This is done by adding an MPI-based implementation of Parareal, which allows us to parallelize in time across nodes. The performance of Parareal with both backends is analyzed in terms of speedup, parallel efficiency and energy-to-solution for an advection-diffusion problem with a time-dependent diffusion coefficient.

MSC:

65Y05 Parallel numerical computation
65L05 Numerical methods for initial value problems involving ordinary differential equations
65M20 Method of lines for initial value and initial-boundary value problems involving PDEs
65Y10 Numerical algorithms for specific classes of architectures

Software:

PARAEXP; STELLA
PDFBibTeX XMLCite
Full Text: DOI arXiv Link

References:

[1] Horton, G.; Vandewalle, S.; Worley, P., An algorithm with polylog parallel complexity for solving parabolic partial differential equations, SIAM J. Sci. Comput., 16, 3, 531-541 (1995), URL <http://dx.doi.org/10.1137/0916034> · Zbl 0827.65094
[2] Nievergelt, J., Parallel methods for integrating ordinary differential equations, Commun. ACM, 7, 12, 731-733 (1964), URL <http://dx.doi.org/10.1145/355588.365137> · Zbl 0134.32804
[3] Miranker, W. L.; Liniger, W., Parallel methods for the numerical integration of ordinary differential equations, Math. Comput., 21, 99, 303-320 (1967), URL <http://dx.doi.org/10.1090/S0025-5718-1967-0223106-8> · Zbl 0155.47204
[4] Hackbusch, W., Parabolic multi-grid methods, Comput. Methods Appl. Sci. Eng., VI, 189-197 (1984), URL <http://dl.acm.org/citation.cfm?id=4673.4714> · Zbl 0565.65062
[5] Horton, G., The time-parallel multigrid method, Commun. Appl. Numer. Methods, 8, 9, 585-595 (1992), URL <http://dx.doi.org/10.1002/cnm.1630080906> · Zbl 0757.76038
[6] Kiehl, M., Parallel multiple shooting for the solution of initial value problems, Parallel Comput., 20, 3, 275-295 (1994), URL <http://dx.doi.org/10.1016/S0167-8191(06)80013-X> · Zbl 0798.65079
[7] Lions, J.-L.; Maday, Y.; Turinici, G., A parareal in time discretization of PDE’s, C. R. Acad. Sci. - Ser. I - Math., 332, 661-668 (2001), URL <http://dx.doi.org/10.1016/S0764-4442(00)01793-6> · Zbl 0984.65085
[8] Farhat, C.; Chandesris, M., Time-decomposed parallel time-integrators: theory and feasibility studies for fluid, structure, and fluid-structure applications, Int. J. Numer. Methods Eng., 58, 9, 1397-1434 (2003), URL <http://dx.doi.org/10.1002/nme.860> · Zbl 1032.74701
[9] Christlieb, A. J.; Macdonald, C. B.; Ong, B. W., Parallel high-order integrators, SIAM J. Sci. Comput., 32, 2, 818-835 (2010), URL <http://dx.doi.org/10.1137/09075740X> · Zbl 1211.65089
[10] Christlieb, A. J.; Haynes, R. D.; Ong, B. W., A parallel space-time algorithm, SIAM J. Sci. Comput., 34, 5, C233-C248 (2012), URL <http://dx.doi.org/10.1137/110843484> · Zbl 1259.65143
[11] Minion, M. L., A hybrid parareal spectral deferred corrections method, Commun. Appl. Math. Comput. Sci., 5, 2, 265-301 (2010), URL <http://dx.doi.org/10.2140/camcos.2010.5.265> · Zbl 1208.65101
[12] Emmett, M.; Minion, M. L., Toward an efficient parallel in time method for partial differential equations, Commun. Appl. Math. Comput. Sci., 7, 105-132 (2012), URL <http://dx.doi.org/10.2140/camcos.2012.7.105> · Zbl 1248.65106
[13] Arbenz, P.; Hiltebrand, A.; Obrist, D., A parallel space-time finite difference solver for periodic solutions of the shallow-water equation, (Wyrzykowski, R.; Dongarra, J.; Karczewski, K.; Waśniewski, J., Parallel Processing and Applied Mathematics. Parallel Processing and Applied Mathematics, Lecture Notes in Computer Science, vol. 7204 (2012), Springer: Springer Berlin Heidelberg), 302-312, URL <http://dx.doi.org/10.1007/978-3-642-31500-8_31>
[14] Arbenz, P.; Hupp, D.; Obrist, D., A parallel solver for the time-periodic Navier-Stokes equations, (Wyrzykowski, R.; Dongarra, J.; Karczewski, K.; Waśniewski, J., Parallel Processing and Applied Mathematics. Parallel Processing and Applied Mathematics, Lecture Notes in Computer Science (2014), Springer: Springer Berlin Heidelberg), 291-300, URL <http://dx.doi.org/10.1007/978-3-642-55195-6_27>
[18] Bal, G.; Maday, Y., A parareal time discretization for non-linear PDE’s with application to the pricing of an american put, (Pavarino, L.; Toselli, A., Recent Developments in Domain Decomposition Methods. Recent Developments in Domain Decomposition Methods, Lecture Notes in Computational Science and Engineering, vol. 23 (2002), Springer: Springer Berlin), 189-202, <http://dx.doi.org/10.1007/978-3-642-56118-4_12> · Zbl 1022.65096
[19] Maday, Y.; Turinici, G., Parallel in time algorithms for quantum control: parareal time discretization scheme, Int. J. Quant. Chem., 93, 3, 223-228 (2003), URL <http://dx.doi.org/10.1002/qua.10554>
[20] Samaddar, D.; Newman, D. E.; Sánchez, R. S., Parallelization in time of numerical simulations of fully-developed plasma turbulence using the parareal algorithm, J. Comput. Phys., 229, 6558-6573 (2010), URL <http://dx.doi.org/10.1016/j.jcp.2010.05.012> · Zbl 1425.76090
[21] Bal, G., On the convergence and the stability of the parareal algorithm to solve partial differential equations, (Kornhuber, R.; etal., Domain Decomposition Methods in Science and Engineering. Domain Decomposition Methods in Science and Engineering, Lecture Notes in Computational Science and Engineering, vol. 40 (2005), Springer: Springer Berlin), 426-432, URL <http://dx.doi.org/10.1007/3-540-26825-1_43> · Zbl 1066.65091
[22] Staff, G. A.; Rnquist, E. M., Stability of the parareal algorithm, (Kornhuber, R.; etal., Domain Decomposition Methods in Science and Engineering. Domain Decomposition Methods in Science and Engineering, Lecture Notes in Computational Science and Engineering, vol. 40 (2005), Springer: Springer Berlin), 449-456, URL <http://dx.doi.org/10.1007/3-540-26825-1_46> · Zbl 1066.65079
[23] Gander, M. J.; Vandewalle, S., Analysis of the parareal time-parallel time-integration method, SIAM J. Sci. Comput., 29, 2, 556-578 (2007), URL <http://dx.doi.org/10.1137/05064607X> · Zbl 1141.65064
[24] Reynolds-Barredo, J.; Newman, D.; Sanchez, R.; Samaddar, D.; Berry, L.; Elwasif, W., Mechanisms for the convergence of time-parallelized, parareal turbulent plasma simulations, J. Comput. Phys., 231, 23, 7851-7867 (2012), URL <http://dx.doi.org/10.1016/j.jcp.2012.07.028>
[26] Farhat, C.; Cortial, J.; Dastillung, C.; Bavestrello, H., Time-parallel implicit integrators for the near-real-time prediction of linear structural dynamic responses, Int. J. Numer. Methods Eng., 67, 697-724 (2006), URL <http://dx.doi.org/10.1002/nme.1653> · Zbl 1113.74023
[27] Gander, M.; Petcu, M., Analysis of a Krylov subspace enhanced parareal algorithm for linear problems, ESAIM: Proc., 25, 114-129 (2008), URL <http://dx.doi.org/10.1051/proc:082508> · Zbl 1156.65322
[28] Ruprecht, D.; Krause, R., Explicit parallel-in-time integration of a linear acoustic-advection system, Comput. Fluids, 59, 0, 72-83 (2012), URL <http://dx.doi.org/10.1016/j.compfluid.2012.02.015> · Zbl 1365.76241
[29] Dai, X.; Maday, Y., Stable parareal in time method for first- and second-order hyperbolic systems, SIAM J. Sci. Comput., 35, 1, A52-A78 (2013), URL <http://dx.doi.org/10.1137/110861002> · Zbl 1264.65136
[30] Gander, M.; Güttel, S., Paraexp: a parallel integrator for linear initial-value problems, SIAM J. Sci. Comput., 35, 2, C123-C142 (2013), URL <http://dx.doi.org/10.1137/110856137> · Zbl 1266.65123
[31] Haut, T.; Wingate, B., An asymptotic parallel-in-time method for highly oscillatory PDEs, SIAM J. Sci. Comput., 36, 2, A693-A713 (2014) · Zbl 1321.65131
[32] Trindade, J. M.F.; Pereira, J. C.F., Parallel-in-time simulation of two-dimensional, unsteady, incompressible laminar flows, Numer. Heat Transf., Part B: Fundam., 50, 1, 25-40 (2006), URL <http://dx.doi.org/10.1080/10407790500459379>
[34] Speck, R.; Ruprecht, D.; Krause, R.; Emmett, M.; Minion, M.; Winkel, M.; Gibbon, P., A massively space-time parallel N-body solver, (Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis, SC ’12 (2012), IEEE Computer Society Press: IEEE Computer Society Press Los Alamitos, CA, USA), 92:1-92:11, URL http://dx.doi.org/10.1109/SC.2012.6
[35] Haynes, R. D.; Ong, B. W., MPI-OpenMP algorithms for the parallel space-time solution of time dependent PDEs, (Domain Decomposition Methods in Science and Engineering XXI. Domain Decomposition Methods in Science and Engineering XXI, Lecture Notes in Computational Science and Engineering, vol. 98 (2014), Springer International Publishing), 179-187, URL <http://dx.doi.org/10.1007/978-3-319-05789-7_14> · Zbl 1382.65243
[36] Krause, R.; Ruprecht, D., Hybrid space-time parallel solution of Burgers’ equation, (Domain Decomposition Methods in Science and Engineering XXI. Domain Decomposition Methods in Science and Engineering XXI, Lecture Notes in Computational Science and Engineering, vol. 98 (2014), Springer International Publishing), 647-655, URL <http://dx.doi.org/10.1007/978-3-319-05789-7_62> · Zbl 1382.65246
[37] Barker, A. T., A minimal communication approach to parallel time integration, Int. J. Comput. Math., 1-15 (2013), URL <http://dx.doi.org/10.1080/00207160.2013.800193>
[38] Keyes, D. E., Exaflop/s: the why and the how, C. R. Méc., 339, 23, 70-77 (2011) · Zbl 1221.00058
[39] Fuhrer, O.; Osuna, C.; Lapillonne, X.; Gysi, T.; Cumming, B.; Bianco, M.; Arteaga, A.; Schulthess, T. C.; portable, Towards a. performance, architecture agnostic implementation strategy for weather and climate models, Supercomput. Front. Innov., 1, 1, 45-62 (2014)
[40] Asanovic, K.; Bodik, R.; Demmel, J.; Keaveny, T.; Keutzer, K.; Kubiatowicz, J.; Morgan, N.; Patterson, D.; Sen, K.; Wawrzynek, J.; Wessel, D.; Yelick, K., A view of the parallel computing landscape, Commun. ACM, 52, 56-67 (2009)
[41] Berry, L.; Elwasif, W.; Reynolds-Barredo, J.; Samaddar, D.; Sanchez, R.; Newman, D., Event-based parareal: a data-flow based implementation of parareal, J. Comput. Phys., 231, 17, 5945-5954 (2012), URL <http://dx.doi.org/10.1016/j.jcp.2012.05.016>
[42] Fischer, P. F.; Hecht, F.; Maday, Y., A parareal in time semi-implicit approximation of the Navier-Stokes equations, (Kornhuber, R.; etal., Domain Decomposition Methods in Science and Engineering. Domain Decomposition Methods in Science and Engineering, Lecture Notes in Computational Science and Engineering, vol. 40 (2005), Springer: Springer Berlin), 433-440, URL <http://dx.doi.org/10.1007/3-540-26825-1_44> · Zbl 1309.76060
[46] Speck, R.; Ruprecht, D.; Emmett, M.; Bolten, M.; Krause, R., A space-time parallel solver for the three-dimensional heat equation, (Parallel Computing: Accelerating Computational Science and Engineering (CSE). Parallel Computing: Accelerating Computational Science and Engineering (CSE), Advances in Parallel Computing, vol. 25 (2014), IOS Press), 263-272, URL <http://dx.doi.org/10.3233/978-1-61499-381-0-263>
[47] Dongarra, J. J.; Meuer, H. W.; Strohmaier, E., Top500 supercomputer sites, Supercomputer, 13, 89-111 (1997)
[48] Feng, W.; Cameron, K., The green500 list: encouraging sustainable supercomputing, Computer, 40, 12, 50-55 (2007)
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.