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.     

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

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

Geocomputation over the Emerging Heterogeneous Computing Infrastructure

Emerging computer architectures and systems that combine multi‐core CPUs and accelerator technologies, like many‐core Graphic Processing Units (GPUs) and Intel's Many Integrated Core (MIC) coprocessors, would provide substantial computing power for many time‐consuming spatial‐temporal computation and applications. Although a distributed computing environment is suitable for large‐scale geospatial computation, emerging advanced computing infrastructure remains unexplored in GIScience applications. This article introduces three categories of geospatial applications by effectively exploiting clusters of CPUs, GPUs and MICs for comparative analysis. Within these three benchmark tests, the GPU clusters exemplify advantages in the use case of embarrassingly parallelism. For spatial computation that has light communication between the computing nodes, GPU clusters present a similar performance to that of the MIC clusters when large data is applied. For applications that have intensive data communication between the computing nodes, MIC clusters could display better performance than GPU clusters. This conclusion will be beneficial to the future endeavors of the GIScience community to deploy the emerging heterogeneous computing infrastructure efficiently to achieve high or better performance spatial computation over big data.     

Out‐of‐Core GPU‐based Change Detection in Massive 3D Point Clouds

If sites, cities, and landscapes are captured at different points in time using technology such as LiDAR, large collections of 3D point clouds result. Their efficient storage, processing, analysis, and presentation constitute a challenging task because of limited computation, memory, and time resources. In this work, we present an approach to detect changes in massive 3D point clouds based on an out‐of‐core spatial data structure that is designed to store data acquired at different points in time and to efficiently attribute 3D points with distance information. Based on this data structure, we present and evaluate different processing schemes optimized for performing the calculation on the CPU and GPU. In addition, we present a point‐based rendering technique adapted for attributed 3D point clouds, to enable effective out‐of‐core real‐time visualization of the computation results. Our approach enables conclusions to be drawn about temporal changes in large highly accurate 3D geodata sets of a captured area at reasonable preprocessing and rendering times. We evaluate our approach with two data sets from different points in time for the urban area of a city, describe its characteristics, and report on applications.     

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

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

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

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

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

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

An efficient geosciences workflow on multi-core processors and GPUs: a case study for aerosol optical depth retrieval from MODIS satellite data

Quantitative remote sensing retrieval algorithms help understanding the dynamic aspects of Digital Earth. However, the Big Data and complex models in Digital Earth pose grand challenges for computation infrastructures. In this article, taking the aerosol optical depth (AOD) retrieval as a study case, we exploit parallel computing methods for high efficient geophysical parameter retrieval. We present an efficient geocomputation workflow for the AOD calculation from the Moderate Resolution Imaging Spectroradiometer (MODIS) satellite data. According to their individual potential for parallelization, several procedures were adapted and implemented for a successful parallel execution on multi-core processors and Graphics Processing Units (GPUs). The benchmarks in this paper validate the high parallel performance of the retrieval workflow with speedups of up to 5.x on a multi-core processor with 8 threads and 43.x on a GPU. To specifically address the time-consuming model retrieval part, hybrid parallel patterns which combine the multi-core processor’s and the GPU’s compute power were implemented with static and dynamic workload distributions and evaluated on two systems with different CPU–GPU configurations. It is shown that only the dynamic hybrid implementation leads to a greatly enhanced overall exploitation of the heterogeneous hardware environment in varying circumstances.     

并行处理技术在全球海量地理信息数据质量控制中的应用

针对全球海量地理信息数据成果数据量大、数据类型丰富、质量检查内容多的特点,本文将分布式并行计算技术、多线程技术应用到地理信息数据质量控制体系中,基于MapReduce框架实现了多源多时相海量数据并行质量控制,把算法结构由一个周期执行一个操作改造为一个周期执行多个操作的并行处理,从根本上解决重复操作多、计算慢的质量检查难题。选取核心矢量要素、DOM成果、DEM成果作为典型数据案例开展效率对比试验。试验结果表明,该技术方案的处理效率比传统技术方案提高2~3倍,有效地压缩了任务执行时间,节约了任务执行成本,实现了对海量地理信息数据的快速质量控制,保障了全球地理信息数据的成果质量。     

Concurrent Drainage Network Rendering for Automated Pen‐and‐ink Style Landscape Illustration

Pen‐and‐ink style geomorphological illustrations render landscape elements critical to the understanding of surface processes within a viewshed and, at their highest levels of execution, represent works of art, being both practical and beautiful. The execution of a pen‐and‐ink composition, however, requires inordinate amounts of time and skill. This article will introduce an algorithm for rendering creases – linework representing visually significant morphological features – at animation speeds, made possible with recent advances in graphics processing unit (GPU) architectures and rendering APIs. Beginning with a preprocessed high‐resolution drainage network model, creases are rendered from selected stream segments if their weighted criteria (slope, flow accumulation, and surface illumination), attenuated by perspective distance from the viewpoint, exceed a threshold. The algorithm thus provides a methodology for crease representation at continuous levels of detail down to the highest resolution of the preprocessed drainage model over a range of surface orientation and illumination conditions. The article also presents an implementation of the crease algorithm with frame rates exceeding those necessary to support animation, supporting the proposition that parallel processing techniques exposed through modern GPU programming environments provide cartographers with a new and inexpensive toolkit for constructing alternative and attractive real‐time animated landscape visualizations for spatial analysis.     

多级存储优化的大规模全局光照快速计算

针对大规模复杂场景渲染的全局光照计算量大从而影响其渲染实时性的问题,提出了一种基于多级分辨率纹理存储结构的改进体素锥追踪全局光照算法。算法首先采用基于人眼视觉特性的多级分辨率纹理存储结构高效存储光照信息,并在直接光照计算时,结合存储结果特点,然后采用混合存储的GPU硬件加速与无贡献节点丢弃的软件加速相结合方法,进一步提高光照渲染效率,最后基于多级纹理及闭合体节点自适应合并对锥波滤器进行改进,实现全局光照的高效计算。试验结果表明,改进算法减少了光照计算量,降低了系统内存占用,并取得了与经典算法相近的场景光照渲染效果,从而验证了其在大规模光照计算的有效性。     

基于 GPU 的 GNSS 信号跟踪设计与实现

软件接收机在数据后处理、算法设计与分析等方面发挥着重要的作用。由于传统的软件接收机均是由CPU 处理器实现,处理效率低下。图像处理单元是高度并行化的处理器,将导航信号处理中并行程度高且对时间要求最为严格的跟踪环节与GPU 的并行处理结构有机结合,能大大提升程序的效率。本文解决了采用GPU实现信号跟踪的关键技术,给出了相关的设计方案,并实现。试验结果表明：采用GPU 实现信号的跟踪,其效率提升了112.5倍。     

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

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

一种利用GPU加速的轨迹线热力图生成显示方法

为解决大数据量带来的热力图生成效率低的问题,引入基于图形处理器(graphic processing unit,GPU)的并行计算方法,并结合轨迹线模型,提出了一种利用GPU加速的轨迹线热力图生成显示方法。首先,针对轨迹点分布不均、邻域半径设置不合理等条件下产生的热力值不连续、不均等问题,采用轨迹线模型提升了热力图的效果。其次,针对大规模数据计算产生的热力图生成效率低的问题,通过GPU并行计算并配合内核函数参数调优、循环展开、像素缓冲对象显示等策略大幅提升算法计算效率。实验结果表明,所提方法较传统的基于中央处理器（central processing unit, CPU）的方法计算效率提升了5~30倍,且随着图像分辨率和轨迹数据的增加,算法加速比有逐步上升的趋势。     

面向WebGL的矢量数据三维绘制技术

矢量数据的叠加显示能够提高三维虚拟地球的表达效果与分析能力。受限于GPU的计算精度,在三维虚拟地球中矢量数据绘制普遍存在抖动现象和深度冲突现象。对基于WebGL的矢量数据三维绘制中计算精度问题进行了分析,提出了使用CPU RTC技术和GPU RTE技术提高顶点变换的精度,使用多视锥渲染算法和深度平面技术解决深度缓存精度问题。实验证明,这几种技术和算法可以有效缓解抖动现象和深度冲突现象导致的视觉干扰,改善了各种尺度和范围的矢量数据在三维地形上的叠加显示效果。     

Fast Image‐Space Silhouette Extraction for Non‐Photorealistic Landscape Rendering

Landscape illustration, a core visualization technique for field geologists and geomorphologists, employs the parsimonious use of linework to represent surface structure in a straightforward and intuitive manner. Under the rubric of non‐photorealistic rendering (NPR), automated procedures in this vein render silhouettes and creases to represent, respectively, view‐dependent and view‐independent landscape features. This article presents two algorithms and implementations for rendering silhouettes from adaptive tessellations of point‐normal (PN) triangles at speeds approaching those suitable for animation. PN triangles use cubic polynomial models to provide a surface that appears smooth at any required resolution. The first algorithm, drawing on standard silhouette detection techniques in surface meshes, builds object space facet adjacencies and image space pixel adjacencies in the graphics pipeline following adaptive tessellation. The second makes exclusive use of image space analysis without referencing the underlying scene world geometry. Other than initial pre‐processing operations, recent advances in the OpenGL API allow implementations for both algorithms to be hosted entirely on the graphics processing unit (GPU), eliminating slowdowns through data transfer across the system memory bus. We show that both algorithms provide viable paths to real‐time animation of pen and ink style landscape illustrations but that the second demonstrates superior performance over the first.     

Parallel algorithm for viewshed analysis on a modern GPU

Spatial analysis, including viewshed analysis, is an important aspect of the Digital Earth system. Viewshed analysis is usually performed on a large scale, so efficiency is important in any Digital Earth application making these calculations. In this paper, a real-time algorithm for viewshed analysis in 3D scenes is presented by using the parallel computing capabilities of a graphics processing unit (GPU). In contrast to traditional algorithms based on line-of-sight, this algorithm runs completely within the programmable 3D visualization pipeline to render 3D terrains with viewshed analysis. The most important difference is its integration of the viewshed calculation with the rendering module. Invisible areas are rendered as shadows in the 3D scene. The algorithm process is paralleled by rasterizer units in the graphics card and by vertex and pixel shaders executed on the GPU. We have implemented this method in our 3D Digital Earth system with the DirectX 9.0c API and tested on some consumer-level PC platforms with interactive frame-rates and high image quality. Our algorithm has been widely used in related systems based on Digital Earth.     

基于多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倍的加速比,其执行效率明显提高,对于大规模数据处理呈现出良好的实时处理能力。     

轨迹大数据云存储与热力图生成方法

针对目前轨迹大数据基于WebGIS的热力图展示中的成图耗时较长、用户移动缩放交互差等问题,本文建立了基于HBase的轨迹数据与地图数据存储模型,为轨迹大数据在电子地图上进行热力图展示提供了存储方法,同时提出一种基于聚类处理的轨迹数据热力图可视化方法,针对不同缩放级别能够有效地减少数据绘制计算量与数据传输量,较大地提升了热力图渲染与展示的效率。试验证明,该方案能够实现轨迹数据、电子地图数据的存储,提高热力图可视化绘制效率,能够为轨迹数据挖掘与分析提供技术支撑。     

并行处理技术在地理信息数据处理中的应用

随着地理信息存储量的飞速增长,传统的单进程、集中式的数据处理方式已不能满足基于网络的地理信息服务的效能要求。分析对比了OpenMP,MPI和MapReduce等主流并行编程模式,将关系型数据库与分布式空间数据管理系统相结合,提出了面向并行处理的地理信息存储模型和数据组织模型,将该模型与传统模型进行了对比分析,并基于MapReduce实现了地理空间数据并行处理框架,选取了矢量数据装载、影像数据装载以及数据切片作为典型数据处理案例开展对比实验,该技术方案的处理效率均数倍于传统技术方案。实验表明,该模型能够很好地支持并行处理框架,可为分布式环境下数据处理中心构建提供一个有效解决方案。