并行算法设计与实现任务指导书.docx

空间信息处理并行算法设计与实现任务指导书1. 课题目的通过对HPC、Linux、并行计算基础、MPI变成模型的理论讲授，以及对应的上机实践，同学们已经为如何利用HPC技术，尤其是MPI并行编程方法实现空间信息领域的典型空间信息处理算法并行化奠定了一定的基础。这部分课题设计就是检验同学们对前面知识的整体掌握程度而设计的。2. 课题介绍本次课题设计算法是基于格网的栅格数据（DEM栅格影像数据）生成等高线（矢量数据结构，Shapefile格式）算法的并行化实现。该算法涉及地理空间信息系统常见的两种数据格式：栅格数据、矢量数据结构，属于数据格式转化算法中的一类（栅格数据转换成矢量数据）。因为等高线生成算法是一个比较典型的栅格-矢量数据转化算法，是GIS的常见空间分析算法之一，具有较为广泛的应用领域。随着获取栅格数据，尤其是DEM数据能力的提高，该算法需要处理的数据越来越大；另一方面，该算法本身处理极为耗时，是一个典型的集数据密集、计算密集型的空间信息处理算法。因此，选择该算法作为研究空间信息处理算法在不同HPC计算手段下的研究对象是适合的；通过该并行算法设计，对探索其他地学计算的算法并行化研究具有较为重要的作用。3. 课题任务设计并实现基于高性能集群平台的MPI版本的等高线生成并行算法，以及并行算法的测试、性能分析报告。最后提交实验报告（参见附件中的“电子科技大学标准实验报告模板”文件进行）。4. 课题要求（1） 提交的标准实验报告（纸质版和电子版）。提交报告的内容部分需包含串行算法原理、热点分析、并行算法设计、并行算法编码实现、并行算法测试、并行算法优化改进（可选）、系统测试等部分。（2） 提交对应的源代码（电子版）；（3） 必须独立完成，避免抄袭（会用相关代码克隆检测软件进行扫描，务必引起重视）；（4） 同时也请提交平时上机练习的作业代码；（5） 上机时间：2016年6月22日，地点请查看系统；请大家提前准备好相关材料，上机的时候统一提交给我。5. 课题实现在具体实施该课题时，提供对应的基础知识与大体的思路与方法，以及列出在实现过程中需要注意的问题，以供同学们参考使用。5.1 等高线串行算法原理目前，获取等高线的手段多种多样，其中通过地形数据自动生成等高线，如通过纸质地图扫描矢量化生成等高线，DEM栅格数据转换成生成等高线等多种途径和方法。其中利用DEM栅格数据通过算法自动生成等高线（图1）是获取等高线的最主要手段，该途径既是利用DEM进行地形分析的重要部分，也是GIS自动制图的一个重要研究内容。此外，空间数据转换既是GIS数据处理的一项重要任务，也是GIS的技术难题之一。有时候，为了方便分析和应用，需要将矢量数据转换成栅格数据，或者将栅格数据转换为矢量数据，而由栅格数据生成等高线则是数据格式转换中的一类。图1 栅格DEM生成等高线传统DEM数据获取主要通过航空摄影测量、卫星遥感、已有地形图矢量化等手段完成，随着先进空间数据获取技术的进步与发展，尤其是LiDAR (light detection and ranging)技术的革命性发展，使快速、低成本、自动处理获取大面积、高精度的DEM数据成为可能。如何将海量的DEM数据快速转换成等高线数据，成为一个急需解决的问题。显然选择利用HPC手段，将是解决这个问题不二的选择。目前，应用得最为广泛的栅格生成等高线算法采用的是等值线传播算法，隶属于网格法这一类，该算法的时间复杂度为O(N)。等值线传播算的基本原理是：为了得到某一高程值的等高线，首先找到一个有对应等高线穿过的格网作为初始格网；然后由这个初始格网开始向邻近的栅格（上、下、左、右）传播这条等高线；当某一条等高线穿过格网时，可通过线性内插方法求出等高点；同时利用下述公理判断其下一个传播方向：公理1：单元格网的边与等高线交点的个数为0，2或4 ；公理2：已知等高线与单元格网的边有4个交点，则在单元格网内中心点和两个顶点同号的对角线与等高线没有交点。直至所有栅格单元遍历一遍，再利用相同方法进行下一条等高线的获取。一个完整的可实现的栅格数据生成等高线算法的描述如下：（1）标志栅格图像的栅格。设置一个标志，用来说明该栅格是否需要再被搜索，初始值与说明不再对该栅格进行搜索的标志值不同，被标志后直至等高线高程发生变化后，标志才会失效。（2）构成栅格矩形。图2 栅格格网设置将待搜索的栅格与其右，右下，下方各栅格一起组成栅格矩形。如图2所示：（3）判断栅格点间等高线是否穿过。如上图所示，以点0和1为例，设点0高程为Z0，点1高程为Z1，判断它们之间是否有高程值为level的等高线穿过，只需判断level-Z0level-Z10的值。如果满足条件，则说明点0和点1之间有等高线穿过。（4）插入等高线矢量点。对于每条等高线，依次搜索栅格图像的各个栅格，对每一栅格，判断该点是否出界及是否已被标记不再搜索。如果均否，则判断相邻两栅格之间是否有等高线穿过（如图2的点01之间，12之间，23之间及30之间）。若有，则按线性内插公式计算并存入对应数组。 (1)注：公式1中： (x,y)为平面坐标；z为高程值；x 、y 为待插值点的平面坐标。线性插入法使用的条件是平面上点的插入，在我们要处理的栅格图像中，四个角点可看作在一个平面内，因此可用线性插入法。（5）寻找该栅格可继续搜索的方向。通过上述公理可知，寻找当前搜索栅格可继续搜索的方向有两种情况：一种是在该栅格所形成的栅格矩形中，只有2条边上有等高线穿过；另一种是该栅格所形成的栅格矩形中，4条边上均有等高线穿过，分以下两种情况讨论：（5-1）栅格矩形只有两边有等高线穿过的情况。在这种情况下，上一步中我们已经插入了其中一个点（可称之为第一个交点），而该栅格部分的等高线必然是从第一个交点指向第二个交点，因此只需将第二个交点插入即可，将栅格矩形移到以这点所在边为边的新矩形上。这种情况比较简单。（5-2）栅格矩形四边均有等高线穿过的情况。这种情况比较复杂，处理起来比较困难。在这种情况下，我们已经插入了第一个交点，怎样从剩余三个交点中挑选出一个交点作为该栅格部分等高线的后续搜索方向呢？可以先求四个角点的高程平均值，设为mid （如图3），那么在栅格矩形中必然存在一个点，其高程与mid对应，再分别按照（3）中方法判断mid与栅格矩形四个角点之间是否有等高线穿过，即可得到该栅格部分的等高线的后续搜索方向，将栅格矩形移到以这点所在边为边的新矩形上。图3 栅格矩形四边均有等高线穿过的情况（6）搜索完毕进入下一栅格的搜索。过程基本重复(2)(5)步，直至该栅格图像到底或已无栅格可再搜索，此时将进入下一条等高线的搜索。5.2 串行算法实现过程本课题提供的等高线算法是参考GRASS中的r.contour模块实现。其原理基于等值线传播算法，由栅格图像生成等高线算法即是将一幅栅格图像按等高线条数或等高线步长，提取高程相等的点，生成该图像对应的等高线矢量图。算法模块主体与上述等值线传播算法基本原理描述类似，只是在在该算法处理之前，需要获取生成等高线的序列，然后依次循环所有不同高程值依循上述算法原理生成对应的等高线。其算法实现的主要过程如下：（1）生成每一条等高线，需先设立栅格标志数组，初始值为0，当处理过并已记录的栅格点均标志为1，以后不再处理，直至下一条等高线开始；（2）对于每一条等高线，分别从栅格图像的上部（前3行）、下部（最下面3行）、左部（最左边3列）、右部（最右边3列）、中间部（除去上下左右3行部分）的第一个栅格开始搜索，对每一个栅格，判断该栅格点是否出界以及是否已被标记为不再搜索；当需要处理时，则按上下、左右、中间的顺序分别判断相邻两栅格之间是否有等高线穿过；如果有，则按线性插入法插入，并记录可继续搜索的方向；（3）继续其他可搜索的方向。直至该栅格已被标记为不再搜索或出界或搜索的当前栅格的相邻栅格之间无等高线穿过，则该栅格搜索结束。同时需要将插入的矢量点予以记录；（4）进入下一个栅格的搜索，过程重复Step 2、Step 3，直至所有栅格均被搜索；（5）开始下一条等高线的生成。在GRASS GIS中，栅格数据生成等高线算法的对应模块为r.contour，算法整体实现流程如图4所示。图4 GRASS中r.contour模块整体实现算法流程其中，利用获取的高程值数据（z_array）以及经过处理的等高线序列（lev）生成具体的等高线数据（分为开曲线、闭曲线）是整个模块的主要部分，由cont()函数完成。该函数的具体实现流程如图5所示。图5 GRASS中r.contour模块cont函数实现结构图但在具体实现时，需要提供单独的LibGeoTiff库以及 LibShapefile库完成栅格数据的读取以及结果矢量文件的生成。这些库的具体知识可以参考各自说明文件。串行程序运行需要的支持包见附件（dependencies文件夹）。在安装具体包之前，先检查下系统是否已经安装了对应的软件（用proj, tiffinfo, listgeo, gdalinfo尝试，用 which XXX查看具体位置）。如果已经安装，就不需要重复安装了。如果没有，那么需要在自己的家目录下安装。大体的安装顺序是：1) 安装Proj4 4.5.0，此时指定的安装路径为/home/fhuang/lib/;./configure -prefix=/home/fhuang/lib make make install 2) 检查有无安装Tif包以及GeoTiff包，如无则安装；./configure -prefix=/data1/home/fhuang/lib/ -with-proj=/data1/home/fhuang/lib/ make make install3) 安装gdal 1.3.2，路径为/home/fhuang/lib/，此时需要指定需要用到的proj-4.5.0，同时需要指定-with-geotiff=internal；./configure -prefix=/data1/home/fhuang/lib -with-static-proj4=/data1/home/fhuang/lib/ -with-geotiff=internal -with-libtiff=internal makemake install4) 安装SHAPELIB库；修改Makefile文件，设置路径makemake testmake install5) 设置环境变量和路径；打开/home/ fhuang下的环境变量文件.bashrc，vi /.bashrc在.bashrc加上下面语句， LD_LIBRARY_PATH=$LD_LIBRARY_PATH:/data1/home/fhuang/lib/libPATH=$PATH:/data1/home/fhuang/lib/binexport LD_LIBRARY_PATH 保存退出，并运行命令使设置生效 wq bash6) 编译运行等高线生成串行算法源码包，直接运行可以看见运行参数的意义解释。将对应的数据拷贝，然后安装说明进行运行。5.3 如何查看输入输出文件由于输入文件以及输出文件皆为地理空间信息处理领域的专用数据格式，故需要利用专业的GIS软件进行输入、输出文件的查看。可以使用的GIS软件有： 商业软件如ArcGIS 10 Desktop等。该软件占用空间较大，可以安装试用版或者教学版。 开源软件如GRASS GIS, QGIS（在software文件夹里面提供不同版本）等。前者较为复杂，后者使用较为简单，建议采用。注意查看这些空间数据与普通数据的不同之处，有对应的空间参考信息。同时这些软件可以作为并行算法生成结果与串行结果比对的平台，即进行结果文件的求差运算。5.4 如何实现热点分析利用Intel VTUNE进行串行算法的热点分析，是比较专业的方法。其Windows版本使用可以参考资料“9-VTune_Amplifier_XE usage”。在Linux下，使用“amplxe-cl -help”可以查看帮助。目前SRE HPC平台上的安装的VTUNE缺少对应的License文件，无法完全运行。你们可以在各自家目录中安装自己下载对应的试用版（需要注册，而且使用有效期为2-3个月）。同时注意，可以将Linux下运行结果拿到Windows下查看结果。(a) s=50m(b) s=20m图6 改进的栅格DEM生成等高线算法热点分析另外一种方法是利用系统提供的时间函数（clock(), timeb），写入数组或者直接输出。5.5 设计对应的并行算法根据前面的学习以及练习，思考该算法的并行化方法。从算法的角度，还是从数据的角度，还是从任务的角度？何种编程模式？设计出对应的并行方案来。首先要从理论上可行才行。5.6 并行算法实现需要注意的问题（1） 结果是否正确？（2） 有无频繁的发送、接收操作？（3） 有无正确的同步？5.7 并行算法优化方法有无进一步优化的可能。从I/O、并行处理、数据传送形式方面考虑。5.8 并行算法系统测试不同并行算法版本，不同输入数据，不同数据大小，利用加速比、效率等评价指标进行综合分析。尽量以独占方式进行，减少彼此间相互影响。6. 课题进度安排与验收 在6月中旬时，形成具体的、切实可行的并行化方案，并与老师讨论。 在6月中下旬旬时，可就具体实现方面的问题与老师进行沟通和交流。 在6月底正式提交实验报告前，可与老师进一步沟通。 在任务进行中间任何时候，欢