CUDA环境下地形因子的并行计算

为了满足栅格数据空间分析的高性能计算需求,本文以坡度计算为例,提出在CUDA环境下将串行地形因子算法进行并行优化的方法:根据地形因子计算过程中无数据相关性,适合进行数据并行计算的特点,将CPU上可以并行执行的计算任务通过CUDA并行处理机制映射到GPU线程块上,从而提高计算效率。试验测试了不同栅格规模下串行算法和并行算法的执行时间差异,测试结果表明,并行地形因子算法的性能明显优于串行算法,在网格规模为12800×11200时,获得最高串-并加速比24.39。     

基于PMVS算法的大规模数据细粒度并行优化方法

三维多视角立体视觉算法（patch-based multi-view stereo，PMVS）以其良好的三维重建效果广泛应用于数字城市等领域，但用于大规模计算时算法的执行效率低下。针对此，提出了一种细粒度并行优化方法，从任务划分和负载均衡、主系统存储和GPU存储、通信开销等3方面加以优化；同时，设计了基于面片的PMVS算法特征提取的GPU和多线程并行改造方法，实现了CPUs_GPUs多粒度协同并行。实验结果表明，基于CPU多线程策略能实现4倍加速比，基于统一计算设备架构（compute unified device architecture，CUDA）并行策略能实现最高34倍加速比，而提出的策略在CUDA并行策略的基础上实现了30%的性能提升，可以用于其他领域大数据处理中快速调度计算资源。     

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

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

一种基于CUDA的大数据量地理加权回归并行加速算法

针对传统地理加权回归（GWR）在大数据量计算中存在的计算效率低、内存占用大、数据规模受限等问题，本文提出了快速并行地理加权回归（FPGWR）算法，基于英伟达CUDA架构实现了GWR的并行加速，将串行过程分解为并行的独立回归计算模块，同时优化了内存使用模型，提高了算法的运行速度。对比FPGWR和传统GWR在不同数量级模拟数据上和真实数据上的运行速度，结果显示，FPGWR能够支持更大规模的样本量计算并有效提升运行效率，数据量越大加速效果越显著。     

基于OpenMP的矢量空间数据并行拓扑算法设计与实现

高性能并行GIS逐渐成为GIS发展的新方向。矢量数据的复杂性使得一些并行GIS算法难以实现,从而无法满足并行GIS的发展要求。文中针对GIS算法中的拓扑算法,借助OpenMP编程模型,通过消除并行拓扑处理过程中的数据依赖,在单机多核的环境下设计并实现了矢量空间数据并行拓扑算法。通过实验对比串行拓扑算法和并行拓扑算法的处理时间和结果,验证了并行拓扑算法的正确性,同时证明并行拓扑算法能够在一定程度上提升拓扑处理的效率。     

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

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

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

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

几何部件缓冲区域合并的Buffer算法及其并行优化方法

摘 要：本文在介绍一种基于几何部件缓冲区域合并的矢量数据缓冲区生成算法的基础上,采用数据并行思想和MPI编程模型对缓冲区算法的并行化实现和优化方法开展研究。实验结果显示,与ArcGIS Buffer工具相比,（1）当缓冲区结果多边形不合并时,虽然串行缓冲区算法的时间开销较高,但可轻易通过并行方式实现加速。（2）当缓冲区结果合并时,本文算法要明显优于ArcGIS Buffer工具,并且经过优化的并行缓冲区算法表现出了更高的计算效率和更大规模的数据处理能力。因此,基于几何部件缓冲区域合并的Buffer算法具备一定的实用价值,本文提出的按结点数量的任务分解方法和进程间结果“树状”归并策略是对缓冲区算法进行并行优化的有效途径,对GIS中其他矢量分析算法的并行化及相关优化工作也具有一定的借鉴意义。     

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

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

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

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

云环境下海量空间矢量数据并行划分算法

空间数据划分是空间大数据索引方法及其数据存储的重要组成部分。针对Hadoop云计算平台在空间数据划分及其存储方面的不足,提出了基于Hilbert空间填充曲线的海量空间矢量数据并行划分算法。在数据划分阶段,充分考虑空间数据相邻对象的空间位置关系、空间对象的自身大小以及相同编码块的空间对象个数等影响因素;通过“合并小编码块,分解大编码块”的划分原则,实现了云环境下海量空间矢量数据的并行划分算法。试验表明,该算法不仅能够提高海量空间矢量数据的索引效率,同时也能够很好地解决空间矢量数据在Hadoop分布式文件系统（Hadoop distributed file system,HDFS）上的数据倾斜问题。     

基于CUDA的高效并行遥感影像处理

近年来,随着空间遥感技术的发展,使得遥感影像数据呈几何级数增长,遥感影像的处理面临数据量大、密集度高、计算复杂度高和运算量大等问题。在分析最新GPU（图形处理单元）的并行架构和统一计算设备架构（CUDA）灵活的可编程性的基础上,提出了一种基于CUDA的遥感影像的高效处理方法,以遥感影像处理中常用的快速傅里叶变换、边缘检...     

MPI+OpenMP环境下的特征函数空间滤值并行化方法研究

针对现有的特征函数空间滤值方法存在算法复杂、计算效率低下、难以满足海量空间数据应用需求等问题,提出一种特征函数空间滤值并行化方法。基于主从模型(master/slave模型)和MPI+OpenMP混合编程模式,充分挖掘多核集群下计算机的性能,并在多核集群平台上与纯MPI算法进行了对比实验。结果表明,基于MPI+OpenMP的方法能够获得更高的并行加速比和计算效率。     

RaPC:一种基于栅格化思想的多边形裁剪算法及其误差分析

传统的基于矢量计算的多边形裁剪算法的时间复杂度介于O(Nlog N)~O(N2)之间,且计算过程与特定的复杂数据结构耦合紧密,难以进行底层优化和细粒度并行化。在满足一定误差要求的前提下,采用栅格化处理思想可以实现多边形快速裁剪。本文在已有多边形裁剪算法特征的基础上,提出了一种基于栅格化处理思想的多边形裁剪算法——RaPC算法,并对其误差进行了分析和讨论。试验结果显示,RaPC算法的计算效率随网格单元增大呈幂函数规律降低;当网格大小恒定时,RaPC算法效率随多边形顶点数量呈线性增长,计算时间复杂度为O(N);在处理小数据集时Vatti算法表现出了较高效率,但是在处理包含大量顶点的多边形叠加时,RaPC算法更为高效;RaPC算法的面积误差与网格大小直接相关,提高网格空间分辨率可以有效地降低面积误差。RaPC算法在处理包含大量顶点的多边形叠加分析时比Vatti算法更为高效。     

多核并行计算在地形因子计算中的应用

为了满足地理国情监测中地形统计指标的高性能计算需求,该文提出在多核计算环境下将地形因子串行计算进行并行化的方法:通过对串行算法耗时部分进行线程级并行化改进,尽可能使计算过程中的线程负载均衡、计算任务的分配更加均匀,从而有效提升程序运算效率。试验对比了不同地形因子算子在计算栅格数据时串行方式和并行方式的执行效率差异,测试结果表明,并行算法在单机16核环境下的计算效率提升明显。     

空间划分多因子耦合PDE模型与算法

为研究非凸空间离散数据的空间划分,建立了耦合数据集的凸凹性、数据规模、离散度的空间划分的数学模型。利用Laves划分标识[36]对非凸空间离散数据进行有限区域变比例划分,然后通过地形曲面微分单元与数据规模的偏导函数关系,耦合离散度计算空间划分的单元间距和数量。最后通过构建DEM,可视化验证和对比分析发现,耦合模型能够计算出非凸离散空间数据空间划分单元的间距和数量,也能实现不同分辨率的划分单元的无缝拼接;且当试验数据从110组递增至440组时,该模型耗时仅是[44]标识划分和Delaunay的1/10~1/3,且随数据规模成倍增加时耗时基本呈线性增长,收敛性较好,但耗时随离散度增加而增长。     

利用等边长正交格网进行层次聚合聚类

层次聚合聚类的典型算法可以体现研究数据的多尺度特征,但是典型算法的时空复杂度太高。通过将数据所在空间划分成等边长正交格网,结合3点间距离的传递性排除冗余计算,并将其推广到N维空间。设计了一种与典型算法遵循相同的单链规则,可即时计算类间距离且无需计算距离矩阵的算法,在获得与典型算法相同的多尺度聚类序列的同时,所需内存远小于典型算法。实验结果表明,该算法无需人工干预且不使用距离矩阵,能大幅降低层次聚合聚类的运行时间,但是效率优势随空间维数增长逐渐降低。     

基于CUDA的并行空间计算

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

基于Hadoop的GNSS网基线向量的分布式处理

对于海量的GNSS观测数据,常规的集中式数据处理方法面临着计算效率低的问题,利用Hadoop平台技术分布式解算基线的方法可以有效地解决这一问题。通过划分子网,调用GAMIT软件并行解算基线,63个IGS站计算结果表明,3个计算节点的加速比达到了6.67,平差得到的坐标点精度在毫米量级。      

云环境下时序遥感影像的快速缓存切片方法

自然灾害与地表环境实时动态监测对短周期内接收影像的快速缓存切片提出了很高的要求。利用云计算并行编程模式Map-Reduce聚集计算资源,提出了一种在时序影像持续抵达情况下的快速缓存切片方法。围绕Map-Reduce本地化计算特性,该方法在任务分配中利用数据动态划分机制及基于空间相邻的上载机制对缓存切片算法进行优化加速,以满足环境动态监测对瓦片式缓存的及时性需求。实验证明,该方法在大数据量情况下较同类方法具有更好的扩展性能和加速性能。