基于OpenMP的两个地学基础空间分析算法的并行实现及优化  

Parallel Implementation and Optimization of Two Basic Geo-Spatial-Analysis Algorithms Based on OpenMP

作　　者：朱效民[1,2,3] 潘景山[1,2,3] 孙占全 顾卫东[1,2,3] 

机构地区：[1]山东省计算中心,济南250014 [2]国家超算济南中心,济南250101 [3]山东省计算机网络重点实验室,济南250014

出　　处：《计算机科学》2013年第2期8-11,39,共5页Computer Science

基　　金：国家自然科学基金青年科学基金项目(61004115);山东省科学院科技发展基金项目(科基合字2011第12号)资助

摘　　要：研究了两个基础空间分析算法(大量线段求交、点面叠加)的实现方法,并基于单机多核环境,利用OpenMP实现了并行算法。通过分析并行算法,得到了无法取得线性加速比的原因,即负载不均衡,内存管理采用全局方法,仍然是"串行"的。基于此,通过对数据进行有效的排序并利用OpenMP的动态调度方式进行调度;改进了现有的并发内存分配技术,并将其用于并行算法的内存管理。利用以上方法对并行算法进行了优化,测试表明,优化后的算法具有较为理想的近线性加速比,单机四核环境下,每个核心的计算效率不低于80%。This paper introduced research on the methods for two basic geo^spatial-analysis algorithms：getting intersec- tion points for large amounts of segments and point-polygon-overlay, and we implemented the two algorithms on the shared memory multi-core environment based on OpenMP. We analyzed the reason why we don＇ t get linear speedup, and got that it is because of unbalanced load and serial memory management method. Then we sorted the input data and adopted the dynamic scheduling of OpenMP. Also, we adopted and improved the current parallel memory allocating technique to manage the memory for parallel algorithms. Based on the two methods above, we improved the algorithms. The tests show that the improved method can reach nearly linear speedup, and the efficiency of each core in a fou^core node is above 80 %.

关 键 词：空间分析 求交 点面叠加 并发内存分配 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]