Task-based adaptive multiresolution for time-space multi-scale reaction-diffusion systems on multi-core architectures
The SMAI Journal of computational mathematics, Volume 3 (2017), pp. 29-51.

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.

Published online:
DOI: 10.5802/smai-jcm.19
Classification: 65Y05, 65T60, 65M50, 65L04, 35K57
Keywords: Task-based parallelism, multi-core architectures, multiresolution, adaptive grid, stiff reaction-diffusion equations
Stéphane Descombes 1; Max Duarte 2; Thierry Dumont 3; Thomas Guillet 4; Violaine Louvet 3; Marc Massot 5

1 Université Côte d’Azur, CNRS, Inria, LJAD, France
2 CCSE, Lawrence Berkeley National Laboratory, 1 Cyclotron Rd. MS 50A-1148, Berkeley, CA 94720, USA and CD-adapco, 200 Shepherds Bush Road, London W6 7NL, UK
3 Université de Lyon, Université Claude Bernard Lyon 1, CNRS UMR 5208, Institut Camille Jordan, 43 blvd. du 11 novembre 1918, F-69622 Villeurbanne Cedex, France
4 Intel, Les Montalets, 2 rue de Paris, 92196 Meudon, France, Exascale Computing Research, Campus Teratec, 2 rue de la Piquetterie, 91680 Bruyères-le-Châtel, France
5 CNRS UPR 288, Laboratoire EM2C, CentraleSupélec, Fédération de Mathématiques de l’École Centrale Paris, CNRS FR 3487, Grande Voie des Vignes, 92295 Chatenay-Malabry Cedex, France
License: CC-BY-NC-ND 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights
     author = {St\'ephane Descombes and Max Duarte and Thierry Dumont and Thomas Guillet and Violaine Louvet and Marc Massot},
     title = {Task-based adaptive multiresolution for time-space multi-scale reaction-diffusion systems on multi-core architectures},
     journal = {The SMAI Journal of computational mathematics},
     pages = {29--51},
     publisher = {Soci\'et\'e de Math\'ematiques Appliqu\'ees et Industrielles},
     volume = {3},
     year = {2017},
     doi = {10.5802/smai-jcm.19},
     zbl = {1416.65184},
     mrnumber = {3646202},
     language = {en},
     url = {https://smai-jcm.centre-mersenne.org/articles/10.5802/smai-jcm.19/}
AU  - Stéphane Descombes
AU  - Max Duarte
AU  - Thierry Dumont
AU  - Thomas Guillet
AU  - Violaine Louvet
AU  - Marc Massot
TI  - Task-based adaptive multiresolution for time-space multi-scale reaction-diffusion systems on multi-core architectures
JO  - The SMAI Journal of computational mathematics
PY  - 2017
SP  - 29
EP  - 51
VL  - 3
PB  - Société de Mathématiques Appliquées et Industrielles
UR  - https://smai-jcm.centre-mersenne.org/articles/10.5802/smai-jcm.19/
DO  - 10.5802/smai-jcm.19
LA  - en
ID  - SMAI-JCM_2017__3__29_0
ER  - 
%0 Journal Article
%A Stéphane Descombes
%A Max Duarte
%A Thierry Dumont
%A Thomas Guillet
%A Violaine Louvet
%A Marc Massot
%T Task-based adaptive multiresolution for time-space multi-scale reaction-diffusion systems on multi-core architectures
%J The SMAI Journal of computational mathematics
%D 2017
%P 29-51
%V 3
%I Société de Mathématiques Appliquées et Industrielles
%U https://smai-jcm.centre-mersenne.org/articles/10.5802/smai-jcm.19/
%R 10.5802/smai-jcm.19
%G en
%F SMAI-JCM_2017__3__29_0
Stéphane Descombes; Max Duarte; Thierry Dumont; Thomas Guillet; Violaine Louvet; Marc Massot. Task-based adaptive multiresolution for time-space multi-scale reaction-diffusion systems on multi-core architectures. The SMAI Journal of computational mathematics, Volume 3 (2017), pp. 29-51. doi : 10.5802/smai-jcm.19. https://smai-jcm.centre-mersenne.org/articles/10.5802/smai-jcm.19/

[1] A. Abdulle Fourth order Chebyshev methods with recurrence relation, SIAM J. Sci. Comput., Volume 23 (2002) no. 6, p. 2041-2054 (electronic) | DOI | MR | Zbl

[2] Structured adaptive mesh refinement (SAMR) grid methods (S.B. Baden; N.P. Chrisochoides; D.B. Gannon; M.L. Norman, eds.), The IMA Volumes in Mathematics and its Applications, 117, Springer-Verlag, New York, 2000, xii+172 pages https://dx-doi-org.bibliopam.ecp.fr/10.1007/978-1-4612-1252-2 (Papers from the IMA Workshop held at the University of Minnesota, Minneapolis, MN, March 12–13, 1997) | DOI | MR

[3] D.S. Balsara; C.D. Norton Highly parallel structured adaptive mesh refinement using parallel language-based approaches, Parallel Comput., Volume 27 (2001) no. 1–2, pp. 37-70 http://www.sciencedirect.com/science/article/pii/S0167819100000880 | DOI | Zbl

[4] J. Bell; M. Berger; J. Saltzman; M. Welcome Three-dimensional adaptive mesh refinement for hyperbolic conservation laws, SIAM J. Sci. Comput., Volume 15 (1994) no. 1, pp. 127-138 https://dx-doi-org.bibliopam.ecp.fr/10.1137/0915008 | DOI | MR | Zbl

[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., Volume 37 (1996) no. 1, pp. 55-69 | DOI

[6] R.D. Blumofe; C.E. Leiserson Scheduling Multithreaded Computations by Work Stealing, J. ACM, Volume 46 (1999) no. 5, pp. 720-748 http://doi.acm.org/10.1145/324133.324234 | DOI | MR | Zbl

[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.), Volume 34, EDP Sci., Les Ulis, 2011, pp. 151-183 | MR | Zbl

[8] K. Brix; S.S. Melian; S. Müller; G. Schieffer, ESAIM: Proc., Volume 29 (2009), pp. 108-129 | DOI | MR | Zbl

[9] C. Burstedde; L. Wilcox; O. Ghattas p4est: Scalable Algorithms for Parallel Adaptive Mesh Refinement on Forests of Octrees, SIAM J. Sci. Comput., Volume 33 (2011) no. 3, pp. 1103-1133 http://epubs.siam.org/doi/abs/10.1137/100791634 | DOI | MR | Zbl

[10] A. Cohen; S. M. Kaber; S. Müller; M. Postel Fully Adaptive Multiresolution Finite Volume Schemes for Conservation Laws, Math. Comput., Volume 72 (2003), pp. 183-225 | DOI | MR

[11] W. Crutchfield; M.L. Welcome Object-oriented implementation of adaptive mesh refinement algorithms, J. Sci. Program. (1993), pp. 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++ (2003) (Technical report)

[14] R. Deiterding Block-structured adaptive mesh refinement - Theory, implementation and application, Summer School on Multiresolution and Adaptive Mesh Refinement Methods (ESAIM Proc.), Volume 34, EDP Sci., Les Ulis, 2011, pp. 97-150 https://dx-doi-org.bibliopam.ecp.fr/10.1051/proc/201134002 | DOI | MR | Zbl

[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., Volume 52 (2014) no. 3, pp. 1311-1334 | DOI | MR | Zbl

[16] S. Descombes; T. Dumont Numerical simulation of a stroke: Computational problems and methodology, Prog. Biophys. Mol. Bio., Volume 97 (2008) no. 1, pp. 40-53 | DOI

[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., Volume 84 (2007) no. 6, pp. 749-765 | DOI | MR | Zbl

[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, pp. 386-482 | MR

[19] S. Descombes; M. Massot Operator splitting for nonlinear reaction-diffusion systems with an entropic structure: Singular perturbation and order reduction, Numer. Math., Volume 97 (2004) no. 4, pp. 667-698 | DOI | MR | Zbl

[20] J. Dreher; R. Grauer Racoon: A parallel mesh-adaptive framework for hyperbolic conservation laws, Parallel Comput., Volume 31 (2005) no. 8–9, pp. 913-932 http://www.sciencedirect.com/science/article/pii/S0167819105000797 | DOI | MR

[21] M.-A. Dronne; J.-P. Boissel; E. Grenier A mathematical model of ion movements in grey matter during a stroke, J. Theor. Biol., Volume 240 (2006) no. 4, pp. 599-615 | DOI | MR

[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., Volume 53 (2016), pp. 232-247 | DOI | MR | Zbl

[23] M. Duarte Adaptive numerical methods in time and space for the simulation of multi-scale reaction fronts, Ecole Centrale Paris (2011) (Ph. D. Thesis)

[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., Volume 231 (2012) no. 3, pp. 1002-1019 | DOI | MR | Zbl

[25] M. Duarte; S. Descombes; C. Tenaud; S. Candel; M. Massot Time-space adaptive numerical methods for the simulation of combustion fronts, Combust. Flame, Volume 160 (2013) no. 6, pp. 1083-1101 | DOI

[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.), Volume 34, EDP Sci., Les Ulis, 2011, pp. 277-290 | DOI | MR | Zbl

[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., Volume 34 (2012) no. 1, p. A76-A104 | DOI | MR | Zbl

[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., Volume 18 (2013) no. 6, pp. 1539-1557 | DOI | MR | Zbl

[29] W. Eckhardt; T. Weinzierl A Blocking Strategy on Multicore Architectures for Dynamically Adaptive PDE Solvers, Parallel Processing and Applied Mathematics (D. Hutchison, ed.), Volume 6067, Springer Berlin Heidelberg, Berlin, Heidelberg, 2010, pp. 567-575 http://link.springer.com/10.1007/978-3-642-14390-8_59 | DOI

[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., Volume 71 (2016), pp. 1-25 | DOI

[31] C.J. Forster Parallel wavelet-adaptive direct numerical simulation of multiphase flows with phase change, Georgia Institute of Technology (2016) (Ph. D. Thesis)

[32] T. Gautier; J.V.F. Lima; N. Maillard; B. Raffin, Parallel Distributed Processing (IPDPS), 2013 IEEE 27th International Symposium on (2013), pp. 1299-1308 | DOI

[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, http://www.unige.ch/~hairer/software.html

[35] E. Hairer; S.P. Nørsett; G. Wanner Solving Ordinary Differential Equations. I, Springer Series in Computational Mathematics, 8, Springer-Verlag, Berlin, 1993, xvi+528 pages (Nonstiff problems) | MR

[36] E. Hairer; G. Wanner Solving Ordinary Differential Equations. II, Springer Series in Computational Mathematics, 14, Springer-Verlag, Berlin, 1996, xvi+614 pages (Stiff and differential-algebraic problems) | MR | Zbl

[37] A. Harten Multiresolution algorithms for the numerical solution of hyperbolic conservation laws, Comm. Pure Applied Math., Volume 48 (1995), pp. 1305-1342 | DOI | MR | Zbl

[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., Volume 229 (2010) no. 22, pp. 8364-8383 | DOI | Zbl

[39] Intel Corporation Intel Threading Building Blocks, https://www.threadingbuildingblocks.org/

[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., Volume 93 (1989) no. 2, pp. 740-749 | DOI

[41] H. Ji; F.-S. Lien; E. Yee A new adaptive mesh refinement data structure with an application to detonation, J. Comput. Phys., Volume 229 (2010) no. 23, pp. 8981-8993 http://www.sciencedirect.com/science/article/pii/S0021999110004705 | DOI | Zbl

[42] S. Jones; A. Lichtl, Proceedings of the GPU Technology Conference (GPU Tech Conferences on demand) (2015) (http://on-demand.gputechconf.com/gtc/2015/video/S5398.html)

[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., Volume 231 (2012) no. 3, pp. 718-744 http://www.sciencedirect.com/science/article/pii/S0021999111000386 | DOI | MR | Zbl

[44] P. MacNeice; K.M. Olson; C. Mobarry; R. de Fainchtein; C. Packer PARAMESH: A parallel adaptive mesh refinement community toolkit, Comput. Phys. Commun., Volume 126 (2000) no. 3, pp. 330-354 http://www.sciencedirect.com/science/article/pii/S0010465599005019 | DOI | Zbl

[45] G.M. Morton A computer Oriented Geodetic Data Base; and a New Technique in File Sequencing (1966) (Technical report)

[46] S. Müller Adaptive Multiscale Schemes for Conservation Laws, 27, Springer-Verlag, Heidelberg, 2003 | MR | Zbl

[47] A. Nejadmalayeri; A. Vezolainen; E. Brown-Dymkoski; O.V. Vasilyev Parallel adaptive wavelet collocation method for PDEs, J. Comput. Phys., Volume 298 (2015), pp. 237-253 | DOI | MR | Zbl

[48] Netlib Compressed Row Storage (CRS), http://netlib.org/linalg/html_templates/node91.html

[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., Volume 94 (1972) no. 4, pp. 1394-1395 | DOI

[50] L. Oliker; R. Biswas PLUM: Parallel Load Balancing for Adaptive Unstructured Meshes, J. Parallel Distr. Com., Volume 52 (1998) no. 2, pp. 150-177 http://www.sciencedirect.com/science/article/pii/S0743731598914691 | DOI | Zbl

[51] OpenMP Architecture Review Board OpenMP Application Program Interface. Version 3.1., 2011 (Available at: http://www.openmp.org)

[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., Volume 3 (2000) no. 3, pp. 147-157 http://link.springer.com/10.1007/PL00013544 | DOI | Zbl

[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., Volume 23 (2011) no. 2, pp. 172-186 | DOI

[55] O. Roussel; K. Schneider; A. Tsigulin; H. Bockhorn A conservative Fully Adaptive Multiresolution algorithm for parabolic PDEs, J. Comput. Phys., Volume 188 (2003) no. 2, pp. 493-523 | DOI | MR | Zbl

[56] H. Sagan Space-filling curves, Universitext, Springer-Verlag, New York, 1994, xvi+193 pages | DOI | MR | Zbl

[57] K. Schneider; O.V. Vasilyev Wavelet methods in computational fluid dynamics, Annu. Rev. Fluid Mech., Volume 42 (2010) no. 1, pp. 473-503 | DOI | MR

[58] M. Schreiber; T. Weinzierl; H.-J. Bungartz Cluster Optimization and Parallelization of Simulations with Dynamically Adaptive Grids, Euro-Par 2013 Parallel Processing (D. Hutchison, ed.), Volume 8097, Springer Berlin Heidelberg, Berlin, Heidelberg, 2013, pp. 484-496 http://link.springer.com/10.1007/978-3-642-40047-6_50 | DOI

[59] G. Strang On the construction and comparison of difference schemes, SIAM J. Numer. Anal., Volume 5 (1968), pp. 506-517 | DOI | MR | Zbl

[60] R. Teyssier Cosmological hydrodynamics with adaptive mesh refinement: A new high resolution code called RAMSES, Astron. Astrophys., Volume 385 (2002) no. 1, pp. 337-364 http://www.edpsciences.org/10.1051/0004-6361:20011817 | DOI

[61] A.I. Volpert; V.A. Volpert; V.A. Volpert Traveling Wave Solutions of Parabolic Systems, American Mathematical Society, Providence, RI, 1994, xii+448 pages (Translated from the Russian manuscript by James F. Heyda) | DOI | MR

[62] T. Weinzierl; M. Mehl Peano-A Traversal and Storage Scheme for Octree-Like Adaptive Cartesian Multiscale Grids, SIAM J. Sci. Comput., Volume 33 (2011) no. 5, pp. 2732-2760 http://epubs.siam.org/doi/abs/10.1137/100799071 | DOI | MR | Zbl

[63] S. Williams; A. Waterman; D. Patterson Roofline: An Insightful Visual Performance Model for Multicore Architectures, Commun. ACM, Volume 52 (2009) no. 4, pp. 65-76 http://doi.acm.org/10.1145/1498765.1498785 | DOI

[64] A.M. Wissink; R.D. Hornung; S.R. Kohn; S.S. Smith; N. Elliott, Supercomputing, ACM/IEEE 2001 Conference (2001), p. 22-22 | DOI

[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, xxi+597 pages (Translated from the Russian by Donald H. McNeill) | MR

Cited by Sources: