PC集群环境下的并行地理网络车辆路径算法

针对PC集群计算节点内存小、进程间通信速度慢的问题,本文设计了分布式的数据存储机制;提出了用同步变换规则代替解编码传输的进程间通信方式;基于邻域分解策略实现了禁忌搜索过程的并行化,发展了一种适用于PC集群环境的并行地理网络VRP算法。应用模拟路网数据进行了相关试验,结果表明：本文算法的计算结果与ArcGIS基本一致,二者平均偏差率在2.11%~2.87%之间;分布式数据存储策略有效地降低了各进程对内存的需求量,保证了算法的稳健性和扩展性;通过算法的并行化提高了VRP算法的求解效率;该算法具有良好的加速性能,8进程时在各测试数据集中的加速比均在4.46~6.32之间。     

3维数字地球快速缓冲区分析算法

提出一种应用在3维数字地球中的通过图形处理器(GPU)快速实现矢量数据缓冲区分析的算法。使用一张4通道的纹理图作为容器将地理实体的矢量数据传入GPU,利用GPU的高效并行特性,将目标缓冲区纹理中的每个像素所对应的矢量坐标与原实体进行距离量算,在一次渲染中得到缓冲区纹理,最后提取出缓冲区纹理的边界。选择中国的流域和湖泊矢量数据,将本文算法与两种传统的CPU算法进行了缓冲区分析计算、测试和对比。结果显示,本文算法相对于传统矢量算法效率提高了9—16倍,相对于传统栅格算法效率提高11—20倍。实验证明,该算法计算简单,效果明显,特别是随着数据量增大,缓冲区计算速度显著优于传统算法,并能有效解决传统矢量法缓冲区分析中的数据自相交问题。     

统一计算设备架构的D8算法并行化研究

针对空间遥感技术的快速发展导致地理空间数据呈几何级数增长,传统GIS空间分析面临巨大的计算实时性需求的问题,该文为提高GIS数字地形分析算法在处理海量高分辨率DEM数据时的计算效率,基于CUDA众核流处理器并行编程模型,采用不同数据划分方法、纹理内存及异步数据传输机制等技术,对串行D8算法进行了并行化设计及算法优化,探索并分析了D8并行算法的数据拷贝与算法执行等环节的计算效率变化。实验结果表明,CUDA并行编程能够对D8算法实现较为明显的加速,在按5个行子块进行划分、调用1 344个线程时并行加速效果达到最佳,加速比为19.5。并且,在不同行子块划分方式下且调用线程数不超过1 344个时,加速比随调用线程数的增加而增长,计算时间占比随线程数的增加呈递减趋势。     

基于IGGⅢ的地理加权回归模型研究

针对离群值存在时地理加权回归模型拟合效果较差的问题,本文提出了基于IGGⅢ的地理加权回归方法。核心是采用IGGⅢ方案中的权函数计算权重矩阵,将权因子用于地理加权回归参数估计模型。利用模拟数据和真实数据与GWR、ACV-GWR进行对比试验,以MSE、MAE和R²作为指标对结果进行评价。模拟试验结果显示,IGGⅢ-GWR比GWR性能分别提升了51.14%、23.77%、28.4%,比ACV-GWR分别提升了49.96%、22.57%、27.1%;真实试验结果显示,IGGⅢ-GWR比GWR性能分别提升了12.65%、7.44%、0.37%,比ACV-GWR分别提升了11.85%、6.96%、0.34%。试验结果表明,基于IGGⅢ的地理加权回归可提高模型的抗差能力,拟合效果更好。     

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

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

GBGWR模型在降水量空间分布模拟中的应用

近年来,我国大部分地区屡遭洪涝与干旱两种自然灾害侵袭,对重洪涝干旱区域进行空间插值具有重要的意义。针对传统地理加权回归（GWR）模型建模过程中模型识别和参数估计易受观测值异常点影响的问题,本文提出了一种基于吉布斯采样的贝叶斯地理加权回归（GBGWR）方法。运用基于吉布斯采样的马尔可夫链蒙特卡罗贝叶斯方法,估计地理加权回归模型参数,通过平滑函数降低观测值中异常点位数据,最后对湖南省1985-2015年35个观测站点的降水观测数据进行了空间分布模拟。试验结果表明,本文提出的方法相较于GWR模型性能提高了19.8%,相较于BGWR模型性能提高了8.2%,该方法可以有效降低异常值和"弱数据"对回归结果的影响,能够更加真实地模拟湖南省降水量的空间分布。     

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

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

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

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

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

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

顾及PWV的中南4省1区春节期间PM2.5浓度估算

社会经济的发展伴随而来的环境污染问题日渐得到人们的重视.针对中南地区4省1区(河南省、湖北省、湖南省、广东省和广西壮族自治区)春节期间PM2.5的变化情况,结合该区域所属及其相邻探空站获取的大气可降水量PWV数据以及气象监测站获取的风速数据,通过反距离加权插值得到中南4省1区春节期间的PWV和风速值,综合考虑CO、SO2、O3和NO2等大气污染物以及PWV、风速和DEM高程值建立该地区春节期间的地理加权回归(GWR)、地理加权回归克里金(GWRK)以及地理加权回归规则样条(GWRCRS)插值模型,并运用3种模型对中南地区4省1区2017、2018年春节假期期间进行PM2.5浓度估算.研究结果显示,GWRK和GWRCRS模型的估算效果较GWR模型更优,而GWRCRS模型估算精度最高,对中南地区4省1区春节期间的PM2.5监测预警具有一定的实用性参考价值.     

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

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

基于机群的并行匹配算法

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

计算子午线弧长的三类算法及其分析比较"

多项式展开算法是计算子午线弧长的传统方法,为了研究利用数值积分算法和常微分方程数值解法进行子午线弧长计算的可行性与可靠性,本文选取大地纬度自0°至90°的3组样本数据(间隔距离分别为1°、1'、1″),分别基于多项式展开数值积分算法和常微分方程数值解法,计算得到各组样本数据的子午线弧长,并通过算法计算结果精度和运算速度两个方面对数值算法的质量进行了评价。计算结果表明:数值积分算法和常微分方程数值解法均可以得到与多项式展开算法精度相同的结果;数值积分算法可通过减小步长以提高计算结果精度,但运算速度急剧降低;3阶、4阶的Runge-Kutta算法不仅运算结果精度高,而且运算速度也比传统算法快3倍多,表明了常微分方程数值解法更适用于子午线弧长的大数据计算。     

GNSS大网双差模型并行快速解算方法

针对GNSS大网数据采用双差模型解算时存在时效性差的问题,提出了一种改进的独立双差观测值构建与独立基线并行解算的方法,采用并行技术实现多核并行与网络多节点并行的双层自动快速解算策略。通过对约375个IGS站1周的观测数据进行处理,改进的独立双差观测值选取方法比传统路径最短方法所选的单天全网独立双差数据平均多了53万个,E、N、U方向坐标重复性平均提升了14.0%、12.9%和29.2%。采用不同解算策略的计算结果表明,4台普通计算机的并行计算比传统串行方案的计算效率提升了14倍左右,如375个测站采用改进观测值构建方法的4节点并行方案仅需要35.62min,显著提高了整网双差的解算效率。     

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

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

X波段航海雷达图像噪声检测与滤除方法研究

根据航海雷达数据的时空特点,提出一种图像噪声检测与滤除方法。该方法首先根据噪声在各次扫描间的不相关性对其进行检测,然后只针对检测出的噪声数据进行滤除。通过与传统的中值滤波算法和均值算法进行比较,同时使用信噪比指标对处理结果进行分析,结果表明,本算法既保持了传统中值滤波方法简单、快速的优点,又很好地保持了图像的灰度信息,具有较好的降噪效果。     

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

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

利用MPI并行算法实现球谐综合的效率分析

分析了求解地球重力场参量的球谐综合计算公式,引入数组预存再调用方法来避免传统算法中对cos（mλ）、sin（mλ）及勒让德函数的递推系数的重复计算问题,并结合MPI（message passing interface）并行技术来提高计算效率。实验采用2 160阶次的EGM2008模型,以DELL PowerEdge R730服务器和超算“天河二号”为计算平台,计算了分辨率1°和5'的网格重力异常。结果表明,数组预存再调用的方式减少了中央处理器（central processing unit,CPU）的计算工作量,但同时增加了内存的访问次数,适用于CPU性能一般而内存频率较高的计算平台。MPI并行技术可充分发挥计算机的多核优势,并在进程个数等于逻辑CPU的个数时获得最大加速比。     

A Parallel Scheme for Large‐scale Polygon Rasterization on CUDA‐enabled GPUs

This research develops a parallel scheme to adopt multiple graphics processing units (GPUs) to accelerate large‐scale polygon rasterization. Three new parallel strategies are proposed. First, a decomposition strategy considering the calculation complexity of polygons and limited GPU memory is developed to achieve balanced workloads among multiple GPUs. Second, a parallel CPU/GPU scheduling strategy is proposed to conceal the data read/write times. The CPU is engaged with data reads/writes while the GPU rasterizes the polygons in parallel. This strategy can save considerable time spent in reading and writing, further improving the parallel efficiency. Third, a strategy for utilizing the GPU's internal memory and cache is proposed to reduce the time required to access the data. The parallel boundary algebra filling (BAF) algorithm is implemented using the programming models of compute unified device architecture (CUDA), message passing interface (MPI), and open multi‐processing (OpenMP). Experimental results confirm that the implemented parallel algorithm delivers apparent acceleration when a massive dataset is addressed (50.32 GB with approximately 1.3 × 10⁸ polygons), reducing conversion time from 25.43 to 0.69 h, and obtaining a speedup ratio of 36.91. The proposed parallel strategies outperform the conventional method and can be effectively extended to a CPU‐based environment.     

计算子午线弧长与底点纬度的常微分方程数值解法

计算子午线弧长与底点纬度本质上是解算标准的一阶常微分方程。为了研究利用常微分方程数值解法进行子午线弧长与底点纬度计算的可行性与可靠性,选取大地纬度自0°起以步长1″依次增大至90°,共计324 001个样本数据,分别基于求解常微分方程的Euler算法、改进的Euler算法以及二阶、三阶、四阶Runge-Kutta算法对其进行了数值计算。并与传统算法结果进行比较,从数值算法结果的精度、运算速度、自洽程度等方面对数值算法质量进行评价。计算结果表明:利用常微分方程数值解法求解子午线弧长与底点纬度的方法,能够得到与传统算法精度一致的结果;且数值算法运算速度大约是传统算法的2倍,其中四阶Runge-Kutta算法的精度与自洽程度最高。这表明,常微分方程数值解法比传统算法更适用于子午线弧长和底点纬度的大数据计算。