A Fast Box Set Subtraction Algorithm for Parallel Structured Adaptive Mesh Refinement Applications

Abstract

Abstract: Box set subtraction is widely used in SAMR to compute data dependency and nested restriction. Traditional box set subtraction algorithms suffer from high time complexity, which often dominates execution time for large scale SAMR simulations. In this paper, a divide and conquer box set subtraction algorithm with linear time complexity was proposed, and enhanced by domain decomposition parallelization. Experiment results on regular box set and irregular box set of SAMR application verify linear time complexity property. And for large scale problems, our algorithm shows great improvement on computing time.

Key words: parallel computing, structured adaptive mesh refinement, box set subtraction algorithm, linear time complexity

CLC Number:

TP301

LIU Xu, XU Xiaowen, ZHANG Aiqing. A Fast Box Set Subtraction Algorithm for Parallel Structured Adaptive Mesh Refinement Applications[J]. CHINESE JOURNAL OF COMPUTATIONAL PHYSICS, 2017, 34(5): 563-573.

References

[1] HOWELL L H, GREENOUGH J A. Radiation diffusion for multi-fluid Eulerian hydrodynamics with adaptive mesh refinement[J]. J Comput Phys, 2003, 184: 53-78.
[2] XU X, MO Z, LIU Q, et al. Implicit time-integration algorithm for diffusion equations with structured AMR and its applications[J]. Chinese J Comput Phys, 2012, 29(5): 684-692.
[3] LIU Q, XU X, WU J. An adaptive explicit time integration algorithm for hydrodynamic equations and application in ICF[J]. Chinese J Comput Phys, 2011, 28(2): 174-180.
[4] GONG X F, YANG J M, ZHANG S D. A parallel SPH method with background grid of adaptive mesh refinement[J].Chinese J Comput Phys, 2016,33(2):183-189.
[5] SUN W J, FAN Z F. Adaptive mesh refinement kinetic scheme for equations of radiation hydrodynamics[J].Chinese J Comput Phys, 2015,32(3):277-292.
[6] SHU S, YUE X Q, ZHOU Z Y, et al. Approximation and two-level algorithm of finite volume scheme for diffusion equations with AMR[J].Chinese J Comput Phys, 2014,31(4):390-402.
[7] NONAKA A, ASPDEN A, ZINGALE M, et al. High-resolution simulations of convection preceding ignition in type Ia supernovae using adaptive mesh refinement[J]. The Astrophysical Journal, 2012, 745: 73-94.
[8] ALMGREN A, BELL J, LIJEWSKI M, et al. Nyx: A massively parallel AMR code for computational cosmology[J]. Astrophysical Journal, 2013, 765(1):930-940.
[9] MO Z, ZHANG A, CAO X, et al. JASMIN: A parallel software infrastructure for scientific computing[J]. Frontiers of Computer Science, 2010, 4(4):480-488.
[10] https://ccse.lbl.gov/BoxLib.
[11] GOODALE T, ALLEN G, LANFERMANN G, et al. The cactus framework and toolkit: Design and applications[M]// High performance computing for computational science - VECPAR 2002. Springer Berlin Heidelberg, 2002:26-28.
[12] COLELLA P, GRAVES D T, LIGOCKI T J, et al. Chombo software package for AMR applications design document[CP]. 2009.
[13] BRYAN G L, NORMAN M L, O'SHEA B W, et al. Enzo: An adaptive mesh refinement code for astrophysics[J]. Astrophysical Journal Supplement, 2013, 211(2).
[14] DUBEY A, REID L B, WEIDE K, et al. Extensible component based architecture for FLASH: A massively parallel, multiphysics simulation code[CP]. 2009:512-522.
[15] HORNNUG R D, KOHN S R. Managing application complexity in the SAMRAI object-oriented framework[J]. Concurrency and Computation: Practice and Experience, 2002, 14(5):347-368.
[16] PARKER S G. A component-based architecture for parallel multi-physics PDE simulation[J]. Future Generation Computer Systems, 2006, 22(1-2):204-216.
[17] WISSKNK A M, HYSOM D, HORNUNG R D. Enhancing scalability of parallel structured AMR calculations[C]//International Conference on Supercomputing, ACM, 2003:336-347.
[18] DE BERG M, KREVELD M V, OVERMARS M H, et al. Computational geometry: Algorithms and applications[M]//Computational Geometry: Algorithms and Applications. Springer-Verlag TELOS, 2008:333-334.
[19] XU L, ZHANG A, LI X, et al. A fast communication algorithm for parallel structured mesh applications[J]. Chinese Journal of Computational Physics, 2012, 29(1):58-64.
[20] ZOMORODIAN A, EDELSBRUNNER H. Fast software for box intersections[C]//Sixteenth Symposium on Computational Geometry, ACM, 2000.
[21] DUBEY A, ALMGREN A, BELL J, et al. A survey of high level frameworks in block-structured adaptive mesh refinement packages[J]. Journal of Parallel & Distributed Computing, 2014, 74(12):3217-3227.