面向结构网格并行应用的一类快速通信算法

计算物理 ›› 2012, Vol. 29 ›› Issue (1): 58-64.

面向结构网格并行应用的一类快速通信算法

刘旭, 张爱清, 肖丽, 莫则尧

北京应用物理与计算数学研究所高性能计算中心, 北京 100094

收稿日期:2011-03-11 修回日期:2011-08-02 出版日期:2012-01-25 发布日期:2012-01-25
作者简介:刘旭(1981-),男,北京,博士,主要从事并行算法与并行应用软件研究,北京市海淀区丰豪东路2号100094,E-mail:liu_xu@iapcm.ac.cn
基金资助:
国家自然科学基金重点项目(61033009);国家高技术研究发展计划863(2010AA012302,2010AA012303);国家重点基础研究发展规划973(2011CB309702)资助项目

A Fast Communication Algorithm for Parallel Structured Mesh Applications

LIU Xu, ZHANG Aiqing, XIAO Li, MO Zeyao

Institute of Applied Physics and Computational Mathematics, Beijing 100094

Received:2011-03-11 Revised:2011-08-02 Online:2012-01-25 Published:2012-01-25

摘要/Abstract

摘要： 通信算法需要在相邻子区域间传输数据.通过求解子区域间的相交问题可以寻找相邻区域.针对子区域的求交问题,基于区间树,结合结构网格应用的特点,构造近似线性时间复杂度的算法.数值实验表明该算法具有较高的计算效率和可扩展性,能够支持百万量级矩形子区域的并行计算.

关键词: 并行计算, 结构网格, 快速通信算法, 区间树

Abstract: Communication algorithms need to exchange data between adjacent subdomains. The detection of adjacent subdomains is an import task for communication algorithms, which can be done by solving an intersection problem of boxes. An interval tree algorithm is proposed for intersection problems. Taking advantage of structured mesh applications, it is able to maintain 0 (Nlog N) time complexity. Numerical experiments show that the algorithm is able to achieve high computational efficiency and good scalability. It supports parallel computing of miUion-box scale.

Key words: parallel computing, parallel structured mesh application, fast communication algorithm, interval tree

中图分类号:

TP301

刘旭, 张爱清, 肖丽, 莫则尧. 面向结构网格并行应用的一类快速通信算法[J]. 计算物理, 2012, 29(1): 58-64.

LIU Xu, ZHANG Aiqing, XIAO Li, MO Zeyao. A Fast Communication Algorithm for Parallel Structured Mesh Applications[J]. CHINESE JOURNAL OF COMPUTATIONAL PHYSICS, 2012, 29(1): 58-64.

[1]	胡晓燕, 范征锋. 惯性约束聚变内爆中基于多块结构网格的高效辐射扩散并行算法[J]. 计算物理, 2022, 39(3): 277-285.
[2]	李凌霄, 翟传磊, 谢辉, 施意. 一种求解三维热辐射输运方程的整体预处理迭代方法及并行计算[J]. 计算物理, 2021, 38(3): 269-279.
[3]	范宣华, 王柯颖, 肖世富, 陈璞. 强脉动压力下飞行器随机振动分析算法与并行实现[J]. 计算物理, 2021, 38(2): 192-198.
[4]	严小松, 杨建伦, 羊奕伟. 康普顿相机图像重建中的快速滤波反投影算法[J]. 计算物理, 2020, 37(2): 153-162.
[5]	艾邦成, 张亮, 陈智. 低耗散非结构网格多维限制器[J]. 计算物理, 2018, 35(5): 545-553.
[6]	彭浩, 单鸣雷, 朱昌平, 姚澄. LBM伪势MRT三维模型GPU并行计算的性能优化[J]. 计算物理, 2018, 35(5): 554-562.
[7]	于晨阳, 范宣华, 王柯颖, 肖世富. 基于PANDA平台的多点基础激励谐响应的并行计算[J]. 计算物理, 2018, 35(4): 443-450.
[8]	李凌霄. 不可压缩流基于块预处理的并行有限元计算[J]. 计算物理, 2018, 35(2): 151-160.
[9]	包芸, 叶孟翔, 罗嘉辉. 湍流热对流的高效并行直接求解方法[J]. 计算物理, 2017, 34(6): 651-656.
[10]	刘旭, 徐小文, 张爱清. 面向结构网格自适应并行计算的矩形区域求差集快速算法[J]. 计算物理, 2017, 34(5): 563-573.
[11]	林文洲, 林忠, 刘全. 非结构多边形网格滑移线开穴算法[J]. 计算物理, 2017, 34(3): 273-282.
[12]	徐幼平, 程煜峰, 王斌, 郭红, 普业, 程锐. 基于JASMIN框架的区域大气模式并行程序开发及试验[J]. 计算物理, 2017, 34(1): 47-60.
[13]	张若兴, 侯士敏, 丑强. 基于第一性原理量子输运模拟的并行计算[J]. 计算物理, 2015, 32(6): 631-638.
[14]	任健, 武林平, 申卫东. 基于JASMIN框架多物理耦合程序的性能优化及分析[J]. 计算物理, 2015, 32(4): 431-436.
[15]	朱炼华, 郭照立. 基于格子Boltzmann方法的多孔介质流动模拟GPU加速[J]. 计算物理, 2015, 32(1): 20-26.