A parallel method to accelerate spatial operations involving polygon intersections

Polygon intersection is an important spatial data-handling process, on which many spatial operations are based. However, this process is computationally intensive because it involves the detection and calculation of polygon intersections. We addressed this computation issue based on two perspectives. First, we improved a method called boundary algebra filling to efficiently rasterize the input polygons. Polygon intersections were subsequently detected in the cells of the raster. Owing to the use of a raster data structure, this method offers advantages of reduced task dependence and improved performance. Based on this method, we developed parallel strategies for different procedures in terms of workload decomposition and task scheduling. Thus, the workload across different parallel processes can be balanced. The results suggest that our method can effectively accelerate the process of polygon intersection. When addressing datasets with 1,409,020 groups of overlapping polygons, our method could reduce the total execution time from 987.82 to 53.66 s, thereby obtaining an optimal speedup ratio of 18.41 while consistently balancing the workloads. We also tested the effect of task scheduling on the parallel efficiency, showing that reducing the total runtime is effective, especially for a lower number of processes. Finally, the good scalability of the method is demonstrated.     

数字地形分析方法研究的维度——精准、高效、易用

数字地形分析基于数字高程模型计算各种地形信息,在诸多地理现象和地理过程的定量刻画和模拟中都发挥着不可或缺的重要作用。作为地理信息空间分析的一个基本组成内容、GIS的必备功能之一,数字地形分析的方法研究不断深化、扩展。本文从一个新的视角,即方法研究的维度,对该领域已有工作及发展趋势进行梳理,将数字地形分析方法研究工作归纳为依次显现出的3个研究维度：① 精准,即如何设计新的数字地形分析方法以更准确、精确地计算出符合地理学认知、满足应用领域问题求解所需的地形信息;② 高效,即如何使数字地形分析的计算更高效;③ 易用,即如何使数字地形分析对于应用者（尤其是相关应用领域中非数字地形分析专家的用户）更易用。特别是近年新显现出的“易用”研究维度,通过研究设计数字地形分析领域应用建模知识的形式化表达及相应的推理应用方法,有望实现数字地形分析应用工作流的智能化构建,满足实际应用中对数字地形分析的易用性需求;同时,其研究思路和方法也可为地理信息空间分析中诸多其他分支领域解决所面临的类似问题提供借鉴。     

Delaunay三角网的并行构网算法

针对传统的Delaunay三角网的并行构建算法负载均衡性不高、运行效率较低等问题,该文在综合逐点插入算法和分治算法各自优点的基础上,提出了一种Delaunay三角网并行构建算法。该算法首先使用动态格网剖分点要素集,从而得到若干点要素子集;然后根据点要素子集数量初始化线程池,每个点要素子集由一个线程按照插入点法构建Delaunay子网;当所有线程完成子三角网构建,最后使用逐点插入法合并所有子网,从而实现所有点要素的Delaunay三角网构建。分析与实验结果表明,相对于传统的并行算法,该并行算法的负载均衡性好、运行时间少、加速比高,具有较好的构建效率,而且构建结果满足Delaunay规则。     

FORTRANM在重磁数据处理中的应用

介绍了ＦｏｒｔｒａｎＭ的基本概念和特点。ＦｏｒｔｒａｎＭ是一个支持分布式环境中并行计算的Ｆｏｒｔｒａｎ语言新成员，它在Ｆｏｒｔｒａｎ７７上扩充而成，不仅能支持数据并行程序设计，而且能支持任务并行程序设计。在重磁数据处理中，常常要进行大计算量的运算，如果采用并行计算方法，可以大大提高低档机器的运算能力，降低运算费用，缩短处理周期。本文用ＦｏｒｔｒａｎＭ把ＧＭＰＳ改造成并行计算系统ＧＭＰＳ－ＦＭ，经实际运行，效果良好，最后对测试结果作了分析。     

基于GPU的并行条件模拟算法及其在储量估算中的应用

条件模拟是一种计算非常耗时的高精度三维插值算法。针对串行条件模拟算法计算时间过长的问题,提出基于GPU的并行条件模拟算法,并进行储量估算。对条件模拟算法进行并行分析,利用GPU的高度并行性,构建CUDA通用计算开发环境,实现串行条件模拟算法到并行条件模拟算法的转换,使条件模拟算法的时间复杂度从O(n)降至O(logn)。并对西藏甲玛铜矿进行了储量估算。实验结果表明,在安装普通NVIDIA显卡的计算机以及估算精度不下降的情况下,GPU并行条件模拟的计算效率比CPU串行条件模拟的计算效率提高了60倍以上。     

基于GPU的全波形并行LM分解算法

波形分解是机载激光雷达全波形数据处理的重要基础工作,通过求解波形函数模型的参数,将波形数据利用具体的函数模型拟合出来,实现对全波形及其中各个子波形函数表达。LM(Levenberg-Marquardt)算法及其改进的算法是波形分解中对参数进行拟合求解的常用方法。针对LM算法在参数拟合计算的过程中存在大量迭代和矩阵运算,提出了基于线程块组和线程两级并行粒度的并行计算方案。将串行多次循环迭代求解参数改为单次并行计算取最佳值实现对参数的选择,将矩阵运算进行线程块的协同并行计算,实现了LM算法在通用计算图形处理器上的并行计算。实验证明,在规定阈值条件下,并行LM降低了算法的迭代次数,提高了波形分解LM算法的计算效率,为提高波形分解的处理效率提供了研究思路。     

一种大规模空间数据流式并行处理方法研究

针对空间数据的读写(I/O)时间占比过高问题,文章提出一种流式并行化方法:通过将空间计算过程与数据I/O过程相重叠,使传统并行空间计算方法中的性能提升瓶颈得到显著缓解;并且,方法所采用的数据分片策略,能够使数据单次I/O所产生的高内存使用率得到降低,进一步提高了具体地学算法的适用性。最后以地理国情普查基本统计分析中地表面积计算为例进行验证,结果表明:该算法的计算效率与内存使用率相对于直接并行方法均获得明显改善,且空间数据流式并行处理方法与具体地学算法耦合度低。该方法已成功应用于多个其他统计分析算法中。     

可扩展的迭代自组织分析并行处理算法

随着遥感影像数据量的增加,传统非监督分类迭代自组织分析(ISODATA)算法的运算将十分耗时,应用并行计算技术能够有效解决该性能瓶颈。针对现有基于并行计算模型MapReduce的遥感迭代自组织分析并行算法存在的局限性,提出一种可扩展的基于MapReduce的迭代自组织分析并行处理算法。该算法通过其包含的全局子采样算法、聚类中心点集合过滤算法以及聚类映射算法,有效克服了现有并行算法中存在的不足。实验结果表明,在同等规模遥感计算中,该算法效率高于现有并行处理算法,具有良好的加速比,且在处理更大的影像块时具有更高的精度。     

Parallel Neural Network-Based Motion Controller for Autonomous Underwater Vehicles

A parallel neural network-based controller （PNNC） is presented for the motion control of underwater vehicles in this paper. It consists of a real-time part, a self-learning part and a desired-state programmer, and it is different from normal adaptive neural network controller in structure. Owing to the introduction of the self-learning part, on-line learning can be performed without sample data in several sample periods, resulting in high learning speed of the controller and good control performance. The desired-state programmer is utilized to obtain better learning samples of the neural network to keep the stability of the controller. The developed controller is applied to the 4-degree of freedom control of the AUV “IUV- IV” and is successful on the simulation platform. The control performance is also compared with that of neural network controller with different structures such as normal adaptive neural network and different learning methods. Current effects and surge velocity control are also included to demonstrate the controller＇ s performance. It is shown that the PNNC has a great possibility to solve the problems in the control system design of underwater vehicles.     

潮流场数学方程交错分区并行计算方法研究

文章对潮流场数学方程进行可并行性方法研究。分析了两种可并行实现的方法，并对两种可并行化的方法可行性进行分析。最后采用虚拟区域分解法对问题进行了实现，并利用串行计算的结果对并行计算的结果进行了验证。