时空大数据背景下并行数据处理分析挖掘的进展及趋势

随着互联网、物联网和云计算的高速发展,与时间、空间相关的数据呈现出“爆炸式”增长的趋势,时空大数据时代已经来临。时空大数据除具备大数据典型的“4V”特性外,还具备丰富的语义特征和时空动态关联特性,已经成为地理学者分析自然地理环境、感知人类社会活动规律的重要资源。然而在具体研究应用中,传统数据处理和分析方法已无法满足时空大数据高效存取、实时处理、智能挖掘的性能需求。因此,时空大数据与高性能计算/云计算融合是必然的发展趋势。在此背景下,本文首先从大数据的起源出发,回顾了大数据概念的发展历程,以及时空大数据的特有特征;然后分析了时空大数据研究应用产生的性能需求,总结了底层平台软硬件的发展现状;进而重点从时空大数据的存储管理、时空分析和领域挖掘3个角度对并行化现状进行了总结,阐述了其中存在的问题;最后指出了时空大数据研究发展趋势。     

A parallel method to accelerate spatial operations involving polygon intersections

Polygon intersection is an important spatial data-handling process, on which many spatial operations are based. However, this process is computationally intensive because it involves the detection and calculation of polygon intersections. We addressed this computation issue based on two perspectives. First, we improved a method called boundary algebra filling to efficiently rasterize the input polygons. Polygon intersections were subsequently detected in the cells of the raster. Owing to the use of a raster data structure, this method offers advantages of reduced task dependence and improved performance. Based on this method, we developed parallel strategies for different procedures in terms of workload decomposition and task scheduling. Thus, the workload across different parallel processes can be balanced. The results suggest that our method can effectively accelerate the process of polygon intersection. When addressing datasets with 1,409,020 groups of overlapping polygons, our method could reduce the total execution time from 987.82 to 53.66 s, thereby obtaining an optimal speedup ratio of 18.41 while consistently balancing the workloads. We also tested the effect of task scheduling on the parallel efficiency, showing that reducing the total runtime is effective, especially for a lower number of processes. Finally, the good scalability of the method is demonstrated.     

gLucifer: next generation visualization framework for high-performance computational geodynamics

High-performance computing provides unprecedented capabilities to produce higher resolution 4-D models in a fraction of time. Thus, the need exists for a new generation of visualization systems able to maintain parity with the enormous volume of data generated. In attempting to write this much data to disk, each computational step introduces a significant performance bottleneck, yet most existing visualization software packages inherently rely on reading data in from a dump file. Available packages make this assumption of postprocessing at quite a fundamental level and are not very well suited for plotting very large numbers of specialized particles. This necessitates the creation of a new visualization system that meets the needs of large-scale geodynamic modeling. We have developed such a system, gLucifer, using a software framework approach that allows efficient reuse of our efforts in other areas of research. gLucifer is capable of producing movies of a 4-D data set “on the fly” (simultaneously with running the parallel scientific application) without creating a performance bottleneck. By eliminating most of the human efforts involved in visualizing results through postprocessing, gLucifer reconnects the scientist to the numerical experiment as it unfolds. Data sets that were previously very difficult to even manage may be efficiently explored and interrogated without writing to disk, and because this approach is based entirely on memory distributed across as many processors as are being utilized by the scientific application, the visualization solution is scalable into terabytes of data being rendered in real time.     

Interactive visualization of 3D mantle convection

The current availability of thousands of processors at many high performance computing centers has made it feasible to carry out, in near real time, interactive visualization of 3D mantle convection temperature fields, using grid configurations having 10–100 million unknowns. We will describe the technical details involved in carrying out this endeavor, using the facilities available at the Laboratory of Computational Science and Engineering (LCSE) at the University of Minnesota. These technical details involve the modification of a parallel mantle convection program, ACuTEMan; the usage of client–server socket based programs to transfer upwards of a terabyte of time series scientific model data using a local network; a rendering system containing multiple nodes; a high resolution PowerWall display, and the interactive visualization software, DSCVR. We have found that working in an interactive visualizastion mode allows for fast and efficient analysis of mantle convection results. Electronic supplementary material  The online version of this article (doi:) contains supplementary material, which is available to authorized users.     

基于GPU的任意多边形相交面积计算方法

一直以来,任意多边形相交面积的高效计算都是地理信息系统中空间分析算法研究的重点。文中提出了一种基于GPU的栅格化多边形相交面积算法GPURAS,在此基础上,分别采用蒙特卡罗方法和遮挡查询技术进一步提出GPURASMC算法和GPURASQ算法,并证明了上述算法的正确性。实验对简单多边形、任意复杂多边形及大数据量多边形进行了测试对比,结果表明:GPURAS算法精度高,通用性较好但效率受CPU与GPU通信延迟的影响;GPURASMC算法效率较高但牺牲了部分精度;GPURASQ算法精度高、效率高但局限于特定运行环境。与基于CPU的传统算法相比,文中所提3种算法效率更高,在处理包含大量顶点的多边形时,效率提升尤为明显。     

An innovative GPS trajectory data based model for geographic recommendation service

Geographic services based on GPS trajectory data, such as location prediction and recommender services, have received increasing attention because of their potential social and commercial benefits. In this study, a Geographic Service Recommender Model (GSRM) is proposed, which loosely comprises three essential steps. Firstly, location sequences are obtained through a clustering operation on GPS locations. To improve efficiency, a programming model with a distributed algorithm is employed to accelerate the clustering. Secondly, in order to mine spatial and temporal information from the cluster trajectory, an algorithm (MiningMP) is designed. Last but not least, the next possible location to which the user will travel is predicted. An integrated framework of GSRM could then be constructed and provide the appropriate geographic recommendation service by considering location sequences as well as other related semantic information. Experiments were conducted based on real GPS trajectories from Microsoft Research Asia (182 users within a period of five years). The experimental results clearly demonstrate that our proposed GSRM model is effective and efficient at predicting locations and can provide users with personalized smart recommendation services in the following possible position with excellent performance in scalability, adaptability, and quality of service.     

Optimization of simulation and visualization analysis of dam-failure flood disaster for diverse computing systems

Simulation and subsequent visualization in a network environment are important to glean insights into spatiotemporal processes. As computing systems become increasingly diverse in hardware architectures, operating systems, screen sizes, human–computer interactions and network capabilities, effective simulation and visualization must become adaptive to a wide range of diverse devices. This paper focuses on the optimization of simulation and visualization analysis of the dam-failure flood spatiotemporal process for diverse computing systems. First, an adaptive browser/server architecture of the dam-failure simulation application was designed to fill the hardware performance and visualization context gap that exists within diverse computing systems. Second, a data flow and an optimization method for multilevel time-series flood data were given to provide more support to network simulation, visualization and analysis on diversified terminals. Finally, a user interaction friendly and plugin-free prototype system was developed. The experiment results demonstrate that the methods addressed in this paper can cope with the challenge in simulation, visualization and interaction of a dam-failure simulation application on diversified terminals.     

基于GPU的并行条件模拟算法及其在储量估算中的应用

条件模拟是一种计算非常耗时的高精度三维插值算法。针对串行条件模拟算法计算时间过长的问题,提出基于GPU的并行条件模拟算法,并进行储量估算。对条件模拟算法进行并行分析,利用GPU的高度并行性,构建CUDA通用计算开发环境,实现串行条件模拟算法到并行条件模拟算法的转换,使条件模拟算法的时间复杂度从O(n)降至O(logn)。并对西藏甲玛铜矿进行了储量估算。实验结果表明,在安装普通NVIDIA显卡的计算机以及估算精度不下降的情况下,GPU并行条件模拟的计算效率比CPU串行条件模拟的计算效率提高了60倍以上。     

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

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