（大地测量学与测量工程专业论文）基于pc集群矿山海量空间数据并行处理与可视化.pdf

ad i s s e r t a t i o ni ng e o d e s ya n ds u r v e ye n g i n e e r i n g p cc l u s t e r - b a s e dp a r a u e lp r o c e s s i n ga n d v i s ua l i z a t i o nf o rm a s s i v em i n e s p a t i a ld a t a b yh a n n f e n g s u p e r v i s o r ：p r o f e s s o rw u l i x i n n o r t h e a s t e r nu n i v e r s i 哆 j a n u a r y2 0 0 8 上 一 独创性声明 本人声明，所呈交的学位论文是在导师的指导下完成的。论文中 取得的研究成果除加以标注和致谢的地方外，不包含其他人己经发表 或撰写过的研究成果，也不包括本人为获得其他学位而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示谢意。 学位论文作者签名：弁铝嘭 日 期：沙驴、i 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学 位论文的规定：即学校有权保留并向国家有关部门或机构送交论文的 复印件和磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学 位论文的全部或部分内容编入有关数据库进行检索、交流。 ( 如作者和导师不同意网上交流，请在下方签名；否则视为同意。) 学位论文作者签名： 签字日期： 导师签名： 签字日期： i 东北大学硕士学位论文 摘要 基于p c 集群的矿山海量空间数据并行处理与可视化 摘要 大规模矿山建模的精细程度是评价数字矿山模型的一个重要指标。进行矿山三维精 细建模，以及在此模型数据上进行地质统计与空间分析，如地质储量计算、采矿最优化 分析、虚拟采矿仿真等，都涉及到三维海量空间数据。由于数据量巨大，难以在普通p c 机上进行程序运算。 近几年来p c 集群技术的不断成熟提供了一种廉价而又强大的并行环境。本文将并 行技术引入数字矿山，首先，通过对p c 集群技术的研究在实验室环境下搭建了一个面 向数字矿山的p c 集群环境；然后，基于所搭建的p c 集群环境进行了矿山三维海量空 间数据并行处理研究和矿山三维精细模型并行可视化研究；并在上述研究的基础上，开 发实现三维地质体快速海量v o x e l 化的并行计算系统以及矿山三维海量数据的并行显示 系统。研究表明，p c 集群是一种经济、高效的数字矿山并行处理与可视化环境。 关键词：数字矿山；海量空间数据；p c 集群：并行处理；可视化 j 东北大学硕士学位论文 a b s t r a c t p cc l us t e r b a s e dp a r a u e lp r o c e s s i n ga n d v i s u a l i z a t i o nf o rm a s s i v em i n e s p a t i a ld a t a a b s t r a c t t h el a r g es c a l ee l a b o r a t i o no ft h r e ed i m e n s i o n a lm i n em o d e li st l l ek e yo fd i g i t a l m i n e t h eb u i l d i n go fe l a b o r a t em i n em o d e la n d 如n h e 瑚o r eg e o s t a t i s t i c a la 1 1 d s p a t i a la n a l y s i s ，戳l c h 弱m ea c c u r a t ec a l c u l a t i o no fg e o l o g i c a lr e s e r v e s ，t h e o p t i m i z a t i o no ft h em i n i n g ，t h ev i r t u a ls i m u l a t i o no fm i n i n gp r o c e s sa n d s oo n ，a l la r e r e l a t e dw i t hm a l s s i v et l l r e e d i m e n s i o n a ls p a t i a ld a t a b e c a u s eo ft l l et r e m e n d o u s v o l 啪eo fm i n ed a t a ，i t sh a r dt of i n i s ht h eh u g ej o bo no r d i n a r yp cm a c h i n e t h ed e v e l o p m e n to fp cc l u s t e rp r o v i d e sac h e a pa n dp o w e r f u lp a r a l l e lc a l c u l a t i o n e n v i r o m n e n to fd i g i t a lm i n e t h j sp a p e ri n t r o d u c e d “ss o l u t i o n sa 1 1 dt e s t so np c c l u s t e r - b 弱e de n v i r o n m e n tf o rd i g i t a lm i n e f i r s t l y ，as o l u t i o nt ob u i l dap cc l u s t e r f o rd 睹词m i n ei sp r o v i d e d ；s e c o n d l y ，t l l ep a r a l l e lp r o c e s s i n ga n d3 dv i s u a l i z a t i o n f o rm 弱s i v et h r e e d i m e n s i o n a ls p a t i a ld a t ao fd i g i t a lm i n ea r es t u d i e d t h i r d l y t 、o p a r a l l e lp r o c e s s i n gs y s t e m s ，o n ef o rf h s tm a s s i v ev o x e l i z a t i o no f3 dg e o l o g i c a lb o d 弘 锄dt h eo t l l e rf o r3 dv i s u a l i z a t i o no fm a s s i v e 3ds p a t i a ld a t aa r ed e v e l o p e d 锄dt e s t e d i ts h o w st l l a tt l l ep cc l u s t e ri sae c o n o m i c a ja n de 仃e c t i v ep a r a l l e lp r o c e s s i n ga 1 1 d v i s u a l i z i n ge n v i r o m e n tf o rd i g i t a lm i n e k e yw o r d s ：d i g i t a lm i n e ；m 2 u s s i v es p a t i a ld a t a ；p cc l u s t e r ；p a r a l l e lp r o c e s s i n g ； v i s u a l i z a t i o n 东北大学硕士学位论文目录 目录 中文摘要i i a b s t r a c t i i i 第1 章绪论1 1 1 研究背景与研究意义1 1 2 国内外研究现状2 1 2 1 并行计算硬件环境2 1 2 2 并行程序设计模型3 1 2 3 并行三维图形绘制4 1 3 本文研究内容和章节安排7 第2 章理论与技术基础9 2 1 并行编程相关理论算法9 2 1 1 并行编程模型9 2 1 2 并行程序设计思路9 2 1 4 并行处理中的负载平衡9 2 2 并行程序开发工具1 0 2 2 1m p i 简介1 0 2 2 2c h r o m i 啪简介1o 2 3 矿山三维可视化建模1l 2 3 1 三维空间构模方法1l 2 3 2 基于g t p 的矿山三维地学构模1 2 2 3 3 矿山精细三维建模1 3 2 4 本章小结1 4 第3 章面向数字矿山的p c 集群搭建1 5 3 1p c 集群简介1 5 3 1 1p c 集群系统定义和发展1 5 东北大学硕士学位论文目录 3 1 2p c 集群的特点与优势1 6 ： 3 2 面向数字矿山的p c 集群搭建17 i 3 2 1 硬件选择及搭建设计1 7 3 2 2 集群操作系统选择及安装18 3 2 3 并行开发环境的安装2 0 “ 3 3 本章总结2 0 第4 章数字矿山海量数据并行处理2 2 4 1 三维地质体快速海量v o x e l 化并行计算2 2 4 1 1 算法原理2 2 4 1 2 算法实现：2 5 4 1 3 算法测试与分析2 9 4 1 4 精确储量计算3 4 4 2 本章小结3 5 第5 章并行环境下数字矿山三维可视化3 6 5 1 并行环境下矿山三维海量数据显示3 6 5 1 1 矿山精细建模三维海量数据3 6 5 1 2 矿山三维海量数据并行显示实现3 8 5 1 3 并行环境下矿山三维海量数据显示测试与分析4 3 5 2 数字矿山精细模型三维并行高分辨率显示5 2 5 2 1 基于p c 集群搭建数字矿山高分辨率大屏幕墙5 2 5 2 2 数字矿山精细模型三维并行高分辨率显示效果5 4 5 3 本章小结5 6 第6 章结论与展望5 7 6 1 本文主要研究成果5 7 6 2 后期工作和展望5 7 参考文献5 9 致谢6 l 在学期间参加的科研项目和发表的论文6 2 东北大学硕士学位论文第1 章绪论 第1 章绪论 1 1 研究背景与研究意义 随着我国矿业水平不断发展，矿山企业对建立数字矿山并为我国矿业服务的 呼声越来越高。数字化和可视化技术应用到矿业工程中，将为矿山建设和资源开 采提供有力的支持，可以有效的管理矿山工程地质的海量数据信息，提高地质资 料的利用效率，根据地质信息采用数字化和可视化技术建立三维矿山地质模型可 以为矿业生产和环境保护提供依据。为了实现上述目标，必须建立高精度的三 维矿山地质模型。 建立高精度的三维矿山地质模型，并运用此模型进行储量计算、采矿最优方 案自动设计、开采过程计算机模拟以及矿山三维有限元计算等矿山企业亟需解决 的问题，需要涉及到巨数据量的复杂计算。常规的串行编程算法很难在效率上满 足此类问题的求解。通过并行技术，采用并行程序设计模式可以大大提高求解效 率。但是由于并行技术打破了传统编程的顺序执行模型，大大增加了程序设计的 复杂度。针对目前计算机技术比较薄弱的矿业应用，对并行技术进行探讨研究， 通过研究并行技术为矿山海量数据处理服务具有重要意义。 并行技术包括硬件和软件两个方面。硬件方面主要分并行机和集群两大类， 前者发展时间较长，性能比较稳定，技术比较成熟，但价格昂贵；后者发展比较 迅速，目前运算性能已超过前者，且价格相对比较便宜。尤其从九十年代末开始， 随着单台p c 性能的不断提高，p c 集群以其极高的性价比受到各行各业广泛关注。 将p c 集群运用于矿山企业，可以在提高效能的同时大大降低成本。因此进行面 向数字矿山的p c 集群的研究具有重要意义；软件方面主要包括并行开发环境和 并行程序设计方法的研究。由于并行技术对于我国矿山企业还比较陌生，因此进 行针对面向数字矿山应用的并行开发环境和并行程序设计方法的研究，对提升我 国矿业技术水平具有重要意义。 数字矿山作为一个面向矿山实际应用的虚拟平台，必须提供一个多尺度，全 方位，多角度的三维可视化环境。由于矿山覆盖区域巨大、内部地质构造复杂， 这就需要进行矿山精细建模，如此带来矿山三维模型数据量倍增，造成矿山三维 可视化难以实现。因此有必要对海量数据复杂地质体进行高分辨率三维可视化研 东北大学硕士学位论文 第1 章结论 究；由于专业图形显示环境价格昂贵且领域局限性大，不适合我国中小矿山企业 普遍应用，如此对基于廉价的p c 集群的矿山三维可视化研究具有重要意义。 1 2 国内外研究现状 1 2 1 并行计算硬件环境 并行计算机就是由多个处理单元( c p u ) 组成的计算机系统，这些处理单元 相互通信和协作，能快速、高效地求解大型复杂问题乜1 。 1 2 1 1 并行计算机的分类与发展 随着并行计算机技术的不断发展，其性能不断提高、体系结构更加复杂、分 类更加丰富。f l y n n 口1 按照指令流和数据流的多倍性概念将计算机系统结构进行 了分类。其中指令流系指机器所执行的指令序列，数据流系指指令流所调用的数 据序列，而多倍性系指机器的瓶颈部件上所可能并行执行的最大指令或数据的个 数。根据指令流和数据流的不同组合，计算机系统可分为：单指令流单数据流 s i s d ( s i n 9 1 ei n s t r u e t i o ns t r e 锄s i n g l ed a t as t r e a i l l ) 、单指令流多数据流 s i m d ( s i n g l ei n s t r u e t i o ns t r e 锄m u l t i p l ed a t as t r e 硼) 、多指令流单数据流 m i s d ( m u l t i p l ei n s t r u e t i o ns t r e a ms i n 9 1 ed a t as t r e a m ) 以及多指令流多数据 流m i m d ( m u l t i p l ei n s t r u e t i o ns t r e a mm u l t i p l ed a t as t r e a m ) 。 1 2 1 2 当代并行机体系结构 依据并行计算机结构模型，当代并行机可分为瞳1 ： 1 并行向量处理机( p v p ) 2 对称多处理机( s m p ) 3 大规模并行处理机( m p p ) 4 分布共享存储多处理机( d s m ) 5 工作站机群( c o w ) 6 并行计算机体系合一结构 ， 东北大学硕士学位论文第1 章绪论 1 2 2 并行程序设计模型 并行程序设计模型( p a r a l l e lp r o g r a 舢i n gm o d e l ) 是针对计算机硬件体系结 构提供给并行程序开发的一组应用程序编程接口( a p i ，a p l i c a t i o np r o g r a 唧i n g i n t e r f a c e ) 。它是连接并行环境与用户程序的桥梁。典型的并行程序设计模型包 括数据并行模型、消息传递模型和共享存储模型三种乜钔。 1 2 2 1 数据并行模型( d a 切一p a r a e im o d e ) 数据并行模型h 3 的基本特征是并行执行作用于一个大数据集中不同部分的 同一个操作。数据并行依据并行粒度的大小，既可以在s i m d 计算机上实现，也 可以在s p m d 计算机上实现。s i m d 实现着重开发细粒度的指令级并行性，而s p m d 实现则着重开发中等粒度的过程( 子程序) 级并行性。数据并行的程序设计模型强 调局部计算和数据选路操作，它适合于使用规则网络结构来求解细粒度的并行应 用问题。数据并行操作通常在编译时完成，其中硬件同步由s i m d 程序的锁步操 作完成。在同步的s i m d 程序中，所有处理单元间的通信直接由硬件控制，处理 单元间的数据并行操作和数据通信都是通过锁步来完成。典型的支持数据并行的 软件系统包括p c + + 阳1 、z p l n 0 1 和p o o m a 1 等。 1 2 2 2 消息传递模型( m e s s a g e - p a s s i n gm o d e i ) 消息传递模型盯1 的特点是驻留在不同结点上的进程通过网络传递消息来相 互通信。消息可以是指令、数据、同步信号或者中断信号等。在消息传递并行程 序中，用户必须明确地为进程分配数据和计算任务，它比较适合开发粗粒度性的 并行程序。各个进程之间是多线程的和异步的，需要路障这样的显式同步操作来 确保正确的执行顺序。每个进程都拥有独立的地址空间。消息传递模型比数据并 行模型更加灵活，两种广泛使用的消息传递系统p v m 2 1 和m p i n 3 一钔使得消息传递 程序具有较好的可移植性。典型的消息传递系统包括p v m 、m p i 、p a r a + + n 射、 t p o + + 1 们、g m p 1 7 1 钔、o o m p i 1 引，a r m i 2 0 1 等。 1 2 2 3 共享存储模型( s h a r e dm e m o r ym o d e i ) 共享存储模型，也称为共享变量模型( s h a r e dv a r i a b l em o d e l ) 。在共享 东北大学硕士学位论文第l 章绪论 存储模型中，驻留在各处理器上的进程可以通过读写公共存储器中的共享变量相 互通信。它与数据并行模型的区别在于共享存储模型是多线程的和异步的。数据 在单一共享地址空间中，因此不需要显式数据分配，工作负载也可以隐式分配。 通信操作通过对共享变量的读写隐式完成，而同步操作必须是显式的，以保证程 序的正确执行次序。典型的共享存储系统包括p o s i xt h r e a d s ( p t h r e a d s ) 乜1 i 、 o p e n m p 2 刳、j a v at h r e a d s 2 3 3 等。 1 2 3 并行三维图形绘制 1 2 3 1 计算机图形学发展趋势 计算机图形学是计算机科学与技术的一个重要分支，它是研究如何用计算机 以及图形图像外围设备来生成、处理和显示图像及视频的一门科学啮3 。目前在机 械、电气、建筑、医药、化学、航空、教育、娱乐等领域应用比较广泛。随着计 算机性能的不断提高，计算机在图形图像上的处理能力越来越强大，计算机图形 学由二维表达进入了三维表达的时代。 目前计算机图形学面临三大趋势哺1 ： 第一、更强的真实感绘制，表现为包括光线跟踪算法和辐射度方法在内的大 量复杂真实感绘制算法的出现和迅速发展。1 9 8 4 年，美国c o r n e l l 大学1 的学 者将热辐射工程中的辐射度方法引入到计算机图形学中，用辐射度方法成功地模 拟了理想漫反射表面间的多重漫反射效果，将真实感图形绘制推进到一个新的阶 段。经过二十多年的发展，光线跟踪和辐射度模型成为当今真实感图形学中最重 要的两个图形绘制技术，以它们为基础衍生出大量的真实感图形绘制算法降3 ， 算法复杂度越来越高，所模拟的场景越来越复杂，图形效果越来越真实，在计算 机辅助设计和图形学领域得到了广泛的应用。 第二、更高的模型复杂度。随着以c a d 软件的进步和一些先进的精密建模设 备如核磁共振、c t 和激光扫描仪等的出现，模型的精度和复杂度大为提高。同 时场景范围进一步扩大，包括大范围的地形和环境，使得模型复杂度和数据量进 一步增加。如北卡大学w a l k t h r o u g h 计划口列的d o u b l ee a 9 1 et a n k e r 模型有8 千3 百万面片，而斯坦福大学数字米开朗基罗计划1 中的大卫雕像更多达2 0 亿 面片，数据量十分惊人。 第三、更快的图形处理速度。直接反映为计算机图形处理硬件的迅猛发展。 ， 东北大学硕士学位论文第1 章绪论 计算机显卡由简单的图形芯片发展到以可编程图形处理芯片( g p u ) 为核心的高 性能图形处理卡口钔。2 0 0 7 年最新的图形处理卡( 以n v i d i a 公司的g e f o r c e8 系 列剐和a t i 公司的r a d e o nh d 系列m 1 ) 的制造工业达到6 5 纳米，晶体管数量超 过6 亿个，核心频率达到6 7 5 m h z ，最大显存容量7 6 8 m b ，显存带宽超过1 0 0 g b s e c ， 具有1 2 8 个流处理单元。材质填充率超过4 0 b i l l i o n s e c ，分辨率达到 2 5 6 0 1 6 0 0 ，性能已经超过了几年前专业图形工作站的高端图形处理硬件。因此 近年来采用便宜的p c 来满足部分图形处理领域的要求己经成为现实。 1 2 3 2 基于p c 集群集的并行图形绘制系统优势 尽管图形处理硬件的处理能力和处理速度都大幅提高，但是面对越来越复杂 的绘制算法和庞大而复杂的场景模型数据，独立图形硬件处理起来仍然捉襟见 肘，面向个人用户设计的p c 的图形处理能力更加难以应对。而且从二十年来的 发展趋势看，图形处理硬件技术的提高总是无法跟上社会应用领域需求的增长， 因此并行图形处理技术作为一种高性能图形绘制的解决方案一直受到研究者的 重视，而基于p c 集群机的并行图形绘制系统因为诸多优点成为近几年来的研究 热点。 基于p c 集群集的并行图形绘制系统用便宜但功能日益强大的p c ，依托高速 网络组建为p c 集群机作为硬件平台，在此硬件平台上构建并行图形绘制系统作 为软件平台，可以将单个p c 无法完成的绘制任务分布到集群机的多个p c 节点上 完成，实现高性能图形绘制。相对于昂贵的专业图形工作站，基于p c 集群机的 并行绘制系统具有以下优势口刀： 1 高性价比：一个3 2 个p c 节点的p c 集群机只需百万人民币左右，而同级别 处理能力的高端专业图形工作站需要数百万美元，组建p c 集群机相对便宜许多： 2 升级方便：p c 集群机的每个节点都是独立的p c ，可以花很小的代价按照当 前最新技术成果更换配件，使p c 集群机性能保持最新。相对而言，传统专业图 形机内部共享内存和i o 子系统，更新换代的代价常高得难以接受。 3 高可扩性：p c 集群机的计算速度、存储容量等性能在一定范围内大致随其 拥有的p c 节点数量的增长而线性增长，这使它易于扩展以满足更高的处理要求。 而专业图形机的扩展性逊色不少。 4 使用灵活：p c 集群机中的节点相互依赖性小，可以相对独立的完成不同任 务，并且可以不局限于图形处理领域，而图形工作站是专为图形处理设计，应用 东北大学硕士学位论文第l 章绪论 领域受限制。 5 多屏拼接显示墙：通过在指定p c 节点上连接投影仪，基于p c 集群机的并 行图形绘制系统可以方便地构建多屏拼接显示墙，提供更广的视域范围和更高的 分辨率，营造沉浸式的虚拟环境。 1 2 3 3 并行图形绘制模型介绍 图形处理过程通常用流水线模型进行描述。图形处理流水线与c p u 流水线的 概念相似，它将整个图形处理过程划分为多个流水阶段，以流水作业的方式分阶 段实现图形计算。当前工业界占主导地位的两个图形处理库( o p e n g l 和d i r e c t 3 d ) 具有类似的流水线模型，其中o p e n g l 更接近硬件底层，使用灵活，技术标准透 明更易于取得技术支持，所以当前绝大多数的并行图形绘制系统是在o p e n g l 的 基础上进行并行扩展。图1 1 是o p e n g l 的典型图形流水线啪1 ，它描述了场景数 据经过几何处理( g e o m e t r yp r o c e s s ) 和光栅处理( r a s t e r i z a t i o np r o c e s s ) 后转 化成可在显示设备上显示的像素的过程。 图1 1 典型的图形流水线( 据、 ，、 ，、 ，o p e n 9 1 o 唱) f i g 1 1a1 卯i c a lg r a p h i c s p i p e l i n e ( v ，1 n v o p e n 9 1 o 嘲 并行图形绘制系统中，场景绘制由p c 集群机中担任绘制任务的p c 节点完成， 每个p c 节点上的图形处理卡都是一条完整的图形绘制流水线，包括几何和光栅 两个基本处理过程，担任绘制任务的p c 节点称之为绘制服务器。绘制时，场景 数据需要按照一定的任务划分策略分配到不同的绘制服务器上，这个数据划分和 分配的过程称为归属判断( s o r t ) 。m o l n a r h 等人根据归属判断发生的方式和时 机，将并行图形绘制系统归为三类：s o r t f i r s t ，s o r t m i d d l e ，s o r t 一1 a s t 。 s o r t f i r s t 类并行图形绘制系统的归属判断在几何处理之前进行，最终显 ， 东北大学硕士学位论文第1 章绪论 示屏幕的图像空间被划分为多个区域分配给不同的绘制服务器。绘制每一帧l j 先 根据场景几何数据在显示屏幕上的投影确认负责处理的绘制服务器，然后将相应 数据发送到此绘制服务器处理，绘制完成后将所有绘制服务器的结果拼接成最终 显示图像。s o r t f i r s t 的优点是各条流水线完整而独立，故特别有利于构建集 群式并行图形绘制系统。归属判断是此类并行图形绘制系统的主要开销和瓶颈所 在。典型的s o r t f i r s t 类并行图形绘制系统有w i r e g l 【4 p “1 、d i s p l a y w a l l 例等。 s o r t m i d d l e 的归属判断发生在几何处理之后、光栅化之前，即在几何处理 阶段每个服务器处理整个场景数据的一部分，几何处理后的输出按照屏幕分块送 入相应流水线的光栅化处理阶段。s o r t m i d d l e 类并行图形绘制系统要求得到绘 制流水线几何处理后、光栅化之前的中间结果进行重分布，而p c 集群机所采用 的商业图形卡一般将几何处理和光栅化功能集成在一起，很难得到流水线的中间 结果，这限制了s o r t m i d d l e 类系统在p c 集群机上的应用。但s o r t m i d d l e 在 某些商业图形处理硬件上得到应用，如i n f i n i t e r e a l i t y “8 3 、p g l h 刀等。 而s o r t 一1 a s t 类系统不对图像空间进行划分，只将场景数据等分为若干子 集，子集的划分不受空间范围的限制，保证三角面片数量大致相等以保持负载平 衡即可，这使s o r t 一1 a s t 的归属判断与s o r t f i r s t 和s o r t m i d d l e 不同。每个 数据子集进入相应服务器的绘制流水线进行几何处理和光栅化后得到一副全屏 幕大小的图像，所有图像进行逐像素深度合成后得到最终的显示结果。s o r t l a s t 最大的优点是简明，场景数据的不均匀分布引起的负载失衡较小，但增加了一个 像素合成的处理步骤。像素的传输和合成是s o r t 一1 a s t 并行图形绘制系统的主要 开销和瓶颈所在。p i x e l f l o w 柏一们、p a r a l l e l m e s a 5 0 1 等都是典型的s o r t l a s t 并行绘制系统。 一 1 3 本文研究内容和章节安排 本文研究目标包括：构建面向数字矿山的p c 集群，并在此p c 集群环境下进 行矿山三维海量数据并行处理与可视化的研究和实现。 围绕着三个研究内容本文章节安排如下： 第二章主要介绍并行程序开发原理以及相应开发工具，同时对矿山三维建模 进行介绍，并介绍通过g t p 三维建模结合地质剖面数据实现矿山精细建模的方 法。建立虚拟的矿区复杂地下三维模型数据，并作为后几章节测试数据。 第三章主要介绍面向数字矿山的p c 集群搭建。探讨如何利用矿山已有p c 东北大学硕士学位论文 第l 章绪论 机进行集群搭建，从而降低成本。通过统一存储方便了集群的配置和节点增删管 理。安装相应并行开发软件，使p c 集群可以进行高强度科学运算和三维图形可 视化两方面的并行程序开发。 第四章主要在三维地质体快速海量v o x e l 化并行程序开发实现基础上，探讨 矿山三维海量数据的并行处理，并依据生成的v o x e l 数据进行地质储量运算。着 重分析讨论了并行处理中区域划分、数据传输、计算与数据传输并行以及终止条 件判断这四大难点的实现。通过大量测试进行了集群性能分析，得出相应结论。 第五章主要在对矿山三维海量数据并行显示程序开发实现，以及矿山精细模 型三维并行高分辨率显示程序开发实现基础上，探讨矿山三维海量数据的并行可 视化。并通过大量测试，总结出p c 集群适合矿山三维海量数据显示。 8 东北大学硕士学位论文 第2 章理论与技术基础 第2 章理论与技术基础 2 1 并行编程相关理论算法 2 1 1 并行编程模型 并行程序设计模型是建立在硬件系统结构模型之上的一组程序的抽象，它定 义了程序的设计与其实现之间的一种形式化的接口，为并行程序的设计者提供了 一个简洁而清晰的并行机硬软件系统结构的概念模型。常见的并行程序设计模型 有：共享变量模型( s h a r e dv a r i a b l em o d d ) 、信息传递模型( m e s s a g ep a s s i n g m o d e l ) 和数据并行模型( d a t ap a r a l l e lm o d e l ) 三种。 2 1 2 并行程序设计思路 并行算法设计有四个步骤：首先将给定问题划分成一些小的任务，划分方法 可以使用域分解法或功能分解法；其次分析诸任务之间的通信需求，通信可以是 局部的或全局的，静态的或动态的，结构化的或非结构化的以及同步的或异步的； 然后使用组合方法，在尽可能保持灵活性的同时，减少通信和开发成本；最终以 最小化总执行时间为目标将诸任务分配给各处理器，使用负载平衡和任务调度技 术可以改善映射的质量。 具体设计思路如下： 1 ) 将一个大任务分解为若干小任务，找出可并行部分，使用消息传递库中的 函数进行编程； 2 ) 把这些小任务分散到不同的节点作为进程同时执行； 3 ) 节点中的并行任务进程利用消息传递库中的函数彼此通信： 4 ) 各个小任务完成后的装配集成。 2 1 4 并行处理中的负载平衡 在并行系统中，任务或作业被分配到各个处理结点上并行执行，称之为负载。 负载平衡( l o a db a l a n e e ) 是研究使重负载的处理机转移一部分任务到某些轻负 东北大学硕士学位论文第2 章理论与技术基础 载处理机中，使系统负载均衡地分布于系统处理机中的策略和算法，充分发挥工 作组中所有成员的能力，避免忙闲不均情况，从而改进系统整体性能。负载平衡 主要研究三大策略问题： ( 1 ) 传输策略( w h e n ) ：决定何时进行负载的远程执行或迁移： ( 2 ) 定位策略( w h e r e ) ：定位什么样的目的处理机作为负载分派的目的对象： ( 3 ) 选择策略( w h i c h ) ：选择哪一个任务远程执行或进行迁移。 有效地将各并行任务或作业比较均衡地分布到不同的处理结点并行计算，使 各结点的利用率达到最大，是研究负载平衡技术的目的。 2 2 并行程序开发工具 2 2 1m p i 简介 m p i 是一种消息传递型并行通信的程序设计规程，也就是一个消息传递库， 库函数可以嵌在c 、c + + 和f o r t r a n 等语言中调用，即在标准的程序设计语言的 基础上，加入实现进程间通信的m p i 消息传递函数，就构成了m p i 并行程序设计 所依赖的并行编程环境h 叫。 m p i 的标准化开始于1 9 9 2 年4 月2 9 日至3 0 日在威吉尼亚的威廉姆斯堡召 开的分布式存储环境中消息传递标准的讨论会，由d o n g a r r a ，h e m p e l ，h e y 和 w a l k e r 建议的初始草案于1 9 9 2 年1 1 月推出，并在1 9 9 3 年2 月完成了修订版， 这就是m p l l o 。为了促进m p i 的发展，一个称为m p i 论坛的非官方组织应运而 生，该论坛对m p i 的发展起了重要的作用。 2 2 2c h m m i u m 简介 c h r o m i u m 是用来在集群环境中进行交互式三维显示的开发工具，它具有完 全可扩展的体系结构，通过它可以在集群环境下进行并行三维图形显示的开发。 c h r o m i u m 具有如下几个特点陋1 1 支持s o r t f i r s t 模型： 2 支持s o r t l a s t 模型； 3 支持s o r t f i r s t 与s o r t l a s t 混合模型； 4 o p e n g l 命令流水线的过滤功能； 东北大学硕士学位论文第2 章理论与技术基础 5 对o p e n g l 提供强大的兼容性； 6 可以第三方对其进行并行功能扩展而提高总体性能； 7 支持多种平台，可运行在l i n u x 、i r i x 、a i x 、s u n 0 s 以及w i n d o w s - b a s e d 系统下； 8 属于开源项目。 2 3 矿山三维可视化建模 2 3 1 三维空间构模方法 3 d 空间构模方法研究是目前3 dg i s 领域以及3 dg m s 领域研究的热点问题。 许多专家学者在此领域做了有益的探索。地质、矿山领域的一些专家学者，围绕 矿山地质、工程地质和矿山工程问题，对3 dg m s 的空间构模问题进行了卓有成 效的理论与技术研究，加拿大、澳大利亚、英国、南非等国还相继推出了一批在 矿山和工程地质领域得到推广应用的3 dg m s 软件。 表2 13 d 空间构模方法分类( 吴立新，史文中等，2 0 0 3 ) 1 a b l e 2 1c l 勰s i f i c a t i o no f3 ds p a _ i i a lm o d e l i n gm e t h o d s ( w ul i x i n ，s h iw 色n z h o n ge ta l ，2 0 0 3 ) 体模型( v o i u l ln e t r i cm o d e l )混合模型( m i x e d 面模型( f k i a lm o d e l ) 规则体元非规则体元 m o d e l ) 不规则三角网( t n )结构实体几何( c s g )四面体格网( t e n ) t i n c s g 混合 t n o c t 陀e 混合或 格网( g r i d )体素( v o x e j )金字塔( p y r a m i d ) h y b r i d 模型 w i r ef m m e b l o c k 混 边界表示模型( b - r e p )八叉树( o c t r e e )三棱柱( t p ) 合 线框( w i 陀f r a m e ) 或 地质细胞 相连切片( l i n l ( e d针体( n e e d l e ) o c 吮e t e n 混合 s l i c e s ) ( g e o c e l l u l a r ) 断面序列规则块体非规则块体 ( s e r i e ss e c t i o n s )( r e g u l a rb l o c k )( i r r e g u l a rb l o c k ) 断面三角网混合 实体( s o l i d ) ( s e c t i o n - t i nm o d e l ) 多层d e m s3 d v b r o n o i 图 广义三棱柱( g t p ) 东北大学硕士学位论文第2 章理论与技术基础 过去十来年中，研究提出了2 0 余种空间构模方法。若不区分准一3 d 和真一3 d ， 则可以将现有空间构模方法归纳为基于面模型( f a c i a lm o d e l ) 、基于体模型 ( v o l u m e t r i cm o d e l ) 和基于混合模型( m i x e dm o d e l ) 的3 大类构模体系，如 表2 1 所示【5 ，5 1 】。 1 ) 基于面模型的空间构模 基于面模型的空间构模方法侧重于三维空间实体的表面表示，如地形表面、 地质层面、构筑物( 建筑物) 及地下工程的轮廓与空间框架等。所模拟的表面可 能是封闭的，也可能是非封闭的。基于采样点的t i n 模型和基于数据内插的g r i d 模型，通常用于非封闭表面模拟；而b r e p 模型和w i r ef r 锄e 模型通常用于封 闭表面或外部轮廓模拟。s e c t i o n 模型、s e c t i o n t i n 混合模型及多层d e m 模型 通常用于地质构模。通过表面表示形成三维空间目标表示，其优点是便于显示和 数据更新，不足之处是由于缺少3 d 几何描述和内部属性记录而难以进行3 d 空间 查询与分析。 2 ) 基于体模型的空间构模 基于体模型的空间构模侧重于三维空间体的表示，如地层、矿体、水体、建 筑物等，通过对体的描述实现三维空间目标表示，优点是易于进行空间操作和分 析，但存储空间大，计算速度慢。目前常用的体构模法有三维栅格、实体几何结 构( c s g ) 、四面体格网( t e n ) 、实体和块段构模等。 3 ) 基于面体混合模型的空间构模 由于地质现象极其复杂，单纯的面构模和体构模要么不能精确表达三维地质 体的边界，要么不能很好的表达地质体内部属性的变化。所以，近年来研究工作 集中在多种模型的集成和混合以及基于这些模型的处理和分析算法上。 2 3 2 基于g t p 的矿山三维地学构模 我国学者在矿山三维地学构模领域进行了大量的科研工作，针对地质体钻孔 尤其是深钻的偏斜特点，提出了一种不受三棱柱棱边平行即( 钻孔垂直) 限制的 新的3 d 构模方法，称为类三棱柱( a n a l o g i c a lt r i p r i s m ，a t p ) 构模技术( 吴 立新等，2 0 0 2 ；齐安文等，2 0 0 2 ) ，后发展为广义三棱柱( g e n e r a l i z e dt r 卜p r i s m ， g t p ) 构模技术( w ul x ，2 0 0 2 ，2 0 0 3 ) 。 g t p 构模原理是：用g t p 的上下底面的三角形集合所组成的t i n 面来表达不 同的地层面，然后利用g t p 的侧面的空间四边形面来描述层面问的空间邻接关 东北大学硕士学位论文第2 章理论与技术基础 系，用g t p 柱体来表达层与层之间的内部实体。 2 3 3 矿山精细三维建模 2 3 3 1 建模原理与步骤 g t p 建模数据主要来自于钻孔数据，其表达突出了地层与层之间的拓扑关系， 但地层的几何信息受钻孔数量的限制，表现力相对不足( 见图2 1a ) 。地质剖面 图以剖面形式展示地下中各地层几何信息，由于加入了人工地质推理过程，其几 何信息非常丰富，但由于地质剖面图是二维的，无法像g t p 一样能够表达地层间 的三维拓扑关系( 见图2 1b ) 。结合以上两种矿山常有构模方法，以g t p 为模型 组织方式，通过地质剖而图进行g t p 的加密，从而实现矿山精细三维建模。 a 1 3 0 个钻孔g t p a ( n pso f1 3 0 sb o r e h o l e b 地质剖面图 b ag e o l o g i c a l 呻f i l e 图2 1 矿山精细建模数据 f i g 2 1d a t a 衙c r 咖e l a b o 眦m i i l e m o d e l 构模思路为：在g t p 构模