GIS典型几何计算算法的并行化及优化研究

空间数据规模的快速增长对传统矢量数据分析方法提出了更高的计算效率和处理规模要求。随着计算机硬件和软件技术的进步,并行计算为提高GIS中典型几何计算算法的计算效率、扩大问题处理规模提供了有效手段。本文在Visual Studio 2010中,使用标准C++编程语言,基于GDAL(Geospatial Data Abstraction Library)库实现空间数据的读写操作,针对线简化算法的并行化问题,在高性能计算环境下对并行任务调度策略、并行计算粒度、数据分解方法等多个核心内容开展研究。在完成相关串行算法的基础上,实现了该算法的并行化和优化设计,为相关的矢量数据空间分析方法的多核并行优化提供了思路和参考。     

并行化矢量多边形叠加算法研究

正空间数据规模的快速增长对传统地学分析方法提出了更高的计算效率和处理规模要求。作为核心的空间分析算法之一,矢量多边形叠加分析具有典型的高算法复杂性和计算密集性特征。随着计算机硬件和软件技术的进步,并行计算为提高多边形叠加分析的计算效率,扩大问题处理规模提供了有效手段。研究面向新型计算架构的多边形并行叠加分析算法对完善高性能GIS理论研究和实现方法,提升传统地学分析算法的计算效率具有重要的理论价值和实践意义。本论文针对多边形非拓扑叠加算法的并行化问题,在多种高性能计算环境下解决了     

基于OpenCL的泛Kriging算法并行化研究

针对泛Kriging插值算法在大量数据处理时的高耗时问题,该文从异构平台主机端与OpenCL设备端的交互方式入手,采用OpenCL异构平台开发语言进行泛Kriging算法并行化实现研究,解决了其在进行大数据量处理时数据存储、数据交互、多设备调度等一系列问题。在K20Xm平台上使用不同的数据集和参数对并行泛Kriging算法进行测试,实验结果表明:与Intel Xeon E5-2670CPU平台相比,并行程序插值部分加速比达到40倍以上,整体并行程序加速比达到了18倍。     

基于OpenMP的并行化水文分析算法研究与实现

水文模拟计算具有数据量较大、过程连续性较强的特点。随着数据采集技术的不断发展,大范围、高分辨率的地形数据使得传统串行算法难以满足性能要求,而并行化水文分析算法研究受到越来越多的关注。本文在对GIS空间分析算法并行化进行分析的基础上,对主要并行计算框架进行了对比,并选用OpenMP框架对水文分析若干过程进行了并行化算法的研究和实践。实验结果表明,基于OpenMP框架的并行化水文分析算法是在多核平台下进行性能优化的有效手段。     

基于GPU的遥感影像SAM分类算法并行化研究

本文简要介绍了并行图像处理的基本模式;对GPU的并行性和流式编程模型进行了分析,提出了GPU并行图像处理的基本流程,并对数据加载、计算结果反馈保存等关键技术问题进行了论述;实现了光谱角匹配(SAM)算法的GPU并行化,最后通过实验验证了该技术方法的有效性。     

K均值聚类算法的研究与并行化改进

K均值算法是一种常用的聚类分析方法,广泛应用于图像处理和机器学习等领域。但该算法具有较高的计算复杂度,导致了算法具有较大的局限性。为了提高算法的运行效率,本文在深入分析算法基本原理的基础上,利用CUDA架构提供的强大计算能力对该算法进行了并行化改进。实验结果表明,算法在取不同的聚类数时均取得了较高的加速比。     

雷达回波外推算法的并行化及实现

为了提高雷达外推TERC算法的效率,首先分析了TREC算法的原理与过程,找出算法计算密集型部分;在此基础上,采用基于多线程的并行计算对算法进行优化,并使用Windows线程库的API实现多线程编程;最后,通过实验比较串行算法和并行算法的运行时间。结果表明,并行算法发挥了多核处理器的优势,大幅提升了效率。     

流域最佳管理措施情景优化算法的并行化

流域最佳管理措施(beneficial management practices, BMPs)情景优化问题是一个典型的复杂地理计算问题,目前所常用的BMPs情景优化算法需要结合流域模型进行大量的迭代运算,因而花费大量计算时间,难以满足实际应用的要求。本文针对目前代表性的BMPs情景优化算法——ε支配多目标遗传算法(ε-NSGA-Ⅱ),采用主从式并行策略,利用MPI并行编程库实现了该优化算法的并行化。在江西省赣江上游的梅川江流域(面积为6366 km²)进行BMPs情景优化的应用案例表明,并行化的优化算法当运行于集群机时,加速比随着核数(8~512核)的增加而递增,当核数为512时,加速比达到最大值(310);并行效率随着核数的增加逐渐下降,最高值0.91,最低值0.61,取得了明显的加速效果。     

并行化多流向策略的栅格河网提取算法

流域栅格河网提取是数字地形分析的一个重要应用。为减少数字高程模型(DEM)预处理而产生的伪河道及平行河道,提出基于并行化多流向策略的栅格河网提取算法。通过水流传输矩阵模拟水量的自然流动过程,可直接应用于原始DEM。从河网空间形态和算法运行效率两方面与串行MFD算法、R&N算法及D8算法进行对比,结果表明,多流向策略得到的河网与实际地形形态更加吻合,使用并行策略后,算法的效率比也较其他算法有明显提升。     

基于集群的影像并行OPTA算法研究

并行计算是提高海量遥感影像细化处理速度的有效途径.基于对OPTA细化算法的分析,深入研究OPTA细化并行算法中数据划分和数据通信优化等关键问题,提出一种适合集群并行处理的通信优化并行算法,实验证明该算法具有良好的加速比,适合集群计算环境下海量遥感影像的细化处理.     

基于CUDA的并行空间计算

基于GPGPU的并行计算是目前新兴的热门研究领域。针对空间信息处理中常涉及的算法,本文讨论了基于CUDA技术的算法并行化问题,并提出基于栅格的点集凸壳并行算法及并行耳三角剖分算法。经对实际数据的实验表明,基于CUDA的几何并行计算可以显著地提高程序的执行效率,具有实际意义。     

基于机群的并行匹配算法

随着卫星遥感技术的发展,需要快速地将卫星遥感图像数据转化为用户需要的信息,并行图像处理技术是解决“快速”的重要途径。并行程序的性能与计算机体系结构密切相关,不但取决于CPU,还与系统架构、指令结构、存储部件的存取速度等因素有关。一般意义上,提高并行程序的性能采用粗粒度并行,指令级优化(ILP)和存储优化等技术。作为尝试,本文讨论了在工业标准化机群上采用软件式共享存储系统做的并行影像匹配方法,以影像匹配算法为例子,讨论了如何在粗粒度并行、指令级优化(ILP)和存储优化三个方面提高图像处理的计算速度。     

计算密集型空间信息服务技术实现架构研究

OGC(OpenGISConsortium)组织所提出的空间信息服务框架中包含多种需要消耗大量计算资源的计算密集型服务,如海量空间信息的存储与获取服务、影像处理服务等,但该组织并未对这类服务的具体实现方式及技术作出规定和说明。针对这类计算密集型空间信息服务,文章从技术层面研究了基于PC集群并行计算环境的计算密集型空间信息服务的实现方法及技术架构,为研究开发高性能的空间信息服务进行了探索。     

基于GPGPU的并行影像匹配算法

提出一种基于GPGPU的CUDA架构快速影像匹配并行算法,它能够在SIMT模式下完成高性能并行计算。并行算法根据GPU的并行结构和硬件特点,采用执行配置技术、高速存储技术和全局存储技术三种加速技术,优化数据存储结构,提高数据访问效率。实验结果表明,并行算法充分利用GPU的并行处理能力,在处理1280×1024分辨率的8位灰度图像时可达到最高多处理器warp占有率,速度是基于CPU实现的7倍。CUDA在高运算强度数据处理中呈现出的实时处理能力和计算能力,为进一步加速影像匹配性能和GPU通用计算提供了新的方法和思路。     

Delaunay三角网的并行构网算法

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

Landsat8地表温度反演算法研究

介绍了Landsat8地表温度反演算法。利用单窗算法和分裂窗算法分别对Landsat8的两个热红外波段进行了地表温度反演,并通过ENVI-met的模拟温度进行精度验证。结果表明,分裂窗算法和第10波段的单窗算法拥有更高的精度。     

基于TIN的土方量计算算法研究

土方量的计算是一项很重要的工作,其计算方法有很多种。本文是基于不规则三角网(TIN)的一种算法,并着重介绍了此算法的原理和方法,以便使用程序语言进行程序设计,提高土方量计算的效率和精度。     

道路中桩统一线路坐标计算模型研究

在对道路平面线形剖析的基础上,提出各类线形中桩统一线路坐标计算模型,可以根据交点坐标和里程、曲线几何元素,以桩号L为引数,计算各中桩坐标,有利于编程计算.特别是对计算复杂、有代表性的卵型曲线,采用了回旋线起点还原法.     

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

针对EM(Expectation Maximization)波形分解算法具有多次迭代和大量乘、除、累加等高密集运算的特点,提出一套将EM算法在通用计算图形处理器GPGPU上并行化的方案。针对通用并行计算架构CUDA的存储层次特点,设计总体的并行方案,充分挖掘共享存储器、纹理存储器的高速访存的潜能;根据波形采样值采用字节存储的特征,利用波形采样值的直方图求取中位数,从而降低求噪音阈值的计算复杂度;最后,采用求和规约的并行策略提高EM算法迭代过程中大量累加的计算效率。实验结果表明,当设置合理的并行参数、EM迭代次数大于16次、数据量大于64 M时,与单核CPU处理相比,GPU的加速比达到了8,能够显著地提高全波形分解的效率。     

遥感影像并行分割的无缝拼接算法

针对影像数据分块并行处理造成的接边问题,该文基于构建缓冲区的方法提出了一种新的拼接算法。该算法只在每一个数据分块的右侧和下侧构建缓冲区,消除拼接线的原则是保证分割边界的准确性和拓扑关系的正确性。数据分块完成后采用并行的策略对第一个块进行分割,然后将每一块的分割结果与相邻的块进行拼接,在缓冲区内按一定规则判断各块分割对象是否保留并对拓扑关系进行检查,拼接完各块后并行输出对象矢量化后的结果。通过实验验证,该算法不仅保证了分割边界的准确性,而且能够处理大影像,提高了工作效率。