﻿ 基于OpenMP多核并行算法的垂线偏差快速计算
 文章快速检索 高级检索
 大地测量与地球动力学  2019, Vol. 39 Issue (10): 1033-1036  DOI: 10.14075/j.jgg.2019.10.009

### 引用本文

HUANG Yan, WANG Qingbin, FENG Jinkai, et al. Fast Calculation of Plumb Line Deviation Based on OpenMP Multi-Core Parallel Algorithm[J]. Journal of Geodesy and Geodynamics, 2019, 39(10): 1033-1036.

### 第一作者简介

HUANG Yan, postgraduate, majors in physical geodesy and parallel compution, E-mail:781367531@qq.com.

### 文章历史

1. 信息工程大学地理空间信息学院，郑州市科学大道62号，450001

1 Belikov递推法与交换积分次序法 1.1 缔合勒让德函数Belikov递推法

 $\left\{ \begin{array}{l} {{\tilde P}_{n0}}\left( {\cos \theta } \right) = t{{\tilde P}_{n - 1, 0}}\left( {\cos \theta } \right) - \\ \;\;\;\frac{u}{2}{{\tilde P}_{n - 1, 1}}\left( {\cos \theta } \right), \;\;\;m = 0\\ {{\tilde P}_{nm}}\left( {\cos \theta } \right) = t{{\tilde P}_{n - 1, m}}\left( {\cos \theta } \right) - \\ \;\;\;u\left[ {\frac{1}{4}{{\tilde P}_{n - 1, m + 1}}\left( {\cos \theta } \right) - {{\tilde P}_{n - 1, m - 1}}\left( {\cos \theta } \right)} \right], \\ \;\;\;m > 0 \end{array} \right.$ (1)

${\tilde P _{nm}}\left( {\cos \theta } \right)$转化为完全正常化勒让德函数:

 ${\overline P _{nm}}\left( {\cos \theta } \right) = \sqrt {2n + 1} {\tilde N_{nm}}{\tilde P_{nm}}\left( {\cos \theta } \right)$ (2)

 $\left\{ \begin{array}{l} {{\tilde N}_{nm}} = \sqrt {\left( {2 - \delta _0^m} \right)\frac{{\left( {n + m} \right)!}}{{{2^m}n!}}\frac{{\left( {n - m} \right)!}}{{{2^m}n!}}} \\ \delta _0^m = \left\{ \begin{array}{l} \begin{array}{*{20}{c}} {1, }&{m = 0} \end{array}\\ \begin{array}{*{20}{c}} {0, }&{m \ne 0} \end{array} \end{array} \right. \end{array} \right.$ (3)
1.2 交换积分次序编程法

 $\left\{ {\begin{array}{*{20}{l}} {\xi _M^{ij} = \sum\limits_{m = 0}^N {(xE_m^i\cos m{\lambda _j} + xF_m^i\sin m{\lambda _j})} }\\ {xE_m^i = - \sum\limits_{n = 0}^N {{{(\frac{R}{{{r_i}}})}^{n + 2}}\bar C_{nm}^ * \frac{d}{{{\rm{d}}\varphi }}{{\bar P}_{nm}}(\sin {\varphi _i})} }\\ {xF_m^i = - \sum\limits_{n = 0}^N {{{(\frac{R}{{{r_i}}})}^{n + 2}}{{\bar S}_{nm}}\frac{d}{{{\rm{d}}\varphi }}{{\bar P}_{nm}}(\sin {\varphi _i})} } \end{array}} \right.$ (4)
 $\left\{ {\begin{array}{*{20}{l}} {\eta _M^{ij} = \sum\limits_{m = 0}^N {(yE_m^i\cos m{\lambda _j} + yF_m^i\sin m{\lambda _j})} }\\ {yE_m^i = - \sum\limits_{n = 0}^N {{{(\frac{R}{{{r_i}}})}^{n + 2}}m{{\bar S}_{nm}}\frac{{{{\bar P}_{nm}}(\sin {\varphi _i})}}{{\cos {\varphi _i}}}} }\\ {yF_m^i = \sum\limits_{n = 0}^N {{{(\frac{R}{{{r_i}}})}^{n + 2}}m\bar C_{nm}^ * \frac{{{{\bar P}_{nm}}(\sin {\varphi _i})}}{{\cos {\varphi _i}}}} } \end{array}} \right.$ (5)

2 OpenMP多核并行算法

2.1 并行计算的需求分析

2.2 并行方案

2.3 并行算法设计

2.3.1 并行程序实现

2.3.2 并行程序改进

OpenMP是以fork-join(分叉-合并)的形式来执行并行指令，其中fork代表开启新线程，join代表多个线程会合。fork-join模型在运行前只有一个线程存在，称之为“主线程”；在运行过程中，遇到并行开始代码，计算机则调用多个线程来执行并行任务；在并行代码执行结束后，调用的程被释放，不再工作[8](图 1)。

 图 1 线程调度示意图[6] Fig. 1 Thread scheduling diagram[6]

3 实验计算分析

3.1 并行程序改进前后对比分析

3.2 不同线程数加速效果分析

 图 2 不同线程数下计算的加速比 Fig. 2 Acceleration ratios computied with different threads

1) 随着线程数的增加，计算的加速比在提高，加速比在8线程下可达到5.3倍。

2) 加速比会小于对应的线程数(如8线程时加速比为5.3)。因为在程序运算过程中，OpenMP调度线程和同步各个线程计算过程都需要消耗一定的时间，改进后的程序尽管减少了线程调度时间，但没有减少同步线程计算的时间。

3) 由图 2可知，线程数为7时，加速比提高效果不明显，主要原因在于格网数不能整除线程数。按照上述线程分配原则，0号线程分配18行格网、1~6线程分配17行格网，计算耗时以任务量最大的0号线程计算结束为准，因此加速效果不明显。

4) 格网分辨率提高，计算量变大，同等线程数下加速比会提高。

3.3 不同范围计算效果对比

4 结语

 [1] 范昊鹏, 李姗姗. 局部区域模型重力异常快速算法研究[J]. 大地测量与地球动力学, 2013, 33(6): 28-30 (Fan Haopeng, Li Shanshan. Study on a Fast Algorithm for Model Gravity Anomalies in Local Areas[J]. Journal of Geodesy and Geodynamics, 2013, 33(6): 28-30) (0) [2] 曲政豪, 曾添, 周强. 超高阶地球重力场模型的高程异常优化算法[J]. 海洋测绘, 2014, 34(4): 5-8 (Qu Zhenghao, Zeng Tian, Zhou Qiang. Optimization Algorithm for Height Anomaly of Ultra-High Degree and Order Earth Gravity Field Model[J]. Hydrographic Surveying and Charting, 2014, 34(4): 5-8 DOI:10.3969/j.issn.1671-3044.2014.04.002) (0) [3] 章传银, 郭春喜, 陈俊勇, 等. EGM2008地球重力场模型在中国大陆适用性分析[J]. 测绘学报, 2009, 38(4): 283-298 (Zhang Chuanyin, Guo Chunxi, Chen Junyong, et al. EGM 2008 and Its Application Analysis in Chinese Mainland[J]. Acta Geodaeticaet Cartographica Sinica, 2009, 38(4): 283-298 DOI:10.3321/j.issn:1001-1595.2009.04.001) (0) [4] 欧阳明达, 张敏利, 于亮. 采用Belikov列推和跨阶次递推方法计算超高阶缔合勒让德函数[J]. 测绘工程, 2017, 26(7): 12-15 (Ouyang Mingda, Zhang Minli, Yu Liang. Calculating the Ultra-High-Order Associated Legendre Functions by Belikov Column Method and Recursive Method Between Every Other Order and Degree[J]. Engineering of Surveying and Mapping, 2017, 26(7): 12-15) (0) [5] 黄佳喜.扰动重力场快速(并行)计算方法研究[D].郑州: 信息工程大学, 2017 (Huang Jiaxi. Research on Fast (Parallel) Computing of Disturbing Gravity[D]. Zhengzhou: Information Engineering University, 2017) http://cdmd.cnki.com.cn/Article/CDMD-90005-1018702621.htm (0) [6] 刘文志. 并行算法设计与性能优化[M]. 北京: 机械工业出版社, 2015 (Liu Wenzhi. Parallel Computing and Performance Optimization[M]. Beijing: China Machine Press, 2015) (0) [7] 郁志辉. 高性能计算并行编程技术——MPI并行程序设计[M]. 北京: 清华大学出版社, 2001 (Yu Zhihui. High Performance Parallel Programming with MPI[M]. Beijing: Tsinghua University Press, 2001) (0) [8] 刘胜飞, 张云泉, 孙相征. 一种改进的OpenMP指导调度策略研究[J]. 计算机研究与发展, 2010, 47(4): 687-694 (Liu Shengfei, Zhang Yunquan, Sun Xiangzheng. An Improved Guided Loop Scheduling Algorithm for OpenMP[J]. Journal of Computer Research and Development, 2010, 47(4): 687-694) (0)
Fast Calculation of Plumb Line Deviation Based on OpenMP Multi-Core Parallel Algorithm
HUANG Yan1     WANG Qingbin1     FENG Jinkai1     TAN Xuli1
1. School of Surveying and Mapping, Information Engineering University, 62 Kexue Road, Zhengzhou 450001, China
Abstract: In order to solve the problem of low efficiency in calculating vertical deviation in large-scale and high-resolution regions by using the super-high-order earth gravity field model, this paper presents an array dimension-lifting and zoning methods based on OpenMP multi-core parallel technology. Experiments show that the acceleration ratio of this method to calculate vertical deviation is up to 5.6 times, which greatly improves the calculation efficiency of super-high order vertical deviation, and provides ideas for solving similar fast calculation problems in data processing of gravity field.
Key words: OpenMP; ultra-high order gravity field model; plumb line deviation; parallel computation; array ascending dimension