面向多核架构的GIS 并行算法实验模拟环境的开发与实践教学

陈占龙+冯齐奇+吴亮+赵雷

摘 要 以VLSI为代表的现代半导体工艺技术单方面的进步已经很难满足微处理器性能发展的需求，以“横向扩展”为特征的多核处理器成为了主流发展方向。多核时代到来的结果是软件开发者必须找出新的开发软件的方法，以多核架构为基础的并行处理技术的快速发展对空间信息数据的并行存取与处理具有重要的借鉴意义。“培养掌握3S工程理论和技术的信息软件技术开发人才”为地理信息系统和信息工程专业人才培养的目标之一，其目的在于使学生在校期间能接触全球最前沿的技术，接受最新科研方法的训练。

关键词 GIS 空间运算 并行模拟 教学实践

中图分类号：G424 文献标识码：A DOI：10.16400/j.cnki.kjdkz.2015.12.060

Abstract In VLSI as the representative of modern semiconductor technology advances unilateral microprocessor performance has been difficult to meet the needs of development in order to "scale" is characterized by multi-core processors become the mainstream of development. The results of multi-core era is the software developers must find new methods to develop software， rapid development of multi-core architecture based on parallel processing technology has important reference for parallel access to data and processing spatial information. One of the goals for the GIS and Information Engineering Personnel Training "training to master 3S engineering theory and technology information software technology development talent"， which aims to enable students at the school have access the world's most cutting-edge technology， accepted the latest research methods training.

Key words GIS spatial operators； parallel simulation； teaching practice

0序言

多核并行空间计算是一门动手能力和理论要求都很强的课程，国内外对于多核并行GIS的运行环境展开了广泛研究。英联邦科学与工业研究组织（CSIRO）的Abel和新加坡国立大学的Ooi等人首先研究了分布式空间数据库的空间连接查询处理问题，提出了一种空间半连接查询处理算法，构建了分布式GIS的运行环境。新加坡国立大学的Tan等人又将上述算法扩展到多维索引结构。韩国Yonsei大学的Kang等人基于“子图划分，任务分治”的思想在并行计算环境下优化了海量空间数据的传输。泰国电子计算技术中心的Apirak Panatkool等人对网格上分布式的GIS服务进行了研究，提出基于计算网格模型的分布式模式。马里兰大学的Tanin等人基于SAND平台研究了在集中式中介模型和对等式中介模型下的GIS系统，能够利用闲散的结点资源响应更多的用户查询请求。德国不来梅大学计算技术研究中心的V gele等人讨论了对等网络环境下使用元数据对空间信息进行获取的模拟环境。奥地利萨尔兹堡研究机构的Alenka Krek等人则提出了对等协同计算GIS的概念，并给出了三种对等协同计算GIS的分类。在国内相关学者进行了研究，2006年北京大学方裕教授等人则顾及空间数据的特殊性，建立了并行协同GIS平台运行环境。中科院地理科学与资源研究所资源与环境信息系统国家重点实验室的沈占锋、骆剑承等实现了当前在GIS领域的并行中间件运行环境。

这些研究为面向多核架构的GIS并行实验模拟环境的开发提供了理论基础和实践参照，但目前国内外商用的GIS软件由于系统结构复杂，安装繁琐，价格昂贵，最重要是现有的GIS软件平台缺乏对多核架构的有力支撑，在这些运行环境中很难体现多核并行GIS空间信息理论，使得教学理论内容与实验教学很难有机结合，学生在做实验时难以理解。因此，研制面向多核架构的GIS并行实验模拟运行环境，提高学生对并行GIS的理解，加强学生实验时的动手能力，节约教学软件资金，具有重要意义。

1并行模拟环境目标

在地理信息系统和信息工程专业本科生中进行多核架构及编程技术的课程建设，使得学生在硬件、软件方面能够更好地了解多核思想及编程技术，更好地适应高新技术飞速发展的需要。当今世界各国存在一个普遍现象，即大学里培养的科技人才不能适应科技创新型社会的需要，而且，两者之间的差距日益扩大，形成“毕业鸿沟”。其根本原因在于学生在校期间无法接触到全球最前沿的技术，接受不到最新科研方法的训练。要改变这个现状，其中关键途径之一就是让年轻人通过感受最新技术成果而树立创新意识，通过参与最新技术的应用研发而提高创新能力。“面向多核架构的GIS 并行实验模拟环境”的建设是历史的必然；另一方面，高校的社会责任之一就是为社会输送更多的复合型人才与专业技术人才，由于学生就业有“滞后性”的特点，而教学设计必须具有“前瞻性”，是故“多核并行空间计算”相关课程的开展也是现实的必然。“面向多核架构的GIS 并行实验模拟环境”的研制，作为地理信息系统和信息工程专业的“地理信息系统”、“并行计算”、“高性能计算”等课程的实验平台运行环境，让学生在校期间接触最前沿的高性能计算技术，接受新的科研方法的训练，使学生通过感受最新技术成果而树立创新意识，通过参与最新技术的应用研发而提高创新能力。

2 GIS并行算法库模块

该模拟环境系统分为多任务并行系统、空间运算处理系统、并行空间运算处理系统共三个子系统，其中并行空间运算处理系统由多任务并行系统和空间运算处理系统共同完成，我们将以三个动态库的形式提供用户，各系统的职责：（1）多任务并行系统：根据用户传入的任务进行任务分解和调度，使任务能得以高效并行的执行；（2）空间运算处理系统：采用OGC抽象规范提供的开源GEOS库，包含了全部空间运算方法实现；（3）并行空间运算处理系统：将多任务并行系统与空间运算处理系统结合，并行系统传入的任务是空间运算，将多个空间运算任务并行去处理。

本系统采用过程驱动控制和多线程并发控制。首先用户传入需要处理的空间数据，选择空间运算操作，程序将这些空间运算操作和空间数据操作传入多任务并行系统，根据依赖关系分配原则，系统分配线程以及每个线程中的任务。然后并行执行线程中的任务，即执行空间运算处理系统。最后输出结果。

3并行实验模拟环境

3.1 实验数据

数据采用MapGIS K9地图编辑器创建的简单要素模型，数据量从10000到100000共十组数据。首先创建一个简单要素，然后通过阵列复制获得大量的简单要素。如图1为10000个简单要素区的数据。

3.2 实验指标

并行程序的性能可以通过下面3个指标来评价。

（1）时间指标。并行程序的直接目的就是要使程序花费的时间性能得到提升。在理论情况下，并行程序的总时间满足下面公式：

并行程序总时间 = 。

但是实际运用中是做不到的，实际的并行程序总时间一般符合下列不等式：

并行程序总时间≥。

（2）加速比指标。为了更好地描述并行程序计算的性能，通常采用加速比指标来进行度量。加速比公式为：

=

加速比通常都小于CPU核心数，只有极少数并行算法如并行顺序搜索可以获得超线性加速比。因此，并行性能较好的程序加速比一般要求向CPU核心数靠近；而且加速比越大，程序性能越好。

加速比是多核并行编程中需要考虑的非常重要的性能指标，影响加速比的主要因素包括：串行计算、CPU饥饿问题和线程间的负载平衡问题等

（3）粒度指标。选择适合应用的粒度是实现出色并行性能的关键之一。粒度是指并行任务的实际工作量。如果选择的粒度太细，则程序的并行性能会因为线程切换、通信开销等因素增加而受到很大影响；如果选择的粒度太粗，则程序的并行性能会因为负载不均衡等因素而受到影响。为了能够实现最佳的并行性能，编程者应选择合适的并行任务粒度（通常粒度越大越好），尽量减小线程切换、通信开销和负载不均衡等因素的影响。

3.3 实验结果与分析

目前，编程者选择合适的并行任务粒度的方法是从逻辑上将需要执行的任务分解成尽量多的并行任务，或者在并行任务内根据执行顺序和共享数据决定必要的通信。由于分解任务、任务分配和线程切换等会产生一些额外的开销，编程者分解任务后还需要整合分解的任务，以减小额外的开销，提高程序性能，这样才能得到最佳的并行任务粒度。在本次实验中，将从上面3个指标来分析实验结果，以更好地理解并行程序的性能提升。

在本次实验中，分别在串行、2线程、4线程和8线程下测试了10000到100000十组数据，并将结果通过图表的形式表现出来。由于空间运算操作较多，这里选取其中几个做详细介绍。

选取半径20，弧段数12，冒端模式2对数据做缓冲区buffer分析，如图2是10000的数据通过缓冲区Buffer分析后得到的新的简单要素区，实验结果证明并行程序的正确性。

经过多次实验后，得出了从10000到100000十组数据经过并行缓冲区分析后所用的时间和加速比图表，如图2所示。

4 总结

通过本次实验，可以总结如下结论：（1）基于OpenMP并行化解决方案的多任务调度算法能够较好地解决GIS中空间运算并行运行。2线程的加速比能达到1.5以上，4线程和8线程的加速比能达到2.0以上。（2）影响程序并行性能的因素包括：并行任务粒度，任务分解与调度策略、负载均衡、硬件配置、软件算法等。（3）程序并行的线程数选择并不是越多越好。选择合适的线程数需要考虑的主要因素包括：硬件配置和并行任务粒度，尽量选择不超过硬件能同时运行的线程数且并行任务粒度大小合适的线程数作为程序并行的线程数。（4）在合适的线程数选择范围内，并行性能会随着线程数的增加而增加。

本文论述了基于OpenMP并行化解决方案的空间运算的多任务调度算法的设计与实现，结合GEOS库提供的空间运算算法进行了多次实验，并取得了不错的并行加速效果，本文采用的是OpenMP并行化解决方案，下一步将融合其他优秀的并行化解决方案，如：TBB并行化解决方案等，进一步提高并行空间分析算法的效率。

基金项目：中国地质大学（ 武汉） 校级B 类教学研究项目：基于项目的“双创型”人才培养模式探索——以信息工程专业为例；中国地质大学（ 武汉） 实验技术研究项目研究项目：面向多核架构的GIS并行实验模拟环境开发

参考文献

[1] 俞艳，袁艳斌，黄解军.GIS拔尖创新人才培养课程体系设计[J].地理空间信息，2015.4（13）：2.

[2] 杨志恒.GIS空间分析研究进展综述[J].安徽农业科学，2012.40（8）：2.

[3] 魏巍巍.空间分析的概念与前沿应用[J].产业与科技论坛，2015.14（12）：3.