面向多核处理器的并行矢量空间分析运算优化技术研究与实现

发布时间：2018-01-31 15:42

本文关键词： 拓扑造区空间索引缓冲区分析　出处：《中国地质大学》2013年硕士论文　论文类型：学位论文

【摘要】：随着GPS等技术的发展,数据量呈现幂指数的增长,大规模的计算应用推动了并行计算机的发展。但是目前并行计算机仍然主要是在实验室中,只有很少的应用在实际的工程当中,尤其是在GIS中,并行计算机更是没有凸显出它的多核处理器的并行计算优势,因此,充分利用多核处理器计算机的计算能力,加速GIS软件的执行速度,成为并行GIS中亟须解决的一个关键问题。未来,GIS的并行化将是GIS发展的趋势,在并行G1S中,提高并行计算机的实际应用效率,缩小计算机实际的应用性能与机器峰值性能之间的差距,本文以多核处理器为目标平台,研究基于数据并行的程序的关键技术,主要研究工作为基于数据并行的理论基础,对空间分析中最常用的空间索引,拓扑造区以及缓冲区分析进行研究,实现其并行化,以提高并行应用程序的实际性能。本文针对数据并行模型和空间分析技术研究,可以充分发挥并行计算机的优势,有效的提高空间分析的性能,具有重要的学术和应用价值。具体来说,本文的主要研究内容概括如下： (1)研究空间索引的并行化。本文研究空间分析中最常用的空间索引R树索引,并对其进行并行化,在多核系统上,实现基于OpenMP的R树并行。 R树是一个类似于B树的平衡树,其最常用的构建方法是逐结点插入法。本文提出了对于R树进行批量插入算法,并且对其进行并行化,以充分利用现在计算机硬件相比原来单核计算机的优势。从而提高算法的运行效率。对于查询和删除操作,同样适用并行操作。本文对R树索引测试重点是在多核处理器的环境下并行R树与串行R树的构建和插入进行性能比较,采用的mapgis格式的数据,得出在数据量较小时,插入和批量构建算法都十分迅速,但是在数据量比较大时,批量建立已经显示出优势,在实验的数据中,批量插入算法和传统的插入算法效率已经相差到10倍,在并行插入和串行插入时,同样是随着数据量的增大,并行插入的优势已经越来越明显,在实验数据中差距离9倍。在多核处理器环境下,并行R树的建立对于数据量较大时具有比串行R树的建立具有更大的优势,能够提高空间分析的性能。 (2)研究拓扑造区的并行化。本文研究空间分析中线拓扑造区的常用算法,然后根据计算机图形学中翼边结构的特点,提出基于数据并行化的拓扑造区算法,并对其进行实验,进行串行拓扑造区和并行拓扑造区进行分析。矢量数据拓扑造区是空间分析中一个非常基础且重要的操作,即矢量数据拓扑造区是对一平面内的一个或者多个线对象所组成的集合进行处理,形成闭合的多边形的过程。在实际应用中,往往会对一个线文件或者对一个线文件中的部分线来进行拓扑造区。本文该部分首先介绍拓扑造区的准备工作,然后再研究矢量线数据拓扑造区的串行化以及在多核处理器环境下的并行化,来提高拓扑造区的加I速比。本文对利用PMR四叉树对并行线拓扑造区进行研究,根据多核处理器的环境特性,实现拓扑造区的并行化算法,提高多核处理器共享存储系统的性能。实验表明在多核环境下,在数据量较小时并行并没有显示出优势,但是在数据量比较大时,并行算法的优势会变得越来越明显；线程数设置也不是越多越好,选择过于高于核数的线程数,由于各个线程之间的通信,往往会降低效率,因此线程数设置为核数的2倍左右最为适宜。 (3)研究缓冲区分析的并行化。本文研究空间分析中矢量折线进行不等半径的缓冲区分析,并提出基于数据并行化的不等半径的缓冲区分析,然后对其进行实验,进行矢量线数据不等半径缓冲区分析的并行算法和串行算法的对比分析。研究矢量数据不等半径buffer分析的串行化,并研究其在多核处理器环境下的并行化,来提高不等半径buffer分析的速度。采用基于平面图模型的来串行线矢量要素的不等半径buffer分析,并利用visual Studio环境下的C++实现,接着根据多核处理器的环境特性,实现不等半径buffer分析的并行化算法,提高多核处理器共享存储系统的性能。最后通过实验来验证矢量buffer分析和光栅法buffer分析的精确性,检验并行矢量数据不等半径buffer的性能,比较串行和并行两个版本的计算速度。这与数据量和划分区域的情况有关系,如果数据量很小,对其进行分割和线程之间的消息传输所占用的时间增加,如果大部分区域需要重复计算,那么其计算时间不但不会减少,而且占用了更多的空间。而相反,如果数据量比较大,且分割时划分比较适当,重复计算的要素不是很多,那么效率就会相对较高。
[Abstract]:......
【学位授予单位】：中国地质大学
【学位级别】：硕士
【学位授予年份】：2013
【分类号】：TP338.6;P208

【参考文献】