Task-based adaptive multiresolution for time-space multi-scale reaction-diffusion systems on multi-core architectures. (English) Zbl 1416.65184

Summary: A new solver featuring time-space adaptation and error control has been recently introduced to tackle the numerical solution of stiff reaction-diffusion systems. Based on operator splitting, finite volume adaptive multiresolution and high order time integrators with specific stability properties for each operator, this strategy yields high computational efficiency for large multidimensional computations on standard architectures such as powerful workstations. However, the data structure of the original implementation, based on trees of pointers, provides limited opportunities for efficiency enhancements, while posing serious challenges in terms of parallel programming and load balancing. The present contribution proposes a new implementation of the whole set of numerical methods including Radau5 and ROCK4, relying on a fully different data structure together with the use of a specific library, TBB, for shared-memory, task-based parallelism with work-stealing. The performance of our implementation is assessed in a series of test-cases of increasing difficulty in two and three dimensions on multi-core and many-core architectures, demonstrating high scalability.


65L04 Numerical methods for stiff equations
65Y05 Parallel numerical computation
65M20 Method of lines for initial value and initial-boundary value problems involving PDEs
65M50 Mesh generation, refinement, and adaptive methods for the numerical solution of initial value and initial-boundary value problems involving PDEs
35K57 Reaction-diffusion equations
Full Text: DOI arXiv


[1] A. Abdulle, “Fourth order Chebyshev methods with recurrence relation”, SIAM J. Sci. Comput.23 (2002) no. 6, p. 2041-2054 (electronic) · Zbl 1009.65048
[2] S.B. Baden, N.P. Chrisochoides, D.B. Gannon & M.L. Norman (ed.), Structured adaptive mesh refinement (SAMR) grid methods, The IMA Volumes in Mathematics and its Applications 117, Springer-Verlag, New York, 2000, Papers from the IMA Workshop held at the University of Minnesota, Minneapolis, MN, March 12-13, 1997 · Zbl 0930.00061
[3] D.S. Balsara & C.D. Norton, “Highly parallel structured adaptive mesh refinement using parallel language-based approaches”, Parallel Comput.27 (2001) no. 1-2, p. 37-70 · Zbl 0971.68017
[4] J. Bell, M. Berger, J. Saltzman & M. Welcome, “Three-dimensional adaptive mesh refinement for hyperbolic conservation laws”, SIAM J. Sci. Comput.15 (1994) no. 1, p. 127-138 · Zbl 0793.65072
[5] R.D. Blumofe, C.F. Joerg, B.C. Kuszmaul, C.E. Leiserson, K.H. Randall & Y. Zhou, “Cilk: An efficient multithreaded runtime system”, J. Parallel Distr. Com.37 (1996) no. 1, p. 55-69
[6] R.D. Blumofe & C.E. Leiserson, “Scheduling Multithreaded Computations by Work Stealing”, J. ACM46 (1999) no. 5, p. 720-748 · Zbl 1065.68504
[7] K. Brix, S. Melian, S. Müller & M. Bachmann, Adaptive multiresolution methods: Practical issues on data structures, implementation and parallelization, Summer School on Multiresolution and Adaptive Mesh Refinement Methods, ESAIM Proc. 34, EDP Sci., Les Ulis, 2011, p. 151-183 · Zbl 1302.65219
[8] K. Brix, S.S. Melian, S. Müller & G. Schieffer, Parallelisation of multiscale-based grid adaptation using space-filling curves, in ESAIM: Proc., EDP Sciences, 2009, p. 108-129 · Zbl 1181.65118
[9] C. Burstedde, L. Wilcox & O. Ghattas, “p4est: Scalable Algorithms for Parallel Adaptive Mesh Refinement on Forests of Octrees”, SIAM J. Sci. Comput.33 (2011) no. 3, p. 1103-1133 · Zbl 1230.65106
[10] A. Cohen, S. M. Kaber, S. Müller & M. Postel, “Fully Adaptive Multiresolution Finite Volume Schemes for Conservation Laws”, Math. Comput.72 (2003), p. 183-225 · Zbl 1010.65035
[11] W. Crutchfield & M.L. Welcome, “Object-oriented implementation of adaptive mesh refinement algorithms”, J. Sci. Program. (1993), p. 145-156
[12] W. Dahmen, T. Gotzen, S.S. Melian-Flamand & S. Müller, Numerical Simulation of Cooling Gas Injection using Adaptive Multiscale Techniques, Inst. für Geometrie und Praktische Mathematik, 2011
[13] R. Deiterding, A generic framework for block-structured Adaptive Mesh Refinement in Object-oriented C++, Technical report, available at http://amroc.sourceforge.net, 2003
[14] R. Deiterding, Block-structured adaptive mesh refinement - Theory, implementation and application, Summer School on Multiresolution and Adaptive Mesh Refinement Methods, ESAIM Proc. 34, EDP Sci., Les Ulis, 2011, p. 97-150 · Zbl 1302.65220
[15] S. Descombes, M. Duarte, T. Dumont, F. Laurent, V. Louvet & M. Massot, “Analysis of operator splitting in the nonasymptotic regime for Nonlinear Reaction-Diffusion Equations. Application to the Dynamics of Premixed Flames”, SIAM J. Numer. Anal.52 (2014) no. 3, p. 1311-1334 · Zbl 1320.65080
[16] S. Descombes & T. Dumont, “Numerical simulation of a stroke: Computational problems and methodology”, Prog. Biophys. Mol. Bio.97 (2008) no. 1, p. 40-53
[17] S. Descombes, T. Dumont, V. Louvet & M. Massot, “On the local and global errors of splitting approximations of reaction-diffusion equations with high spatial gradients”, Int. J. Comput. Math.84 (2007) no. 6, p. 749-765 · Zbl 1122.65061
[18] S. Descombes, T. Dumont & M. Massot, Operator splitting for stiff nonlinear reaction-diffusion systems: Order reduction and application to spiral waves, Patterns and waves (Saint Petersburg, 2002), AkademPrint, St. Petersburg, 2003, p. 386-482
[19] S. Descombes & M. Massot, “Operator splitting for nonlinear reaction-diffusion systems with an entropic structure: Singular perturbation and order reduction”, Numer. Math.97 (2004) no. 4, p. 667-698 · Zbl 1060.65105
[20] J. Dreher & R. Grauer, “Racoon: A parallel mesh-adaptive framework for hyperbolic conservation laws”, Parallel Comput.31 (2005) no. 8-9, p. 913-932
[21] M.-A. Dronne, J.-P. Boissel & E. Grenier, “A mathematical model of ion movements in grey matter during a stroke”, J. Theor. Biol.240 (2006) no. 4, p. 599-615
[22] F. Drui, A. Fikl, P. Kestener, S. Kokh, A. Larat, V. Le Chenadec & M. Massot, “Experimenting with the p4est library for AMR simulations of two-phase flows”, ESAIM: Proc. Surv.53 (2016), p. 232-247 · Zbl 1408.76380
[23] M. Duarte, Adaptive numerical methods in time and space for the simulation of multi-scale reaction fronts, Ph. D. Thesis, Ecole Centrale Paris, 2011
[24] M. Duarte, Z. Bonaventura, M. Massot, A. Bourdon, S. Descombes & T. Dumont, “A new numerical strategy with space-time adaptivity and error control for multi-scale streamer discharge simulations”, J. Comput. Phys.231 (2012) no. 3, p. 1002-1019 · Zbl 1406.76063
[25] M. Duarte, S. Descombes, C. Tenaud, S. Candel & M. Massot, “Time-space adaptive numerical methods for the simulation of combustion fronts”, Combust. Flame160 (2013) no. 6, p. 1083-1101
[26] M. Duarte, M. Massot, S. Descombes, C. Tenaud, T. Dumont, V. Louvet & F. Laurent, New resolution strategy for multi-scale reaction waves using time operator splitting and space adaptive multiresolution: Application to human ischemic stroke, Summer School on Multiresolution and Adaptive Mesh Refinement Methods, ESAIM Proc. 34, EDP Sci., Les Ulis, 2011, p. 277-290 · Zbl 1302.65211
[27] M. Duarte, M. Massot, S. Descombes, C. Tenaud, T. Dumont, V. Louvet & F. Laurent, “New resolution strategy for multiscale reaction waves using time operator splitting, space adaptive multiresolution, and dedicated high order implicit/explicit time integrators”, SIAM J. Sci. Comput.34 (2012) no. 1, p. A76-A104 · Zbl 1243.65107
[28] T. Dumont, M. Duarte, S. Descombes, M.-A. Dronne, M. Massot & V. Louvet, “Simulation of human ischemic stroke in realistic 3D geometry”, Commun. Nonlinear Sci. Numer. Simul.18 (2013) no. 6, p. 1539-1557 · Zbl 1322.92019
[29] W. Eckhardt & T. Weinzierl, A Blocking Strategy on Multicore Architectures for Dynamically Adaptive PDE Solvers, in D. Hutchison et al., ed., Parallel Processing and Applied Mathematics, Springer Berlin Heidelberg, 2010, p. 567-575
[30] M. Essadki, S. de Chaisemartin, M. Massot, F. Laurent & A. Larat, “Adaptive mesh refinement and high order geometrical moment method for the simulation of polydisperse evaporating sprays”, Oil Gas Sci. Technol.71 (2016), p. 1-25
[31] C.J. Forster, Parallel wavelet-adaptive direct numerical simulation of multiphase flows with phase change, Ph. D. Thesis, Georgia Institute of Technology, 2016
[32] T. Gautier, J.V.F. Lima, N. Maillard & B. Raffin, XKaapi: A Runtime System for Data-Flow Task Programming on Heterogeneous Architectures, in Parallel Distributed Processing (IPDPS), 2013 IEEE 27th International Symposium on, 2013, p. 1299-1308
[33] P. Gray & S.K. Scott, Chemical Oscillations and Instabilities: Non-linear Chemical Kinetics, International Series of Monographs on Chemistry 21, Oxford University Press, 1994
[34] E. Hairer, “Fortran and Matlab Codes”,
[35] E. Hairer, S.P. Nørsett & G. Wanner, Solving Ordinary Differential Equations. I, Springer Series in Computational Mathematics 8, Springer-Verlag, Berlin, 1993, Nonstiff problems
[36] E. Hairer & G. Wanner, Solving Ordinary Differential Equations. II, Springer Series in Computational Mathematics 14, Springer-Verlag, Berlin, 1996, Stiff and differential-algebraic problems · Zbl 0859.65067
[37] A. Harten, “Multiresolution algorithms for the numerical solution of hyperbolic conservation laws”, Comm. Pure Applied Math.48 (1995), p. 1305-1342 · Zbl 0860.65078
[38] B. Hejazialhosseini, D. Rossinelli, M. Bergdorf & P. Koumoutsakos, “High order finite volume methods on wavelet-adapted grids with local time-stepping on multicore architectures for the simulation of shock-bubble interactions”, J. Comput. Phys.229 (2010) no. 22, p. 8364-8383 · Zbl 1381.76218
[39] Intel Corporation, “Intel Threading Building Blocks”,
[40] W. Jahnke, W.E. Skaggs & A.T. Winfree, “Chemical vortex dynamics in the Belousov-Zhabotinskii reaction and in the two-variable Oregonator model”, J. Phys. Chem.93 (1989) no. 2, p. 740-749
[41] H. Ji, F.-S. Lien & E. Yee, “A new adaptive mesh refinement data structure with an application to detonation”, J. Comput. Phys.229 (2010) no. 23, p. 8981-8993 · Zbl 1207.80023
[42] S. Jones & A. Lichtl, GPUs to Mars, Full Scale Simulation of SpaceX’s Mars Rocket Engine, in Proceedings of the GPU Technology Conference, GPU Tech Conferences on demand, , 2015
[43] R. Keppens, Z. Meliani, A. J. van Marle, P. Delmont, A. Vlasis & B. van der Holst, “Parallel, grid-adaptive approaches for relativistic hydro and magnetohydrodynamics”, J. Comput. Phys.231 (2012) no. 3, p. 718-744 · Zbl 1426.76385
[44] P. MacNeice, K.M. Olson, C. Mobarry, R. de Fainchtein & C. Packer, “PARAMESH: A parallel adaptive mesh refinement community toolkit”, Comput. Phys. Commun.126 (2000) no. 3, p. 330-354 · Zbl 0953.65088
[45] G.M. Morton, A computer Oriented Geodetic Data Base; and a New Technique in File Sequencing, Technical report, IBM, 1966
[46] S. Müller, Adaptive Multiscale Schemes for Conservation Laws 27, Springer-Verlag, Heidelberg, 2003
[47] A. Nejadmalayeri, A. Vezolainen, E. Brown-Dymkoski & O.V. Vasilyev, “Parallel adaptive wavelet collocation method for PDEs”, J. Comput. Phys.298 (2015), p. 237-253 · Zbl 1349.65652
[48] Netlib, “Compressed Row Storage (CRS)”,
[49] R.M. Noyes, R. Field & E. Koros, “Oscillations in chemical systems. I. Detailed mechanism in a system showing temporal oscillations”, J. Ame. Chem. Soc.94 (1972) no. 4, p. 1394-1395
[50] L. Oliker & R. Biswas, “PLUM: Parallel Load Balancing for Adaptive Unstructured Meshes”, J. Parallel Distr. Com.52 (1998) no. 2, p. 150-177 · Zbl 0920.68016
[51] OpenMP Architecture Review Board, “OpenMP Application Program Interface. Version 3.1.”, July 2011, Available at:
[52] J. Reinders, Intel Threading Building Blocks, O’Reilly & Associates, Inc., Sebastopol, CA, USA, 2007
[53] C.A. Rendleman, V.E. Beckner, M. Lijewski, W. Crutchfield & J.B. Bell, “Parallelization of structured, hierarchical adaptive mesh refinement algorithms”, Comput. Vis. Sci.3 (2000) no. 3, p. 147-157 · Zbl 0971.65089
[54] D. Rossinelli, B. Hejazialhosseini, M. Bergdorf & P. Koumoutsakos, “Wavelet-adaptive solvers on multi-core architectures for the simulation of complex systems”, Concurr. Comput.: Pract. Exper.23 (2011) no. 2, p. 172-186
[55] O. Roussel, K. Schneider, A. Tsigulin & H. Bockhorn, “A conservative Fully Adaptive Multiresolution algorithm for parabolic PDEs”, J. Comput. Phys.188 (2003) no. 2, p. 493-523 · Zbl 1022.65093
[56] H. Sagan, Space-filling curves, Universitext, Springer-Verlag, New York, 1994 · Zbl 0806.01019
[57] K. Schneider & O.V. Vasilyev, “Wavelet methods in computational fluid dynamics”, Annu. Rev. Fluid Mech.42 (2010) no. 1, p. 473-503 · Zbl 1345.76085
[58] M. Schreiber, T. Weinzierl & H.-J. Bungartz, Cluster Optimization and Parallelization of Simulations with Dynamically Adaptive Grids, in D. Hutchison et al., ed., Euro-Par 2013 Parallel Processing, Springer Berlin Heidelberg, 2013, p. 484-496
[59] G. Strang, “On the construction and comparison of difference schemes”, SIAM J. Numer. Anal.5 (1968), p. 506-517 · Zbl 0184.38503
[60] R. Teyssier, “Cosmological hydrodynamics with adaptive mesh refinement: A new high resolution code called RAMSES”, Astron. Astrophys.385 (2002) no. 1, p. 337-364
[61] A.I. Volpert, V.A. Volpert & V.A. Volpert, Traveling Wave Solutions of Parabolic Systems, American Mathematical Society, Providence, RI, 1994, Translated from the Russian manuscript by James F. Heyda · Zbl 0805.35143
[62] T. Weinzierl & M. Mehl, “Peano-A Traversal and Storage Scheme for Octree-Like Adaptive Cartesian Multiscale Grids”, SIAM J. Sci. Comput.33 (2011) no. 5, p. 2732-2760 · Zbl 1245.65169
[63] S. Williams, A. Waterman & D. Patterson, “Roofline: An Insightful Visual Performance Model for Multicore Architectures”, Commun. ACM52 (2009) no. 4, p. 65-76
[64] A.M. Wissink, R.D. Hornung, S.R. Kohn, S.S. Smith & N. Elliott, Large Scale Parallel Structured AMR Calculations Using the SAMRAI Framework, in Supercomputing, ACM/IEEE 2001 Conference, 2001, p. 22-22
[65] Ya.B. Zelʼdovich, G.I. Barenblatt, V.B. Librovich & G.M. Makhviladze, The Mathematical Theory of Combustion and Explosions, Consultants Bureau [Plenum], New York, 1985, Translated from the Russian by Donald H. McNeill
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.