一种多核系统中的扫描线算法并行策略
矢量地图叠加分析是GIS空间分析中的重要组成部分.传统的矢量地图叠加分析算法主要采用扫描线算法求得交点,然后通过交点构建叠加结果.随着计算机硬件的发展以及用户需求的变化,传统的扫描线算法不能发挥多核与集群的并行优势,已经不能满足快速、精确地叠加分析要求.本文提出一种求交算法的并行策略.在新型硬件架构环境下,本文采用消息传递编程模型,利用各个计算节点之间的数据通讯,实现了大规模数据在集群环境下的快速求交运算.实验表明,该方法在多个计算节点的计算中取得了良好的加速比.随着内核数目的不断增加，该算法IO时间稳定，计算时间不断下降，从而程序运行的总时间呈下降趋势。在内核数目较多的情况下，该算法可以在15秒左右完成全部计算任务。但随着内核数目的增加，进程之间的通讯代价以及网络传输代价等，加速比和并行效率呈现下降的趋势。此外，随着进程数目的变化，计算结果的要素个数有少量偏差，主要原因是因为矢量叠加分析为浮点数运算，计算过程中需要动态的计算容差范围，经过结果的比对，误差在允许范围之内。实验结果表明，该算法在服务器集群环境下具有较高的性能。算法的运行效率和正确性都取得了理想的结果。另一方面，真实的地理数据与传统计算机图形学有所不同，地理数据具有数据密集，复杂度高，不同类型的数据分布特征明显等特点。研发可并行的扫描线算法有助于提高空间分析算法的效率，但集群环境下的空间数据管理，进程间数据通讯方式等问题将成为制约并行算法效率的主要瓶颈。进一步优化空间数据格式，提高算法的并行效率作为下一步工作的主要内容。
多核系统 矢量地图叠加 扫描线算法 并行策略
邱强 曹磊 卢亮 方金云
中国科学院计算技术研究所,计算机应用研究中心,北京,100190;中国科学院大学,信息工程学院,北京,100190 中国科学院计算技术研究所,计算机应用研究中心,北京,100190
国内会议
成都
中文
396-402
2013-10-01（万方平台首次上网日期，不代表论文的发表时间）