面向结构网格自适应并行计算的矩形区域求差集快速算法

计算物理 ›› 2017, Vol. 34 ›› Issue (5): 563-573.

所属专题：超强激光等离子体相互作用的数值模拟

面向结构网格自适应并行计算的矩形区域求差集快速算法

刘旭, 徐小文, 张爱清

北京应用物理与计算数学研究所, 北京 100094

收稿日期:2016-07-11 修回日期:2016-12-27 出版日期:2017-09-25 发布日期:2017-09-25
作者简介:刘旭(1981-),男,博士,副研究员,从事并行计算研究与软件研发,E-mail:liu_xu@iapcm.ac.cn
基金资助:
国家自然科学基金（91430218， 61370067）、国家973计划项目（2011CB309702）及国家863计划项目（2012AA01A309）资助

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

LIU Xu, XU Xiaowen, ZHANG Aiqing

Institute of Applied Physics and Computational Mathematics, Beijing 100094, China

Received:2016-07-11 Revised:2016-12-27 Online:2017-09-25 Published:2017-09-25

摘要/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

中图分类号:

TP301

刘旭, 徐小文, 张爱清. 面向结构网格自适应并行计算的矩形区域求差集快速算法[J]. 计算物理, 2017, 34(5): 563-573.

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.

参考文献

[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.

面向结构网格自适应并行计算的矩形区域求差集快速算法

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

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

作者中心

审稿中心

期刊浏览

期刊介绍

[1]	李凌霄, 翟传磊, 谢辉, 施意. 一种求解三维热辐射输运方程的整体预处理迭代方法及并行计算[J]. 计算物理, 2021, 38(3): 269-279.
[2]	范宣华, 王柯颖, 肖世富, 陈璞. 强脉动压力下飞行器随机振动分析算法与并行实现[J]. 计算物理, 2021, 38(2): 192-198.
[3]	严小松, 杨建伦, 羊奕伟. 康普顿相机图像重建中的快速滤波反投影算法[J]. 计算物理, 2020, 37(2): 153-162.
[4]	彭浩, 单鸣雷, 朱昌平, 姚澄. LBM伪势MRT三维模型GPU并行计算的性能优化[J]. 计算物理, 2018, 35(5): 554-562.
[5]	于晨阳, 范宣华, 王柯颖, 肖世富. 基于PANDA平台的多点基础激励谐响应的并行计算[J]. 计算物理, 2018, 35(4): 443-450.
[6]	李凌霄. 不可压缩流基于块预处理的并行有限元计算[J]. 计算物理, 2018, 35(2): 151-160.
[7]	包芸, 叶孟翔, 罗嘉辉. 湍流热对流的高效并行直接求解方法[J]. 计算物理, 2017, 34(6): 651-656.
[8]	徐幼平, 程煜峰, 王斌, 郭红, 普业, 程锐. 基于JASMIN框架的区域大气模式并行程序开发及试验[J]. 计算物理, 2017, 34(1): 47-60.
[9]	张若兴, 侯士敏, 丑强. 基于第一性原理量子输运模拟的并行计算[J]. 计算物理, 2015, 32(6): 631-638.
[10]	任健, 武林平, 申卫东. 基于JASMIN框架多物理耦合程序的性能优化及分析[J]. 计算物理, 2015, 32(4): 431-436.
[11]	朱炼华, 郭照立. 基于格子Boltzmann方法的多孔介质流动模拟GPU加速[J]. 计算物理, 2015, 32(1): 20-26.
[12]	程汤培, 莫则尧, 邵景力. 基于JASMIN的地下水流大规模并行数值模拟[J]. 计算物理, 2013, 30(3): 317-325.
[13]	任健, 魏军侠, 曹小林. 基于JASMIN框架的辐射流体与粒子输运耦合计算[J]. 计算物理, 2012, 29(2): 205-212.
[14]	张僡凤, 欧阳洁, 代向艳. 耦合有限体积法的Brown构型场并行算法[J]. 计算物理, 2012, 29(1): 17-24.
[15]	刘旭, 张爱清, 肖丽, 莫则尧. 面向结构网格并行应用的一类快速通信算法[J]. 计算物理, 2012, 29(1): 58-64.