论文部分内容阅读
【摘要】栅格数据矢量化算法在GIS领域具有重要的作用，为了提高栅格数据矢量化算法的转换效率，本文基于OpenMP并行计算平台设计了一种针对大型栅格数据的快速转换多个图像的并行算法，使用开源地理空间数据抽象库GDAL作为数据读写和转换的工具，针对影响并行算法性能的因素：线程数、任务调度策略，对传统按行划分的矢量化算法进行并行优化。
【关键词】栅格数据矢量化;并行算法;调度策略;OpenMP
1. 引言
矢量结构和栅格结构是地理信息系统（GIS）中两种主要的空间数据结构，矢栅数据间的转换是GIS应用中必不可少的，其中尤以栅格数据的矢量化过程应用更为频繁。随着人类获取遥感数据的技术不断提高，获取栅格数据的数目和也急剧增加，数据转换需要的规模也成倍增长，传统的栅格数据矢量化算法在效率上无法满足现实的需求。因此，大型栅格数据的快速矢量化算法研究便有了重要的现实意义。近年来，并行计算技术迅速发展，出现了大量利用并行方法解决和遥感领域图像处理等题的新方法，其强大的计算资源为解决中大型栅格数据的矢量化问题提供了动力。
2. 研究方法
2.1 矢量化串行算法
所谓栅格数据的矢量化是对栅格数据的象元或象元集合所构成的图斑的边缘进行勾绘，并以矢量坐标点构成折线段（GIS中称为弧段）的方式给予记录，再经拓扑数据结构处理，生成面状矢量数据结构。典型的栅格矢量化算法主要包括有向边界法、散列线段聚合法等。经过近十几年的研究，逐渐形成三种较为典型的矢量化算法：基于边缘跟踪的矢量化方法、基于窗口匹配的矢量化方法和基于拓扑关系的矢量化方法。
本文以基于邊缘跟踪的矢量化方法作为研究对象，使用GDAL库中封装的栅格数据矢量化算法进行设计，实现算法并行化。基于边缘跟踪的矢量化方法通过读取栅格图像，以一个像元为起始像元，在该像元的八邻域中，按逆时针方向找出与该像元的属性值相同的第一个像元。按此方法继续，直到返回起始点为止。
2.2 矢量化并行算法设计
并行计算（Parallel Computing）通过计算机同时处理多个计算过程来提高计算速度和处理能力。并行计算根据不同的条件有不同的分类，根据程序和算法设计人员角度来看，并行计算可分为任务并行和数据并行两种。任务并行是将一个流水线上的任务分配给各个线程，每个线程只负责一个或固定的某些任务，而数据并行是对不同的数据采用相同的处理方法处理的过程。因此，在并行计算的过程中，主要工作就是数据划分和任务划分。
OpenMP（Open Multi-Processing）是一种共享式存储或共享分布式存储的并行编程模型，主要用于多核的计算机系统，即多个核共享一个内存，将任务划分给多个核进行并行处理，从而提高算法的计算效率和CPU利用率。为了提高大型遥感数据在栅格数据矢量化的过程中的效率，本文以OpenMP并行编程模型为基础，从任务并行和数据并行两个方面对算法进行设计。算法对栅格数据进行任务划分和数据划分，根据本地栅格数据的数量，按照线程数进行任务划分，实现多个图像的并行矢量化;在单个图像的矢量化过程中，对栅格图像的栅格单元进行数据划分，实现单个图像的并行矢量化。
2.3 OpenMP并行实现
在程序中，for循环是比较耗时的，因此利用OpenMP并行的关键是for循环的并行。OpenMP提供了parallel for指令来对循环结构进行并行处理，parallel for指令有两种使用形式：
其中type有static，dynamic，guided和auto四种，chunk是表示一个并行块的大小。static表示静态调度，在整个并行计算过程中并行块的大小都一样。dynamic则表示动态调度，默认其并行块尺寸为1。guided表示启发式调度，指定第一个并行块的大小，后面每个并行块的尺寸都会递减，直到最小的并行块尺寸。采用auto或runtime时，不需要设置chunk参数，此时队列类型将由环境变量omp_schedule来控制。
3. 实验与结果分析
3.1 数据准备及实验环境
本次实验数据采用Landsat-8卫星下载遥感影像，选取江苏丰县和山东曲阜的两个区域前八个波段共16个TIFF栅格影像为源栅格影像，临时矢量数据文件为ESRI Shapefile格式，采用8核16线程的计算机作为实验平台。
3.2 并行实验结果分析
为了更好的了解算法在多核共享存储的计算机上的可扩展性，本次实验分别对静态调度（static）、动态调度（dynamic）、启发式调度（guided）三种调度策略进行测试。按照不同的线程数分为8组测试，记录在三种动态策略下共计3×8组实验耗费的具体时间，并计算对应的加速比（如图）。其中当线程数为1时，采用的是串行算法，由主线程单独完成。
不同线程下不同调度策略对计算效率影响对比
加速比是衡量并行算法时间性能的重要指标，它是指任务由单核执行完成所耗费的时间与并行化所耗费时间的比值。加速比可以反映并行计算带来的效益。由图2可以看出，三种调度策略加速比的整体趋势是相同的，都是先升高后降低，这是因为随着线程数的增加，计算机CPU的利用率也不断增大，并行计算产生的开销包括通信开销和负载开销等也会不断增大，因此会导致运行时间不减反增的情况。虽然三种调度策略的整体趋势不同，但通过比较可以看出，采用静态调度的加速比波折较大，不够稳定，说明采用这种任务调度方式的负载均衡性能较差，而采用动态调度的并行算法相对稳定且加速比大，说明动态调度策略最适合于栅格数据矢量化的并行计算。
4. 结语
本文以OpenMP为并行编程模型，发掘栅格矢量化函数的并行潜力，完成了矢量化函数的并行化以及多个栅格图像的并行算法，对提高大型遥感数据在栅格数据矢量化的过程中的效率有一定的帮助。通过对三种调度策略的测试，选取了加速比最高，且随着线程数增加，运行时间相对稳定的动态调度策略。考虑到通信开销、负载开销、进程启动和结束时间对并行算法性能的影响，为了获取最大的效益，计算机线程数要控制在一定范围内，不宜过少或过多。
参考文献：
[1]魏金标.自适应栅格数据矢量化并行方法研究[D].南京大学，2014.
[2]章孝灿，潘云鹤.GIS中基于“栅格技术”的栅格数据矢量化技术[J].计算机辅助设计与图形学学报，2001，13（10）：895-900.
[3]Tzen T H， Ni L M. Trapezoid self-scheduling： A practical scheduling scheme for parallel compilers[J]. IEEE Transactions on Parallel and Distributed Systems，1993， 4（1）： 87-98.
[4]Hummel S F， Schonberg E， Flynn L E. Factoring： A method for scheme scheduling parallel loops[J]. Communications of the ACM， 1992， 35（8）： 90-101.
[5]王亭亭.基于OpenMP和MPI的并行算法研究[D].吉林大学，2011.
[6]范会敏，李滋田.基于OpenMP的多线程负载均衡调度策略[J].计算机与现代化，2013，（12）：192-195+200.
作者简介：秦柳，山东临沂人，硕士研究生，主要研究方向为3D时空分析与可视化技术。
【关键词】栅格数据矢量化;并行算法;调度策略;OpenMP
1. 引言
矢量结构和栅格结构是地理信息系统（GIS）中两种主要的空间数据结构，矢栅数据间的转换是GIS应用中必不可少的，其中尤以栅格数据的矢量化过程应用更为频繁。随着人类获取遥感数据的技术不断提高，获取栅格数据的数目和也急剧增加，数据转换需要的规模也成倍增长，传统的栅格数据矢量化算法在效率上无法满足现实的需求。因此，大型栅格数据的快速矢量化算法研究便有了重要的现实意义。近年来，并行计算技术迅速发展，出现了大量利用并行方法解决和遥感领域图像处理等题的新方法，其强大的计算资源为解决中大型栅格数据的矢量化问题提供了动力。
2. 研究方法
2.1 矢量化串行算法
所谓栅格数据的矢量化是对栅格数据的象元或象元集合所构成的图斑的边缘进行勾绘，并以矢量坐标点构成折线段（GIS中称为弧段）的方式给予记录，再经拓扑数据结构处理，生成面状矢量数据结构。典型的栅格矢量化算法主要包括有向边界法、散列线段聚合法等。经过近十几年的研究，逐渐形成三种较为典型的矢量化算法：基于边缘跟踪的矢量化方法、基于窗口匹配的矢量化方法和基于拓扑关系的矢量化方法。
本文以基于邊缘跟踪的矢量化方法作为研究对象，使用GDAL库中封装的栅格数据矢量化算法进行设计，实现算法并行化。基于边缘跟踪的矢量化方法通过读取栅格图像，以一个像元为起始像元，在该像元的八邻域中，按逆时针方向找出与该像元的属性值相同的第一个像元。按此方法继续，直到返回起始点为止。
2.2 矢量化并行算法设计
并行计算（Parallel Computing）通过计算机同时处理多个计算过程来提高计算速度和处理能力。并行计算根据不同的条件有不同的分类，根据程序和算法设计人员角度来看，并行计算可分为任务并行和数据并行两种。任务并行是将一个流水线上的任务分配给各个线程，每个线程只负责一个或固定的某些任务，而数据并行是对不同的数据采用相同的处理方法处理的过程。因此，在并行计算的过程中，主要工作就是数据划分和任务划分。
OpenMP（Open Multi-Processing）是一种共享式存储或共享分布式存储的并行编程模型，主要用于多核的计算机系统，即多个核共享一个内存，将任务划分给多个核进行并行处理，从而提高算法的计算效率和CPU利用率。为了提高大型遥感数据在栅格数据矢量化的过程中的效率，本文以OpenMP并行编程模型为基础，从任务并行和数据并行两个方面对算法进行设计。算法对栅格数据进行任务划分和数据划分，根据本地栅格数据的数量，按照线程数进行任务划分，实现多个图像的并行矢量化;在单个图像的矢量化过程中，对栅格图像的栅格单元进行数据划分，实现单个图像的并行矢量化。
2.3 OpenMP并行实现
在程序中，for循环是比较耗时的，因此利用OpenMP并行的关键是for循环的并行。OpenMP提供了parallel for指令来对循环结构进行并行处理，parallel for指令有两种使用形式：
其中type有static，dynamic，guided和auto四种，chunk是表示一个并行块的大小。static表示静态调度，在整个并行计算过程中并行块的大小都一样。dynamic则表示动态调度，默认其并行块尺寸为1。guided表示启发式调度，指定第一个并行块的大小，后面每个并行块的尺寸都会递减，直到最小的并行块尺寸。采用auto或runtime时，不需要设置chunk参数，此时队列类型将由环境变量omp_schedule来控制。
3. 实验与结果分析
3.1 数据准备及实验环境
本次实验数据采用Landsat-8卫星下载遥感影像，选取江苏丰县和山东曲阜的两个区域前八个波段共16个TIFF栅格影像为源栅格影像，临时矢量数据文件为ESRI Shapefile格式，采用8核16线程的计算机作为实验平台。
3.2 并行实验结果分析
为了更好的了解算法在多核共享存储的计算机上的可扩展性，本次实验分别对静态调度（static）、动态调度（dynamic）、启发式调度（guided）三种调度策略进行测试。按照不同的线程数分为8组测试，记录在三种动态策略下共计3×8组实验耗费的具体时间，并计算对应的加速比（如图）。其中当线程数为1时，采用的是串行算法，由主线程单独完成。
不同线程下不同调度策略对计算效率影响对比
加速比是衡量并行算法时间性能的重要指标，它是指任务由单核执行完成所耗费的时间与并行化所耗费时间的比值。加速比可以反映并行计算带来的效益。由图2可以看出，三种调度策略加速比的整体趋势是相同的，都是先升高后降低，这是因为随着线程数的增加，计算机CPU的利用率也不断增大，并行计算产生的开销包括通信开销和负载开销等也会不断增大，因此会导致运行时间不减反增的情况。虽然三种调度策略的整体趋势不同，但通过比较可以看出，采用静态调度的加速比波折较大，不够稳定，说明采用这种任务调度方式的负载均衡性能较差，而采用动态调度的并行算法相对稳定且加速比大，说明动态调度策略最适合于栅格数据矢量化的并行计算。
4. 结语
本文以OpenMP为并行编程模型，发掘栅格矢量化函数的并行潜力，完成了矢量化函数的并行化以及多个栅格图像的并行算法，对提高大型遥感数据在栅格数据矢量化的过程中的效率有一定的帮助。通过对三种调度策略的测试，选取了加速比最高，且随着线程数增加，运行时间相对稳定的动态调度策略。考虑到通信开销、负载开销、进程启动和结束时间对并行算法性能的影响，为了获取最大的效益，计算机线程数要控制在一定范围内，不宜过少或过多。
参考文献：
[1]魏金标.自适应栅格数据矢量化并行方法研究[D].南京大学，2014.
[2]章孝灿，潘云鹤.GIS中基于“栅格技术”的栅格数据矢量化技术[J].计算机辅助设计与图形学学报，2001，13（10）：895-900.
[3]Tzen T H， Ni L M. Trapezoid self-scheduling： A practical scheduling scheme for parallel compilers[J]. IEEE Transactions on Parallel and Distributed Systems，1993， 4（1）： 87-98.
[4]Hummel S F， Schonberg E， Flynn L E. Factoring： A method for scheme scheduling parallel loops[J]. Communications of the ACM， 1992， 35（8）： 90-101.
[5]王亭亭.基于OpenMP和MPI的并行算法研究[D].吉林大学，2011.
[6]范会敏，李滋田.基于OpenMP的多线程负载均衡调度策略[J].计算机与现代化，2013，（12）：192-195+200.
作者简介：秦柳，山东临沂人，硕士研究生，主要研究方向为3D时空分析与可视化技术。