异构计算环境下的地图代数空间分析并行方法研究

发布时间：2018-01-05 18:36

本文关键词：异构计算环境下的地图代数空间分析并行方法研究　出处：《中国地质大学》2013年硕士论文　论文类型：学位论文

【摘要】：一直以来,如何快速地从空间数据中提取更加丰富和有用的信息,为人们有效地管理和利用空间数据提供信息决策参考是空间分析研究人员的目标。随着全球范围测量精度的不断提高,空间分析应用数据源的数据量也在逐步增加。虽然在过去的几十年里,CPU通过不断地提高制作工艺,性能在逐步提升,浮点运算能力也达到了较高的水平,但随之而来的散热和能耗等问题,导致CPU时钟频率无法显著提高,单CPU执行能力的提升遇到了瓶颈,浮点运算能力的提升也在放缓,相对于日益增长的空间数据,缓慢提升的CPU浮点计算能力显得明显不足,严重影响了空间分析的计算速度,从而限制了诸多优秀的空间分析算子的应用。面对现有计算平台浮点计算能力上的限制和各应用领域巨大的计算需求,人们开始探索其它的解决方案,微处理器也随之进入多核时代,并行编程的重要性日益凸显,各领域的科研和开发人员纷纷开始尝试使用并行编程来加速计算。异构计算(Heterogeneous Computing)是一种特殊形式的并行计算,它的基本思想是将功能或性能相异的计算设备通过高速网络连接起来,并将计算任务划分成一组计算类型不同的子任务,分配到合适的计算设备上进行计算,充分利用各计算设备的优势,从整体上减少完成计算任务所需的时间,突破同构计算平台的计算能力瓶颈。异构计算具有成本低、能耗低、可扩展性强等特点,因此比传统的同构并行计算更加适合空间分析这类海量数据的计算。CPU+GPU异构计算平台是目前主流的异构计算平台,在“全球超级计算机TOP500排行榜”上占据着异构计算架构的主导地位。当前,除了浮点计算能力不足以外,空间分析进一步发展的难点在于其计算的普适性、准确性和规范性。地图代数存在着广厚的数学基础,采用代数观点全面阐述地理信息处理和可视化本质与过程的理论和方法,是空间分析的有力工具。地图代数作为一种以栅格点集的变换和运算来解决地理信息的图形符号的可视化和空间分析的理论和方法,更能适应全球环境下的大范围多维、多源空间信息数据的动态分析过程。本文针对CPU+GPU所构成的异构环境,以基于栅格点集、处理流程相对固定、数据处理具有内在并行性的地图代数为研究对象,从空间分析并行映射角度,对相应地图代数算子进行并行加速策略的研究,采用数据分割策略,借助操作的重叠隐藏数据传输的时间、并行计算减少算子运算的时间,采用数据预处理策略,突破磁盘-内存传输速度的瓶颈。主要研究内容包括： (1)对基于栅格点集、处理流程相对固定、数据处理具有内在并行性的地图代数算子的CPU串行实现进行CUDA并行化：研究算子的处理特点,将浮点运算密集的操作、适合并行执行的操作从CPU中剥离出来,交由GPU来处理,从而解放CPU资源,同时充分利用GPU的浮点运算、高并发的优势。 (2)针对算子的计算性质,选择合适的数据分割策略,对大数据量栅格点集进行拆分,通过数据传输与数据处理的时间重叠隐藏数据传输时间。并不断实验、优化数据分割策略,从而在不同的计算条件下均能够达到较好的数据传输时间隐藏效果。 (3)研究内存-显存的按块传输的数据传输模式,选择与之相适配的栅格数据存储结构,并设计适合按块读取的栅格数据文件格式、相应的访问接口,以改变对现有栅格数据文件格式的按坐标逐像元值读取的读取模式,突破磁盘-内存的读取瓶颈。同时,将于空间分析计算无关的数据从栅格数据文件中剔出,减少空间分析计算过程中的I/O数据量。最后,本文选择了具有代表性的地图代数算子LPos在NVIDIA推出的GeForce、Quadro和Tesla三种不同级别的CUDA计算硬件环境下对空间栅格数据进行了多组实验,分别对比了这些算子的CPU串行实现、CUDA并行实现、经过数据分割优化的CUDA并行实现的运行结果和耗时,验证了论文研究的关键方法与技术的正确性。
[Abstract]:All the time, how to quickly extract more rich and useful information from spatial data, for people to effectively manage and use the spatial data to provide information and decision-making reference is a spatial analysis of the goal of researchers worldwide. With the improvement of measurement accuracy, data analysis and application of the data source space has gradually increased. Although in the past for decades, CPU by constantly improving the production process, performance gradually improve, floating-point ability have reached a higher level, but the resulting heat and energy consumption and other issues, leading to CPU clock frequency can significantly improve, enhance the execution ability of single CPU encountered a bottleneck, enhance the ability in floating-point operations slow growing compared with spatial data, slowly increase CPU floating-point computing capacity is obviously insufficient, serious impact on the calculation speed of spatial analysis, from which limits the The application of many excellent spatial analysis operators.
The face of the existing computing platform floating-point computation ability of the limitations and the various application fields of huge computing demand, people began to explore other solutions, the microprocessor has entered the era of multi-core parallel programming, importance has become increasingly prominent, in various fields of scientific research and development personnel have begun to try to use parallel programming to accelerate the computation of heterogeneous computing (Heterogeneous. Computing) is a special form of parallel computing, the basic idea is to connect the function or performance of different computing devices through high-speed network and computing tasks will be partitioned into a set of calculation of different types of sub tasks assigned to the computing device suitable for calculation, the full use of the advantages of computing devices, reduce the time required to complete computing tasks, breakthrough isomorphic computational ability bottleneck. Heterogeneous computing platform has the advantages of low cost, low energy consumption, can be Expansibility, so compared with the traditional homogeneous parallel computing is more suitable for spatial analysis of.CPU+GPU heterogeneous computing platform of this kind of data is the current mainstream heterogeneous computing platform dominated heterogeneous computing architecture in the "global supercomputer TOP500 list".
At present, in addition to floating-point computation ability is insufficient, the difficulty lies in the further development of the spatial analysis calculation of universality, accuracy and standardization. There is a mathematical basis of map algebra guanhou, the algebra view expounded the theory and method of geographic information processing and visualization of nature and process, is a powerful tool for spatial analysis. The theory and method of visualization and spatial analysis of graphic symbols as map algebra transformation and calculation with a grid point set to solve the geographical information, can adapt to a wide range of global environment, multidimensional, dynamic analysis process of multi-source spatial information data.
This paper consists of a heterogeneous environment for CPU+GPU, based on the grid point set, processing process is relatively fixed, data processing has the inherent parallelism of map algebra as the research object, from the perspective of spatial analysis of parallel mapping, the corresponding map algebra operators for parallel acceleration strategy research, using data partitioning strategy with overlapping hidden data transmission operation time, reduce operator parallel computing time, the strategy of data preprocessing, breaking the bottleneck of the transmission speed of the disk memory. The main contents include:
(1) based on grid points, process is relatively fixed, data processing has the inherent parallelism of the map algebra operator to achieve CPU serial parallel CUDA: processing characteristics of the operator, the floating-point intensive operation, suitable for parallel operation out stripped from the CPU, handled by GPU. In order to free CPU resources, and make full use of GPU floating-point operations, high concurrency.
(2) for calculating the properties of operators, choose the suitable data partitioning strategy to split a large amount of data points set, through the data transmission and data processing time overlapping hidden data transmission time. And continue to experiment, optimizing the data partitioning strategy, resulting in different calculation conditions were able to achieve better data transmission time hidden effect.
(3) research on memory - memory according to the data transmission mode of block transmission, selection of raster data storage structure matched with the design, and is suitable for block read raster data file format, access interface corresponding, to change the existing raster data file format according to the coordinates of each pixel value read read. Read the disk memory bottleneck breakthrough. At the same time, the calculation and analysis of independent data removed from the raster data file in space, the analysis of the I/O data in the process of calculation to reduce the amount of space.
Finally, this paper chooses the map algebra operator LPos representative at the NVIDIA launch of GeForce, Quadro and Tesla three different CUDA computing hardware environment of spatial raster data was carried out experiments, compared these operators CPU serial implementation, a parallel implementation of CUDA, the operation results after data segmentation optimization CUDA parallel implementation and time-consuming, to verify the correctness of the key methods and techniques of the research.

【学位授予单位】：中国地质大学
【学位级别】：硕士
【学位授予年份】：2013
【分类号】：TP338.6

【参考文献】