3维地理信息系统课程报告-HPC三维地质隐式建模-文库

中国地质大学研究生课程论文封面课程名称三维地理信息系统教师姓名研究生姓名研究生学号研究生专业软件工程所在院系信息工程学院类别:A.博士B.硕士C.进修生日期:2015年12月5日评语对课程论文的评语:平时成绩：课程论文成绩：总成绩：评阅人签名：注：1、无评阅人签名成绩无效；2、必须用钢笔或圆珠笔批阅，用铅笔阅卷无效；3、如有平时成绩，必须在上面评分表中标出，并计算入总成绩。高性能计算在三维地质隐式建模中的应用一、应用背景随着地学信息化的发展，数学地质正向“数字地质”发展。三维地质建模软件将是“数字地质”的精髓与核心。三维地质建模是指采用适当的数据结构，在计算机中建立能反映地质构造的形态和各要素之间关系以及地质体物理、化学属性空间分布等地质特征的数学模型。相比传统的平面图、剖面图，三维地质模型有显示直观、空间分析功能强大、对原始数据可以直接检查等特点。受地质条件以及勘查技术的局限性,地质勘查测量不能够获取到完整且规则的地质体数据，因此如何通过勘探测量等方式采集的离散地质数据，来建立接近真实的地质体三维空间可视化模型是目前地学领域中的研究难题。现有的三维地质建模软件对各种地质体进行三维建模的过程一般是按照显式模拟的方法，使用勘探工程数据绘制勘探线剖面，再在三维可视化环境下按剖面人机交互圈定地质界线并生成地质体三维模型。这种方法除了耗时外，主要的缺点是每个地质学家建立的模型都因为各自主观条件而不同，模型不具有复制性。随着三维可视化各种算法的发展与成熟，一些三维隐式建模方法被一些学者提出，即将离散的采样数据通过空间插值来生成完备的样品数据，然后再通过三维曲面构建等算法自动生成三维可视化模型。相对显式模拟的地质体界线推断和交互式圈定，隐式模拟方法可省去烦琐的人工操作过程，生成三维模型高效且直观，便于对矿体进行概略性研究和进行储量的快速估算。在隐式建模的实际应用过程中，由于三维地质建模涉及钻孔数据、剖面数据、三维地震资料等多种数据源，并且地质建模从二维转向三维数据量急剧增大，并涉及较为复杂的计算过程，传统电脑的计算能力已经逐渐满足不了相应计算与存储的要求。近年来，由于GPU以其高内存带宽、多处理内核等优势表现出非常好的计算性能，并且英伟达公司推出的GPU的通用编程架构CUDA（ComputeUnifiedDeviceArchitecture）将复杂的GPU编程进行极大的简化，降低了使用GPU的开发成本。本文主要通过相关资料的查阅对三维地质隐式建模的流程进行介绍，简要的说明了基于CUDA的并行算法加速。在此基础上介绍了几种主流的计算机集群计算技术——MPI、Hadoop、Spark，并对集群计算在三维地质隐式建模中的应用进行分析和对比。二、三维地质隐式建模流程1.隐式势场插值隐式势场插值方法可以从离散分布的数据中建立三维地质模型，可以采用的数据有：地质图与数字地形模型、与地层相关的结构数据、钻孔数据、地质学家的经验插值。由于地质数据有其特殊的特点，在其他领域使用的方法不能简单的直接套用。目前在地学建模和矿产资源储量估算中，以几何方法和空间统计方法在地学领域最为常用。如克立格(Kriging)法、距离反比加权法(inversedistanceweighted)法、杨赤中滤波与推估法(YangChizhongestimationmethod)和径向基人工神经网络(radialbasisfunction,简称RBF)法。其中克里格插值法在地质建模中最为常用的方法之一，但随着数据量的增大，计算时占用的内存和速度会以平方和立方的规模增大，需要借助高性能计算的方式进行加速。克里格插值的基本步骤为：1)求源要素之间的协方差矩阵，源要素和目标要素之间的协方差矩阵；2)构建矩阵方程；3)通过求解方程得到权值矩阵；4)通过权值矩阵求得目标要素的属性值。2.三维地质体等值面追踪通过上一步的隐式势场插值可以将分散的不规则分布的地质数据通过插值转换成规则分布的网格数据，建立三维空间的规则数据长，通过三维的规则体元进行存储和处理。要对插值得到的地质体数据进行可视化分析，需要从规则体元数据中提取等值面，得到地质体的基本形态。移动立方体（MarchingCubes）算法由W.Lorensen等学者于1987年提出，是一种三维数据场等值面提取的经典算法，被用于三维重建方面的相关研究。此算法在三维空间规则数据场的基础上，通过数据场中每两层切片每对应的八个点（上下各取四个点）构成一个立方体体元。如下图，上下层切片的每一个点都对应原来三维空间中的一个规则体元，每八个点可以组成一个立方体体元。分别对每个立方体体元进行处理，依次找出每个体元中所包含的等值面。当体元的八个顶点值都大于或都小于给定值c时，体元的内部不存在等值面。只有在既包含大于c的顶点也包含小于c的顶点的体元内部才存在等值面。通过组合所有体元的等值面即可得到最终的等值面。移动立方体算法过程如下：1）每次读出两张切片，形成一层Layer；2）两张切片上下相对应的四个点构成一个立方体Cube；3）依次从左至右，从前到后，顺序处理每一层中的Cube，抽取出各个Cube的等值面，并从下到上逐步处理(n-1)层。三、CUDA与算法并行1.CUDA（ComputeUnifiedDeviceArchitecture）在高性能计算领域，GPU凭借远高于CPU的计算能力、较低的成本、非常高的内存带宽而广泛的运用于有密集计算的程序中。相比传统的CPU计算，GPU已经在很多的科学计算领域证明了其高效性。NVIDIA公司最新的专用于科学计算的显卡TESLAK80的双精度性能将近3TeraFLOPS，内存总带宽高达480GB/s。CUDA是显卡厂商NVIDIA推出的并行计算平台和编程模型，专为NVIDIA显卡进行计算加速而设计，通过更为简单的模型提高了显卡并行运算的易用性，将GPU从图形计算硬件转变为通用计算硬件。CUDA向开发人员提供了C/C++语言的程序接口来编写高计算密度的函数，在CUDA中称这种函数为kernels。kernels被CPU执行的代码调用，执行在具有大量线程的GPU程序中。线程以块（block）为单位按一维、二维或三维的形式进行组织，同时块以网格（grid）为单位按一维或二维的形式进行组织。要使GPU充分发挥其计算能力，开发人员注意数据的本地性和内存的访问类型，充分利用GPU内存的分层特点。（如下图）每一个线程都有自身的本地内存，成为寄存器（Register），寄存器可以在1个时钟周期之内直接访问。每一个线程块都有单独的块共享内存（SharedMemory），可以被线程块中的所有线程访问并且与线程块有相同的生命周期。全局内存（GlobalMemory）更大并且能够被所有的线程访问，但是从全局内存的延时和带宽考虑不建议过多的使用全局内存。对于经常访问的数据，常量内存（ConstantMemory）和纹理内存（TextureMemory）在效率上更高。此外，设备内存与主机内存通过PCIE（PCIExpress）总线连接，PCIE的带宽对比设备内存相对很小，在与主机内存之间较多的通信可能造成性能瓶颈。CUDA并行计算主要解决以下几个方面的问题：1)大规模矩阵的运算。由于获取地质源数据量的增大，地质数据进行反演计算的过程中会出现上万阶甚至更大的矩阵，这些矩阵的运算在CPU的程序中执行速度远低于GPU中的速度。2)计算代码并行。当地质体生成的三维体元数据对精度的要求较高时会有大量的体元值需要重复的耗时计算，十分适合进行GPU的并行处理。在使用移动立方体法进行等值面追踪时，对每层数据的处理与其它层之间没有相互依赖，可以放在GPU的大量线程中进行处理。2.隐式势场插值并行计算克里格插值可以完全转换成矩阵之间的运算。以下是克里金插值的权值计算矩阵：000FfF其中∑表示协方差矩阵，F表示基函数矩阵，λ表示权重，μ表示拉格朗日参数，σ表示数据点与克里格点的协方差向量，f表示克里格点基函数向量。这样可以将插值的运算转变为计算线性方程组的问题。CUDAToolkit为C/C++程序员开发GPU程序提供了全面的开发环境，包含NVIDIAGPUs编译器，数学库，调试优化工具等。地质建模中的数学计算可以调用其中的数学库进行加速：cuBLAS(BasicLinearAlgebraSubroutines)，是标准的BLAS库的完整实现，可以进行基本线性代数的运算，相比最新的MKL库有6倍至17倍的加速。在使用cuBLAS库时，需要将矩阵先分配到GPU的内存中，调用cuBLAS的函数后再从GPU内存中取出计算结果或进行下一步的计算。矩阵相加的计算在CPU的程序中需要对矩阵的每一项进行相加，对于n*n阶的矩阵，算法复杂度为O(n2)。在GPU的并行执行中，相加的计算在大量线程中同时执行，算法复杂度在理论上可以达到O(1)，但随着数据量的增大，GPU计算线程的数量相比矩阵较小时，算法复杂程度会上升的O(n)。对于矩阵相乘，在CPU的实现中算法复杂度为O(n3)，但在GPU的实现中为O(n2)。对于矩阵求逆，CUDA采用高斯约旦消元法（Gauss–Jordanreductionmethod）将算法复杂度从CPU计算的O(n2log(n))下降到O(n)。3.等值面追踪并行计算对于移动立方体算法，由于每次从总的计算数据中抽取两层组成一片立方体，因此很容易对三维规则数据场组成的立方体按层划分，将每层的数据放入不同的进程块中进行处理，然后将计算结果返回到内存。对于每一个体元的八个顶点都可能有大于阈值与不大于阈值两种情况，因此每个体元的等值面都有28=256种可能。由于立方体有旋转对称性且不影响等值面的拓扑关系，可以将旋转后可以重叠的立方体作为一种，最后只有15种可能（如下图），通常用一个长度为256的查找表来对应这15种可能。按顺序对比八个顶点与阈值之间的关系，在查找表中找到立方体里的等值点与等值点的连接信息，通过将各个立方体中找到的等值点按一定规则进行连接即可得到一个三角化的等值面。由于构成的等值面很可能同时穿过多层立方体，因此相邻两层立方体之间的等值点还存在拓扑关系，需要在等值点提取完后进行进一步的处理，相邻层之间存在数据交换。并行的移动立方体算法流程为：1)从三维规则体元中抽取相邻两层形成n-1层立方体；2)将立方体按层存入GPU的内存进程块中进行处理；3)将提取的等值点再次按相邻层进行分配，建立相邻层等值点的关系；4)从GPU内存中导出三角网等值面结果。当数据量过大导致GPU内存无法一次存储时，需要对待处理数据进行磁盘-内存-GPU显存的多次调度，将中间结果转移到内存、磁盘后再进行进一步的处理。在第2）步中先将一部分数据存入GPU中，计算完后将计算结果转出，再转入下一部分数据进行计算。在所有的第2）步计算完之后一般等值点占的内存不会超过GPU的计算能力，可以直接采用第3）步中的算法进行计算。四、网格计算与云计算分析1.网格计算MPIMPI(MessagePassingInterfaee)是一个消息传递接口的标准，MPI是一个可以被C、C++、FORTRAN等编程语言调用。从语法上说，它遵守所有语言对函数的调用过程，和一般的函数没有区别。MPI具有良好的移植性和可扩展性、完善的异步通信机制、众多厂商的支持并且易于使用。通过MPI可以实现多个主机之间进程的通信，达到网格集群计算的目的。在linux环境下，常用的MPI库为MPICH和OpenMPI，低版本可以在windows上使用。最新的MPI3.1标准在2015年6月发布，不支持容错性，预计两年后发布的MPI4.0支持新的容错性。在windows环境下，推荐使用微软为高性能计算开发的MS-MPI。2015年11月发布当前最新的7.0版本，相比之下MPICH与OpenMPI都在2011年停止了对windows的更新，只能通过安装linux虚拟运行环境使用。微软专为windows开发了一套高性能集群计算的库MicrosoftHPCPack，通过HPCPa