| Kriging interpolation algorithm is one of Best Linear Unbiased Estimate(BLUE) spatial interpolation algorithms, which have been widely used in the fields of mining, hydrogeology, environmental science, and remote sensing etc. In some large-scale engineering applications, there usually are very large amount of data need to be dealt with, where the computation increases exponentially as the size of the data sets gets larger. Under this circumstance, utilizing certain high performance computing technologies, such as parallel computing on clusters, or on multi/many-core platforms, becomes the primary solution. However, there are still many problems and challenges to be resolved: 1) On traditional PC clusters, Kriging algorithm shows poor linear expansibility and highly energy consumption; 2) On multi-core platform, Kriging algorithm shows poor efficiency as it was not originally designed and optimized for multi-cores platforms, which are relatively new; and 3) On many-core platforms, e.g., GPU, there are still many difficulties in developing portable parallel codes. For instance, a program developed with CUDA cannot run on AMD GPU platform directly.With the rapid development of computing technologies in both hardware and software, the heterogeneous computing emerged and becomes more and more important for its excellent features, such as enormous computing power, strong adaptability and extensibility. In order to address the above-mentioned problems in Kriging algorithm, this research aims to design and implement a parallel universal Kriging interpolation algorithm with OpenCL, a heterogeneous computing programming model, on heterogeneous computing platforms(CPU+GPU/MIC). The main contributions of the work include:(1) Implemented the serial universal Kriging algorithm, and tested the implementation’s correctness with the professional GIS software by selecting the corresponding input parameters for the algorithm.(2) Got the hotspots of the serial implementation with professional performance analysis tools. A parallel software framework was designed and a parallel universal Kriging algorithm was implemented. The parallel implementation was tested and benchmarked to show satisfactory results.(3) The implementation of the parallel algorithm can only use a single computing device, either the GPU card or MIC card. In order to efficiently use all the computing resources available, a dynamic load balance strategy for the task scheduling is designed. With this technique, the constructed parallel algorithm can fully leverage the computing resources effectively.Finally, different versions of the parallel universal Kriging algorithm have been tested on two different heterogeneous computing platforms, one is CPU+GPU, and the other is CPU+MIC. In the experiments, the parameters and inputting data size are different to detect the differences of the sequential and parallel algorithms. The experiment results show that: 1) On the GPU platform, the parallel algorithm can get a speed-up up to 40 X and almost reaches it’s the theoretical peak. 2) On MIC platform, the parallel algorithm can be executed without any modification to the codes and also achieves satisfactory efficiency. Our implementation of the parallel algorithm has been demonstrated to be portable across platforms. 3) On the platform that has multiple devices, the parallel algorithm equipped with a dynamic load balance strategy can reach a speedup up to 80 X. Furthermore, the obtained speedup is lineally increasing with the number of involved computing devices.In summary, the research has certain significance in high performance Geo-computing area and shall be found useful for those researchers in this field. |
PDF Full Text Request