并行计算环境下三种空间计算域划分算法的设计与比较-以沙尘暴数值模拟为例
作为一种自然天气过程,沙尘暴对环境、人类健康及社会财产都有严重的负面影响.随着全球气候的持续变化和人为因素,沙尘暴的频率和强度已经在过去几十年内发生了显著提升.作为沙尘暴的频发区域,我国北方地区,近十年来几乎每年冬春两季都会发生若干次强沙尘暴天气,对人民的交通出行、工作和生活带来诸多不便,并已经严重危害了人民的健康和安全. 针对这NP Hard问题，本文提出三种不同的划分方法，分别是基于二次规划的最优化方法(Quadratic Programming，QP)、一种K-Means聚类算法和Kernighan-Lin节点置换算法结合的三阶段启发式计算域划分算法(K&K)和基于自动种子区域生长的算法(AutomaticSeeded Region Growing，ASRG)，并针对求解效率和效果进行了深入的比较。针对求解效率，本文比较了三种算法在不同问题规模下的算法求解时间。针对求解效率，本文从子计算域上数据块的均衡性、子计算域上跨域通讯量的均衡性以及子计算域划分过程中产生的总通讯录三个方面进行度量和评价，并针对不同的问题规划、区域形状进行了深入的比较。实验表明三种算法有各自不同的适用场合，但总的来说K&K算法不仅有较好的收敛速度，能够胜任大计算域（网格节点数量大）划分的问题；同时有良好计算效果，可以保证较好的划分形态。 本文提出的K&K算法显著降低了计算节点之间的通讯成本、平衡了计算负载并降级了总计算时间（针对不同计算节点个数和数据块粒度的实验中，数值模拟过程提速最高可达20％-80%）。因此该算法显示了其在沙尘暴数值模拟过程中的实用价值；同时，在涉及计算域划分的同类计算和通讯密集型科学计算中，该算法也具有广泛的潜在应用空间。
沙尘暴 天气预测 计算域 划分过程 最优化方法 K-Means聚类算法 Kernighan-Lin节点置换算法
桂志鹏 姜云峰 杨超伟
武汉大学遥感信息工程学院,武汉,430079;Center of Intelligent Spatial Computing for Water/Energy Science, George Maso Center of Intelligent Spatial Computing for Water/Energy Science, George Mason University, Fairfax,
国内会议
徐州
中文
51-52
2014-10-11（万方平台首次上网日期，不代表论文的发表时间）