摘要
研究了两个基础空间分析算法(大量线段求交、点面叠加)的实现方法,并基于单机多核环境,利用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 %.
出处
《计算机科学》
CSCD
北大核心
2013年第2期8-11,39,共5页
Computer Science
基金
国家自然科学基金青年科学基金项目(61004115)
山东省科学院科技发展基金项目(科基合字2011第12号)资助
关键词
空间分析
求交
点面叠加
并发内存分配
Spatial analysis, Intersection, Point polygon-overlay, Parallel memory allocate
