本文關鍵詞：異構計算環(huán)境下的地圖代數(shù)空間分析并行方法研究　出處：《中國地質大學》2013年碩士論文　論文類型：學位論文

  更多相關文章： 異構計算 GPGPU CUDA 空間分析 地圖代數(shù)

【摘要】：一直以來,如何快速地從空間數(shù)據(jù)中提取更加豐富和有用的信息,為人們有效地管理和利用空間數(shù)據(jù)提供信息決策參考是空間分析研究人員的目標。隨著全球范圍測量精度的不斷提高,空間分析應用數(shù)據(jù)源的數(shù)據(jù)量也在逐步增加。雖然在過去的幾十年里,CPU通過不斷地提高制作工藝,性能在逐步提升,浮點運算能力也達到了較高的水平,但隨之而來的散熱和能耗等問題,導致CPU時鐘頻率無法顯著提高,單CPU執(zhí)行能力的提升遇到了瓶頸,浮點運算能力的提升也在放緩,相對于日益增長的空間數(shù)據(jù),緩慢提升的CPU浮點計算能力顯得明顯不足,嚴重影響了空間分析的計算速度,從而限制了諸多優(yōu)秀的空間分析算子的應用。 面對現(xiàn)有計算平臺浮點計算能力上的限制和各應用領域巨大的計算需求,人們開始探索其它的解決方案,微處理器也隨之進入多核時代,并行編程的重要性日益凸顯,各領域的科研和開發(fā)人員紛紛開始嘗試使用并行編程來加速計算。異構計算(Heterogeneous Computing)是一種特殊形式的并行計算,它的基本思想是將功能或性能相異的計算設備通過高速網絡連接起來,并將計算任務劃分成一組計算類型不同的子任務,分配到合適的計算設備上進行計算,充分利用各計算設備的優(yōu)勢,從整體上減少完成計算任務所需的時間,突破同構計算平臺的計算能力瓶頸。異構計算具有成本低、能耗低、可擴展性強等特點,因此比傳統(tǒng)的同構并行計算更加適合空間分析這類海量數(shù)據(jù)的計算。CPU+GPU異構計算平臺是目前主流的異構計算平臺,在“全球超級計算機TOP500排行榜”上占據(jù)著異構計算架構的主導地位。 當前,除了浮點計算能力不足以外,空間分析進一步發(fā)展的難點在于其計算的普適性、準確性和規(guī)范性。地圖代數(shù)存在著廣厚的數(shù)學基礎,采用代數(shù)觀點全面闡述地理信息處理和可視化本質與過程的理論和方法,是空間分析的有力工具。地圖代數(shù)作為一種以柵格點集的變換和運算來解決地理信息的圖形符號的可視化和空間分析的理論和方法,更能適應全球環(huán)境下的大范圍多維、多源空間信息數(shù)據(jù)的動態(tài)分析過程。 本文針對CPU+GPU所構成的異構環(huán)境,以基于柵格點集、處理流程相對固定、數(shù)據(jù)處理具有內在并行性的地圖代數(shù)為研究對象,從空間分析并行映射角度,對相應地圖代數(shù)算子進行并行加速策略的研究,采用數(shù)據(jù)分割策略,借助操作的重疊隱藏數(shù)據(jù)傳輸?shù)臅r間、并行計算減少算子運算的時間,采用數(shù)據(jù)預處理策略,突破磁盤-內存?zhèn)鬏斔俣鹊钠款i。主要研究內容包括： (1)對基于柵格點集、處理流程相對固定、數(shù)據(jù)處理具有內在并行性的地圖代數(shù)算子的CPU串行實現(xiàn)進行CUDA并行化：研究算子的處理特點,將浮點運算密集的操作、適合并行執(zhí)行的操作從CPU中剝離出來,交由GPU來處理,從而解放CPU資源,同時充分利用GPU的浮點運算、高并發(fā)的優(yōu)勢。 (2)針對算子的計算性質,選擇合適的數(shù)據(jù)分割策略,對大數(shù)據(jù)量柵格點集進行拆分,通過數(shù)據(jù)傳輸與數(shù)據(jù)處理的時間重疊隱藏數(shù)據(jù)傳輸時間。并不斷實驗、優(yōu)化數(shù)據(jù)分割策略,從而在不同的計算條件下均能夠達到較好的數(shù)據(jù)傳輸時間隱藏效果。 (3)研究內存-顯存的按塊傳輸?shù)臄?shù)據(jù)傳輸模式,選擇與之相適配的柵格數(shù)據(jù)存儲結構,并設計適合按塊讀取的柵格數(shù)據(jù)文件格式、相應的訪問接口,以改變對現(xiàn)有柵格數(shù)據(jù)文件格式的按坐標逐像元值讀取的讀取模式,突破磁盤-內存的讀取瓶頸。同時,將于空間分析計算無關的數(shù)據(jù)從柵格數(shù)據(jù)文件中剔出,減少空間分析計算過程中的I/O數(shù)據(jù)量。 最后,本文選擇了具有代表性的地圖代數(shù)算子LPos在NVIDIA推出的GeForce、Quadro和Tesla三種不同級別的CUDA計算硬件環(huán)境下對空間柵格數(shù)據(jù)進行了多組實驗,分別對比了這些算子的CPU串行實現(xiàn)、CUDA并行實現(xiàn)、經過數(shù)據(jù)分割優(yōu)化的CUDA并行實現(xiàn)的運行結果和耗時,驗證了論文研究的關鍵方法與技術的正確性。
[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

【參考文獻】

相關期刊論文 前10條

1 耿協(xié)鵬;楊傳勇;胡鵬;;基于地圖代數(shù)距離變換的空間實體分布的聚集度分析[J];測繪科學;2006年02期

2 郭金來;胡鵬;;網絡最短路徑的地圖代數(shù)柵格算法[J];測繪科學;2007年01期

3 農宇;陳飛;;土地利用現(xiàn)狀圖掃描符號的自動提取與識別[J];測繪科學;2011年02期

4 張劍波;楊文鑫;周斯波;張帥;;利用CUDA的地圖代數(shù)局部算子優(yōu)化[J];測繪科學;2012年02期

5 袁友偉;;采用GPU加速的三維實體模型繪制[J];電子學報;2008年S1期

6 張劍波;周斯波;張帥;;CUDA加速的地圖代數(shù)并行算法[J];桂林理工大學學報;2011年01期

7 楊學軍,戴華東,夏軍;多處理器系統(tǒng)中的數(shù)據(jù)局部性及其優(yōu)化技術研究[J];中國工程科學;2002年05期

8 蘇超軾;趙明昌;張向文;;GPU加速的八叉樹體繪制算法[J];計算機應用;2008年05期

9 吳連貴;易瑜;李肯立;;基于CUDA的地震數(shù)據(jù)相干體并行算法[J];計算機應用;2009年03期

10 田緒紅;江敏杰;;GPU加速的神經網絡BP算法[J];計算機應用研究;2009年05期

，

本文編號：1384356