并行地图叠加分析中基于数据分解的负载均衡方法研究

地图叠加分析是一种计算密集型算法,并行化计算可以加快算法执行速度。本文研究并行化地图叠加分析中的负载均衡方法。首先针对并行算法中的IO竞争情况,定义了负载均衡指数;然后基于分治法分解空间数据,将并行系统下的地理要素分而治之,将Hilbert空间索引作为集群系统中各节点分配数据的依据,最终实现并行地图叠加分析系统中的数据负载均衡,为地图叠加分析算法中的数据并行策略提供可能性。结果表明,利用空间索引分治的负载均衡方法建立索引速度快,调度系统可以将计算任务明确分配到各计算节点。     

大规模遥感影像全球金字塔并行构建方法

金字塔模型是大规模遥感影像可视化的基础,是在保证精度的前提下,采用不同分辨率的数据来提高渲染速度,从而在网络环境下实现大规模数据共享、服务和辅助决策支持。在构造金字塔的过程中,由于遥感数据经常会突破内存的容量,同时会产生大量的小瓦片,小瓦片存贮非常耗时,传统的串行算法很难满足应用需求。本文提出了一种并行大规模遥感影像的全球金字塔构造算法,利用图形处理器(graphics processing unit,GPU)的高带宽完成费时的重采样计算,使用多线程实现数据的输入和输出,在普通的计算机上实现大规模影像的全球金字塔的快速构建。首先,采用二级分解策略突破GPU、CPU和磁盘的存储瓶颈;然后,利用多线程策略加速数据在内存和磁盘之间的传输,并采用锁页内存来消除GPU全局延迟的影响;最后,用GPU完成大规模的并行重采样计算,并利用四叉树策略提高显存中数据的重复利用率。实验结果表明,本文方法可以明显地提高全球金字塔的构造速度。     

基于 VisIt与地球系统格网的并行可视化实验

利用集群架构和分布式并行可视化工具 VisIt,编写了自定义插件,实现了基于大规模地球系统格网组织下的全球科学数据并行可视化,并设计实验对其并行可视化性能进行了对比分析.实验发现: VisIt完成一次渲染的加速比及并行效率随着核数的增加逐渐降低;采用 GPU 渲染,可以很好地提高并行渲染的效率.但在核数和 GPU 个数同步增加的情况下,由于核间通信、 GPU 间通信以及核- GPU 间通信等,VisIt一次渲染的并行运行时间并无明显降低.随着数据量增加,VisIt对单位数据量的运行时间却逐渐减低.实验表明,VisIt可较高效地完成大数据量的并行渲染.该方法和结论可供地学领域大规模海量数据可视化研究参考.     

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

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

大规模GNSS网分布式存储与解算方法

针对GNSS大网在海量数据存储和解算方面面临的挑战,设计了从基础设施、数据管理、计算和服务到应用的GNSS分布式存储与解算体系结构;基于HDFS改进了GNSS数据存储目录结构;基于HBase设计了GNSS数据存储表结构;基于MapReduce提出了GNSS大网分区分布式解算策略。实验搭建了分布式平台,实现了GNSS数据分布式存储、并行检索和发布以及GNSS大网分区分布式解算,存储和解算性能均得到了较大提高。结果表明,所提出的方法可用于GNSS大网数据存储和解算。     

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

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

大范围复杂三维场景并行绘制实时帧同步技术

针对复杂三维模型在实时绘制过程中的帧同步策略,该文提出改进。基于Windows集群开发了一种sort-first数据分布式体系结构的并行图形绘制系统;基于缓存交换技术提出一种多路并行的帧同步算法来提高集群的通信效率。在Windows集群系统上进行了验证实验,结果表明:(1)该算法较大程度地提高了集群的帧同步性能并缩短了同步重建时间;(2)集群并行系统有效地完成了大范围复杂三维GIS场景的流畅绘制显示。     

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

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

基于集群的遥感影像并行绘制研究

基于集群并行绘制系统,采用基于WCF通信构架的Sort-first体系结构,对遥感影像建立金字塔层次模型,提高并行绘制效率。并行绘制集群系统采用基于WCF构架并发机制的分布式数据存储模式,突破传统的共享数据存储模式,减少数据在网络传输的开销。在集群系统环境下,对遥感影像建立金字塔模型和未建立金字塔模型两种情况下的影像数据进行并行绘制实验。实验结果表明:建立金字塔模型的遥感影像使得并行绘制效率显著提高。     

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

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

海量GNSS小文件云存储优化方法研究

GNSS数据量呈指数级趋势增长,Hadoop分布式文件系统（HDFS）解决了海量GNSS数据存储瓶颈的难题,却面临内存占用多、文件相关性差和缺乏优化机制的问题。针对HDFS处理海量GNSS小文件效率不高的问题,结合GNSS数据类型、特点以及存储过程,提出了一种新的GNSS小文件云存储方法,优化了GNSS小文件的写入、读取、添加和删除策略。该方法分别按观测文件和解算成果的类型进行合并,对合并后的文件构建压缩Trie树索引,索引切分后,根据匹配算法分布式地存储索引块。实验采用国际GNSS服务（IGS）28 d的数据和产品进行云存储优化。结果表明,该方法降低了各节点内存消耗,提高了海量GNSS小文件写入、读取和删除的效率,实现了对海量GNSS小文件的高效云存储。     

基于多GPU的Harris角点检测并行算法

提出了一种基于多图形处理器(graphic processing unit,GPU)设计思想的Harris角点检测并行算法,使用众多线程将计算中耗时的影像高斯卷积平滑滤波部分改造成单指令多线程(single instruction multi-ple thread,SIMT)模式,并采用GPU中共享存储器、常数存储器和锁页内存机制在统一计算设备架构(com-pute unified device archetecture,CUDA)上完成影像角点检测的全过程。实验结果表明,基于多GPU的Har-ris角点检测并行算法比CPU上的串行算法可获得最高达60倍的加速比,其执行效率明显提高,对于大规模数据处理呈现出良好的实时处理能力。     

分布式网络安全问题分析

介绍分布式网络中存在的一些安全问题,总结分布式网络的安全对策,提出要引入使用虚拟CA(Certificate Authority)和证书链方式实现可靠的认证,使用可以量化的信任机制来解决分布式网络中对等节点之间通信安全。     

全球电离层模型的分布式并行解算

为满足GNSS数据处理效率不断提升的需求,提出并开发了一套分布式并行计算框架,并基于该框架实现了全球电离层模型的分布式并行解算。采用2台服务器和4台台式机,对全球电离层建模分别测试了单机多线程、多机分布式等并行计算方案,并分析了不同方案建模的数据处理效率。结果表明,采用多线程并行计算可以大幅提高数据处理效率,且当开启线程数与计算机CPU核心数一致时效率提升最佳;采用多机分布式并行计算可进一步提高数据处理效率,使用4台台式机相对于单台台式机解算时间减少约60%,使用2台服务器相对于单台服务器解算时间减少约18%;采用分布式并行计算方案,可充分利用多台计算机资源来提高全球电离层建模效率,对电离层产品快速发布、建模算法的测试等具有重要的意义,对多系统GNSS精密定轨与定位、大网解算也具有很好的参考价值。     

A spatial parallel heuristic approach for solving very large‐scale vehicle routing problems

The vehicle routing problem (VRP) is one of the most prominent problems in spatial optimization because of its broad applications in both the public and private sectors. This article presents a novel spatial parallel heuristic approach for solving large‐scale VRPs with capacity constraints. A spatial partitioning strategy is devised to divide a region of interest into a set of small spatial cells to allow the use of a parallel local search with a spatial neighbor reduction strategy. An additional local search and perturbation mechanism around the border area of spatial cells is used to improve route segments across spatial cells to overcome the border effect. The results of one man‐made VRP benchmark and three real‐world super‐large‐scale VRP instances with tens of thousands of nodes verify that the presented spatial parallel heuristic approach achieves a comparable solution with much less computing time.     

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

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

利用最小二乘直接法反演卫星重力场模型的MPI并行算法

针对海量卫星重力数据反演高阶次地球重力场模型的密集型计算任务与高内存耗用问题,基于MPI实现了最小二乘直接法恢复高阶次位系数的并行算法。引入并行读写、分块存储与分块计算等方式完成了设计矩阵的构建、法方程的形成与求解等密集型计算任务的并行算法,数值计算结果表明三者的并行相对效率峰值可分别达到95%、68%、63%。利用GOCE轨道跟踪和径向扰动重力梯度数据(共518 400个历元)分别反演了120、240阶次地球重力场模型,计算时间仅为40 min、7 h,内存耗用峰值仅为290 MB、1.57 GB;采用与GOCE同等噪声水平的观测数据恢复的重力场模型精度与GOCE已发布模型的解算精度相一致,联合GRACE和GOCE的解算模型能够实现二者独立信息的频谱互补,表明本文方法可高效稳定地恢复高阶次地球重力场模型。     

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

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

共享内存环境下的干涉合成孔径声呐复图像配准及优化方法

提出了一种共享内存环境下的干涉合成孔径声呐（interferometric synthetic aperture sonar,InSAS）复图像配准优化方法。首先在分析复图像配准算法各处理步骤计算特点和并行性的基础上,针对粗配准和精配准计算中大量的滑动窗口计算操作,根据相邻窗口数据之间的关系进行了计算方法优化设计;然后采用OpenMP指令对粗配准、精配准、复图像插值和干涉相位提取计算步骤进行了并行化设计和计算任务分配,以充分利用多核计算资源加速复图像配准过程;最后通过InSAS复图像的并行配准试验验证了所提方法的正确性和高效性。