基于异构集群计算的地统计面插值并行算法

地统计面插值算法在空间统计分析中有广泛应用,其目的是通过一组面要素的某已知属性值估算另一组面要素的属性值。地统计面插值算法多是基于克里金（Kriging）插值及其衍生算法。克里金插值算法考虑属性在空间位置上的变异性,需计算要素之间的协方差,是典型的计算密集型算法。本文分析了基于克里金插值的地统计算法计算过程,该算法中面要素间协方差计算相互独立,可作为并行计算单元划分。另外,面要素间协方差计算可使用快速傅里叶变换（FFT）快速计算,而FFT是一种非常适合并行处理的计算密集型算法。本文根据算法特征设计了基于异构集群计算的并行算法,并使用MPI+CUDA实现了该算法。实验结果表明,本文实现的算法比使用MPI实现的CPU集群的算法有更好的性能,具备良好的可扩展性,并且随着插值精度提高表现出更好的性能。     

一种计算简单奇异点的有效算法

本文提供一种加边算法用以计算简单奇异点 ,并用数值例子的计算说明算法的有效性。     

改进的DWCS算法及其在弱硬实时系统中的应用

针对动态窗口约束调度算法中,单个任务到达调度处理节点时,系统存在着无效计算的缺点,本文提出了一个改进算法。该算法在保留原有算法优良性能的同时,能够降低计算复杂性,提高系统的性能。并证明了DWCS算法可以用于一般的弱硬实时系统中。     

基于剖分表达结构的雷达探测范围计算方法

雷达不仅在现代军事中发挥着至关重要的作用,也被广泛应用于社会经济发展和科学研究等领域。如何科学表达并计算真实环境下雷达探测范围是当前研究热点。目前已有算法采用几何光学和数学建模的思路,存在计算量大、复杂度高等问题,导致算法效率低。本文基于空间剖分结构提出一种雷达探测范围的计算方法,该方法采用剖分的思想,实现了地形影响下雷达探测范围和多雷达探测范围的计算及可视化,具备计算简单、算法复杂度低等特点。实验表明,该算法具备很好的表达效果与计算能力,算法效率较传统方法明显提高,为雷达探测范围的计算提供了一条新的解决途径。     

并行地理计算算法性能评测技术研究

从并行地理算法的正确性评测、性能评测、评测流程和评测工具实现等角度,研究了高性能集群环境下的评测技术。在正确性评测假设基础上,将评测用例在不同进程数环境下的计算结果与该算法在单进程环境下的运算结果逻辑求差得出相对误差,提出了问题规模计算方法。根据评测用例的问题规模确定评测用例的权重,提出了性能指标和评测流程,并通过评测工具自动获得同一个并行地理计算算法。在多个不同评测用例下的评测指标来衡量算法的计算误差与性能,形成评测报告。经实验验证,本文方法能较好地满足并行地理计算算法评测的需求,为并行空间分析算法性能优化提供技术保障。     

栅格地理计算并行算子对区域计算算法并行化的可用性分析——以多流向算法为例

栅格地理计算并行编程库的研发有助于实现对栅格地理计算算法的并行化。在现有的研究中,Qin 等(2014)设计并初步研发的栅格地理计算并行算子(PaRGO),在设计思路上能较好地隐藏与并行编程软硬件环境相关的复杂细节,实现栅格地理计算通用步骤的并行化,且较其他类似思路的编程库而言,PaRGO能兼容多种常用的并行计算平台,具有明显优势。但PaRGO目前在设计上仅直接支持本地、邻域及全局计算特点的栅格地理计算算法并行化,对于更为复杂的区域计算特点算法并行化的支持能力尚未探究。对此,本文选取栅格数字地形分析中具有区域计算特点、递归设计的多流向算法为算例,利用PaRGO进行并行化设计、实现及测试,以计算时间、相对加速比和相对并行效率为定量指标。通过可运行性和并行性能进行评价,结果表明:PaRGO虽然不能直接支持对递归的多流向算法进行并行化,但在根据多流向计算的原理将该递归算法转变为非递归的设计之后,可将算法由原区域计算改造为邻域迭代计算,就能利用PaRGO 实现并行化,并得到较好的并行效果。在集群环境下,MPI版本并行程序的并行效果优于MPI/OpenMP混合版本。     

改进的HASM-AD算法及在空间变量模拟的应用分析

高精度曲面建模(HASM)可以显著提高空间曲面模拟的精度,但是计算速度低限制了该模型的进一步应用。为了提高HASM模型的计算效率,本文对HASM-AD算法作了改进,通过在计算过程中为采样点添加索引,避免了计算过程中对采样点信息的重复查找操作;同时,在遍历独立计算单元时实时计算第一类、第二类基本量及克式符号,避免了全局存储上述变量所需要的额外内存消耗。数值试验表明,由于将全局线性方程组求解问题转化为局部独立计算单元(5×5栅格)内的方程组求解,改进的HASM-AD算法显著提高了计算效率,同时降低了模型运行过程中的内存消耗。最后,本文以全国陆地降水空间分布模拟分析作为实例,验证改进的HASM-AD算法模拟精度及计算效率,模拟结果表明,改进的HASM-AD算法模拟结果精度优于其他HASM算法(以HASM-PCG为例),并且计算效率优势更为明显,实现全国10km分辨率的降水分布模拟耗时仅为4s。表明改进的HASM-AD算法提高了计算速度,并且适于大尺度的空间变量模拟应用。     

一种地形改正新算法

通过对地球表面和大地水准面的物理学受力分析发现,传统计算地形改正方法存在误差。分析了其误差来源及大小,解释了该误差形成的原因,并给出了计算地形改正的新算法,新算法可有效提高计算精度。     

水流算法对于坡度坡长因子的影响研究

坡度坡长因子是影响土壤侵蚀的主要地形因子。单流向算法和多流向算法得到的坡度坡长因子差异非常大。基于多流向算法的坡长计算得到的坡度坡长因子图,光滑连续,符合坡面漫流原理,比单流向算法得到得坡长计算得到的坡度坡长因子更加合理。     

地震精密水准网平差的一种高效算法研究

传统的地震水准网平差计算方法因需要进行大量的“零乘积”运算而致使运算效率低下,不适用于数据量较大的地震水准网计算工作。针对地震水准网平差计算过程中法方程系数具有对称正定的特性,利用变量循环重新编号法进一步提升运算效率。利用新算法进行数据平差计算,对比验证结果表明,与传统算法相比,地震精密水准网型越复杂,新算法节省的时间越多。     

GPU加速的改进PAM聚类算法研究与应用

空间聚类是空间数据挖掘的重要方法,而K-Medoids是一种常用的空间聚类算法。K-Medoids聚类算法存在初始点选择问题,而且计算复杂。为了提高算法的有效性和时间效率,本文结合模拟退火算法思想,改进了传统的K-Medoids算法PAM,提出一种基于GPU计算的并行模拟退火PAM算法。类比矩阵乘法运算,定义了一种新的矩阵计算方法,可以有效减少数据在GPU全局内存和共享内存之间的传输,提高了算法在GPU中的执行效率。利用模拟退火算法搜索聚类中心点,保证了聚类结果的全局最优性。基于不同的数据集,将串行和并行模拟退火PAM算法以及已有的遗传PAM算法进行比较,结果表明并行模拟退火PAM算法聚类结果正确,且时间效率高。最后,应用本文改进算法对贵州省安监系统的安全监管隐患数据进行聚类分析,发现了隐患聚集中心,相关结果对政府的决策具有一定的实际应用价值。     

基于Spark的空间数据实时访存技术的研究

研究并实现了基于Spark的空间查询算法。根据空间查询特性和Spark分布式内存计算模型,设计了HBase分布式存储、分布式空间索引、Spark分布式内存计算框架的空间区域查询算法和Spark Streaming的空间查询算法,提供实时在线空间查询服务。实验表明,基于Spark streaming并行空间查询算法*可以提供空间数据的实时空间查询服务。     

RANSAC-PSO算法的抗差反演——以芦山地震为例

本文利用RANSAC-PSO算法研究在反演断层滑动参数时所用大地测量数据包含粗差的问题。在模拟实验中对理论观测值加入1%、5%、10%粗差,分别采用粒子群算法、选权迭代算法和RANSAC-PSO算法反演断层滑动参数。结果表明,当观测值中包含粗差率达10%时,PSO算法反演的滑动参数与理论值相差23.2 cm,选权迭代法反演的滑动参数与理论值相差26.2 cm,而RANSAC-PSO反演的滑动参数与理论值相差小于1 cm。芦山地震具有以逆冲为主兼具少量左旋走滑性质,采用芦山地震同震GPS位移数据分别以PSO算法和RANSAC-PSO算法反演断层滑动参数,RANSAC-PSO算法反演的走滑量为0.051 8 m,倾滑量为0.828 9 m,均大于PSO的反演结果;释放能量1.000 9×1019 N·m（MW6.63）,与GCMT 的1.060 0×1019 N·m更加吻合。分别用RANSAC-PSO算法与PSO算法反演的滑动参数计算地表水平位移,并与GPS观测进行对比,发现二者在计算距断层的远场点时,计算的水平位移基本一致;而在计算距断层的近场点时,RANSAC-PSO算法表现更为优秀,尤其体现在LS07点上,其计算值与GPS观测值完全重合。     

基于状态转移矩阵的Hilbert码快速生成算法

空间填充曲线的空间排列码可实现多维空间到一维空间的线性映射,广泛应用于空间查询、空间索引、空间划分及影像编码等领域。Hilbert是一种优秀的空间填充曲线,具有非常好的空间聚集性。传统的Hilbert排列二进制循环位操作算法的算法复杂度为O(n²)。本文首先分析了Hilbert的分形自相似特性,推导并归纳出Hilbert状态转移矩阵,按位编码顺序定义了空间划分中的象限顺序,将Hilbert状态转移矩阵转换为C++中的数组运算,减少了Hilbert码计算过程中的嵌套循环及迭代处理,将算法复杂度降为O(n)。其次,采用位域共用体以数值计算替代了传统计算过程中的数值与字符串间类型转换,提高了Hilbert码生成算法的性能。最后,在C++环境下实现了Hilbert码快速生成算法的相关代码,并完成算法的正确性验证实验和性能对比实验。实验结果表明,本文提出的算法计算结果与二进制循环位算法的结果一致,在性能上本文算法与二进制循环位算法及空间层次分解算法相比有明显的优势。     

一种改进的平方根滤波在卫星钟差实时解算中的应用

目前普遍采用卡尔曼滤波方法来实现非差法卫星钟差的实时解算。平方根滤波可以增强数值计算的稳定性,避免滤波发散,但矩阵的求逆会耗费较长的计算时间;序贯算法可以避免对矩阵直接求逆,能提升计算效率。综合两种算法的优点,提出一种基于序贯算法的平方根滤波器,并应用于卫星钟差的实时解算,得到的卫星钟差精度优于0.2 ns,且计算时长缩短40%。     

全空间下并行矢量空间分析研究综述与展望

新一代并行空间分析将面临空间大数据分析和实时空间分析服务的挑战。矢量空间计算作为GIS系统中的重要组成部分,在并行化算法设计中存在负载不均,并行扩展性差,IO性能低等技术瓶颈。本文首先从应用需求和技术发展的演变历史回顾了矢量空间分析算法发展过程;然后,从研究现状的角度详细阐述了并行矢量空间分析计算的研究成果,总结了并行空间分析算法的算法特征和技术瓶颈,对不同并行编程模型进行了对比,并提出了并行空间分析算法的研发流程;最后,从发展前景的角度预测了全空间信息系统中基于多粒度时空对象的空间数据模型和计算方法的发展趋势,提出了以内存计算等技术实现存算一体化的新型空间数据模型和分析方法的技术趋势。     

ArcGIS环境下DEM的坡长计算与误差分析

坡长是水土保持、土壤侵蚀和环境评价等研究中的基本因子。在GIS环境下,坡长的提取是基于格网DEM进行的,其结果受到DEM精度、DEM结构、流向提取算法和栅格距离计算方式的影响。在确定分辨率和精度的DEM下,坡长计算误差主要来自流向提取算法和栅格距离计算方式。本文对这两种DEM坡长计算误差源进行了详细的分析,指出集成到ArcGIS软件中的坡长计算模型D8存在较大缺陷,尽管栅格距离计算方式对坡长影响最大误差为8.9%,并可通过统计方式实现整体坡长的修正,但D8算法的单流向特性使得水流方向变得确定和不连续,进而导致坡面单元坡长产生较大误差,因此,利用D8算法进行数值模拟计算需要考虑其精度问题。同时应提高坡长计算的准确性,需要发展更为完善的流向计算方法和坡长计算模型。     

多边形叠加Vatti算法的VCS优化方法与GPU并行化

Vatti算法是常用的矢量多边形裁剪算法之一,在其构建扫描束实现交点计算的过程中,二叉树的数据结构和递归计算方法导致其计算效率受矢量多边形边界顶点数量影响显著。本文针对Vatti算法执行过程中较为耗时的扫描束构建环节,提出了一种多边形边界顶点预排序的优化方法——VCS（Vertex Coordinate Pre-Sorting）方法,并基于该方法实现了对Vatti算法的GPU细粒度并行化。VCS方法使用双向链表对Vatti算法原有的二叉树数据结构进行了替换,以较小的额外存储空间取得了多边形边界顶点信息查找效率的明显提升。在GPU环境下采用双调排序算法对多边形边界顶点数组元素进行并行化排序并过滤出有效值,克服了原始算法使用二叉树存储导致效率低下的问题。实验结果表明,改进后的算法与原始算法相比,具有相同的计算精度;当多边形顶点数量为92万,CUDA每个线程块中的线程数量为32时,使用VCS优化方法,与采用CPU计算构建扫描束方法相比,GPU并行化方法获得了39.6倍的相对加速比,矢量多边形叠加分析算法效率总体上提升了4.9倍。     

改进权重的迭代最近点算法在点云配准中的应用

针对传统迭代最近点算法不具备抗差性的难题,利用迭代最近点算法配准残差的分布规律,综合M估计及选权迭代思想,提出改进权重的迭代最近点配准算法。根据每个点对配准计算出对应的初始权重,然后在附加点对权重的基础上使用选权迭代法计算出满足条件的权重,以达到抵御粗差的目的。结果表明,选权迭代过程能合理改善三维空间转换参数计算的结果,提出的改进算法较适合含粗差点的点云数据的配准。     

超图平台软件创新:SuperMap GIS高性能GIS技术简介

正北京超图软件股份有限公司研发的高性能GIS技术,融合了内存计算、并行计算、GPU计算和高性能算法(图1),其研制的高性能GIS内核,整合发挥计算机大内存、多CPU、多核和显卡的高性能计算能力,显著提升空间数据处理的性能。SuperMap GIS内核构建了全新的基于内存计算(即64位计算)的GIS数据结构与算法,充分利用64位计算环境的大内存寻址能力和更高的指令处理带宽,