|
|
- 2017
一种面向CPU/GPU异构环境的协同并行空间插值算法
|
Abstract:
CPU/GPU异构混合系统是一种新型高性能计算平台，但现有并行空间插值算法仅依赖CPU或GPU进行加速，迫切需要研究协同并行空间插值算法以充分利用异构计算资源，进一步提升插值效率。以薄板样条函数插值为例，提出一种CPU/GPU协同并行插值算法以加速海量激光雷达（light detector&ranger，LiDAR）点云生成数字高程模型（DEM）。通过插值任务的分解与抽象封装以屏蔽底层硬件执行模式的差异性，同时在多级协同并行框架基础上设计了Greedy-SET动态调度策略，策略顾及底层硬件能力的差异性，以实现异构并行资源的充分利用和良好负载均衡。实验表明，协同并行插值算法在高性能工作站上取得19.6倍的加速比，相比单一CPU或GPU并行算法，其效率提升分别达到54%和44%，实现了高效的协同并行处理
| [1] | Liu Eryong, Wang Yunjia. Parallel IDW Algorithm Based on CUDA and Experimental Analysis[J]. Journal of Geo-information Science, 2011, 13(5):707-710(刘二永, 汪云甲. 基于CUDA的IDW并行算法及其实验分析[J]. 地球信息科学学报, 2011, 13(5):707-710) |
| [2] | Cheng T. Accelerating Universal Kriging Interpolation Algorithm Using CUDA-Enabled GPU[J]. Computers & Geosciences, 2013, 54(2013):178-183 |
| [3] | Ju Tao, Zhu Zhengdong, Dong Xiaoshe. The Feature, Programming Model and Performance Optimization Strategy of Heterogeneous Many-Core System:A Review[J]. Acta Electronica Sinica, 2015, 43(1):111-119(巨涛, 朱正东, 董小社. 异构众核系统及其编程模型与性能优化技术研究综述[J]. 电子学报, 2015, 43(1):111-119) |
| [4] | Jang H, Park A, Jung K. Neural Network Implementation Using CUDA and OpenMP[C]. International Conference on Digital Image Computing:Techniques and Applications (DICTA), Canberra, Australia, 2008 |
| [5] | Mitas L, Mitasova H. Spatial Interpolation[J]. Geographical Information Systems:Principles, Techniques, Management and Applications, 1999, 1:481-492 |
| [6] | Preis T, Virnau P, Paul W, et al. GPU Accelerated Monte Carlo Simulation of the 2D and 3D Ising Model[J]. Journal of Computational Physics, 2009, 228(12):4468-4477 |
| [7] | Jeon Y, Jung E, Min H, et al. GPU-Based Acceleration of an RNA Tertiary Structure Prediction Algorithm[J]. Computers in Biology and Medicine, 2013, 43(8):1011-1022 |
| [8] | Brovelli M, Cannata M. Digital Terrain Model Reconstruction in Urban Areas from Airborne Laser Scanning Data:the Method and an Example for Pavia (Northern Italy)[J]. Computers & Geosciences, 2004, 30(4):325-331 |
| [9] | Guan X, Wu H. Leveraging the Power of Multi-core Platforms for Large-Scale Geospatial Data Processing:Exemplified by Generating DEM from Massive LiDAR Point Clouds[J]. Computers & Geosciences, 2010, 36(10):1276-1282 |
| [10] | Sharma G, Agarwala A, Bhattacharya B. A Fast Parallel Gauss Jordan Algorithm for Matrix Inversion Using CUDA[J]. Computers & Structures, 2013, 128:31-37 |
| [11] | Cheng T, Li D, Wang Q. On Parallelizing Universal Kriging Interpolation Based on OpenMP[C]. International Symposium on Distributed Computing and Applications to Business Engineering and Science (DCABES), Hong Kong, China, 2010 |
| [12] | Li B, Liu G F, Liu H. A Method of Using GPU to Accelerate Seismic Pre-Stack Time Migration[J]. Chinese Journal of Geophysics, 2009, 52(1):242-249 |
| [13] | De Ravé E G, Jiménez-Hornero F J, Ariza-Villaverde A B, et al. Using General-Purpose Computing on Graphics Processing Units (GPGPU) to Accelerate the Ordinary Kriging Algorithm[J]. Computers & Geosciences, 2014, 64(2014):1-6 |
| [14] | Lu Fengshun, Song Junqiang, Yin Fukang, et al. Survey of CPU/GPU Synergetic Parallel Computing[J]. Computer Science, 2011, 38(3):5-9(卢风顺, 宋君强, 银福康, 等. CPU/GPU协同并行计算研究综述[J]. 计算机科学, 2011, 38(3):5-9) |
| [15] | Reinders J. Intel Threading Building Blocks:Outfitting C for Multi-core Processor Parallelism[M]. Sebastopol:O' Reilly Media Inc., 2007 |
| [16] | Terzopoulos D. Regularization of Inverse Visual Problems Involving Discontinuities[J]. Pattern Analysis and Machine Intelligence, 1986, PAMI-8(4):413-424 |
| [17] | Beutel A, M？lhave T, Agarwal P K. Natural Neighbor Interpolation Based Grid DEM Construction Using a GPU[C]. The 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems, San Jose, USA, 2010 |
