（计算机系统结构专业论文）地震数据处理中的并行计算技术研究.pdf

硕士学位论文 摘要 地震数据处理一直是高性能计算的主要领域之一，本文以海量地震数据处理 为研究对象，其主要工作和创新点包括三方面的内容：设计并实现了网络化的并 行地震数据处理支撑框架；为框架设计了一个基于n e t c d f 数据格式的并行i 0 子 系统，并对其关键算法进行了深入研究；将m p i + o p e n m p 模型引入到现有的并行 地震数据处理中，实现了一个可以支持多种并行地震数据处理模型的支撑库。 首先，设计并实现了网络化的并行地震数据处理框架，框架为实验人员提供 一个集成的实验环境，内容包括地震数据处理和数据显示分析。框架提供的流程 构建器允许用户在客户端利用服务器上模块库中的模块来构建处理流程、提供交 互式的模块参数设置界面，具有新建工程、模板保存等强大的编辑功能。平台同 时为地震数据处理模块开发者提供一个集成的开发平台，利用该平台定义的具有 较好容错能力的a p i 接口，开发者不需要了解与平台相关的分布式计算相关知 识，专注模块处理算法的开发。实践证明，借助框架可使油气勘探研究人员开发 并行数据处理和显示模块的效率大幅度提高。 其次，在深入分析原有并行文件系统和n e t c d f 地震数据格式特点的基础上， 为并行地震数据处理系统设计了一个基于n e t c d f 的高效、高可靠的专用并行文 件系统，重点研究了文件系统的文件分片算法，数据备份恢复技术，并在l i n u x 集群上实现该系统原型。实验表明，文件系统可以使地震数据处理最常见的简单 并行达到很高的并行效率，且文件越大这种优势越明显。 最后，将基于消息传递( m p i ) 的并行地震处理模型与共享存储( o p e n m p ) 模型 相结合，实现了一个适合于s m p 集群并行地震数据支撑库，将涉及到消息传递 的并行地震数据操作以直观的a p i 的形式提供给开发人员，利用支撑库提供的 a p i 开发了一些测试模块，实验证明：支撑库可支持现有地震数据处理和显示模 块的多种并行计算模型，并且能够获得较高的并行加速比和计算效率。 关键词：地震数据处理；并行i 0 ：文件系统；o p e n m p ；m p i 地震数据处理中的并行计算技术研究 a b s t r a c t s e i s m i cd a t ap r o c e s s i n gi sam a i na r e a so fh i g hp e r f o r m a n c ec o m p u t i n g ，t a k i n g s e i s m i cd a t ap r o c e s s i n gf o ri t sr e s e a r c ho b j e c t ，t h em a i nc o n t e n ta n di n n o v a t i v e p o i n t so ft h i sp a p e rc a nb eo u t l i n e da st h ef o l l o w i n ga s p e c t s ：w ep r e s e n tai n t e g r a t e d s o f t w a r ef r a m e w o r kf o rp a r a l l e ls e i s m i cd a t ap r o c e s s i n go np cc l u s t e r ，d e s i g na p a r a l l e li 0s u b s y s t e mb a s e do nn e t c d ff o rt h ef r a m e w o r k ，c o m b i n e st h ee x i s t i n g p a r a l l e l s e i s m i cd a t a p r o c e s s i n gp a t t e r n s b a s e do nm p lw i t hs h a r em e m o r y p r o g r a m m i n gp a r a d i g m ( o p e n m p ) ，p r o v i d i n g ap a r a l l es e i s m i cd a t ap r o c e s s i n g s u p p o r tl i b r a r yf o rt h ef r a m e w o r k f i r s t ，w ep r e s e n tai n t e g r a t e ds o f t w a r ef r a m e w o r kf o rp a r a l l e ls e i s m i cd a t a p r o c e s s i n go np cc l u s t e r am o d e r na n df e a t u r e - r i c hg r a p h i c a lu s e ri n t e r f a c e ( g u i ) w a sd e v e l o p e df o rt h es y s t e ma l l o w i n ge d i ta n ds u b m i s s i o no fp a r a l l e lp r o c e s s i n g f l o w sa n di n t e r a c t i o nw i t hr u n n i n gj o b s m u l t i p l ej o b sc a nb ee x e c u t e do nt h ep c c l u s t e ra n dc o n t r o l l e df r o mt h es a m eg u i t h ef r a m e w o r kp r o v i d e sam o d u l e i n t e g r a t e dd e v e l o p m e n te n v i r o n m e n t ( m i d e ) t op cc l u s t e rm o d u l ed e v e l o p e r s y s t e m m o n i t o r , d a t a b a s e ，m e m o r ym a n a g e m e n ta n dt h em p if u n c t i o n a l i t i e sa r ep r o v i d e dt o d e v e l o p e ra sa p i ，w h i c hc a ns i g n i f i c a n t l ys i m p l i f yt h ec o d ed e v e l o p m e n tf o rt h e s y s t e m am u l t i u s e rd e v e l o p m e n ta n dp r o c e s s i n ge n v i r o n m e n ti sa v a i l a b l e t h e s y s t e mc a ng r e a t l yr e d u c et i m ef o rt r a n s p l a n t i n gs e r i a lp r o c e s s i n gm o d u l e st op c c l u s t e r ，a n dg e tah i g hs p e e d u p s e c o n d ，a f t e ri n d e p t ha n a l y s i st h ee x i s t i n gp a r a l lf i l e s y s t e ma n dn e t c d fd a t a f o r m a t ，t h i sp a p e rd e s i g nae f f i c i e n t ，r e l i a b l ep a r a l l e li of i l e s y s t e mb a s eo nn e t c d f f o rt h ef r a m e w o r k ，t h ef i l e s y s t e mu s e san e wd a t as c a t t e ra l g o r i t h m ，c o m p a r i n gt ot h e e x i s t i n gp a r a l lf i l e s y s t e m ，t h ef i l e s y s t e mi m p r o v eg r e a t l yi nf a u l t - t o l e r a n ta n dd a t a b a c k u p r e c o v e r y ，t h ee x p e r i m e n t d e m o n s t r a t e sc a n t h o r o u g h l ys u p p o r ts i m p l e s e i s m i cd a t ap r o c e s s i n gp a t t e r n sa n dg e tah i g hp a r a l ls p e e d u p l a s t ，t h i sp a p e rc o m b i n e st h ee x i s t i n gp a r a l l e ls e i s m i cd a t ap r o c e s s i n gp a t t e r n s b a s e do nm p lw i t hs h a r e m e m o r yp r o g r a m m i n gp a r a d i g m ( o p e n m p ) ，p r o v i d i n ga p a r a l l e l s e i s m i cd a t ap r o c e s s i n gs u p p o r tl i b r a r ys u i t a b l ef o rs m pc l u s t e r ，t h e e x p e r i m e n td e m o n s t r a t e st h a tt h ep l a t f o r mc a nt h o r o u g h l ys u p p o r tc u r r e n ts e i s m i c d a t ap r o c e s s i n gp a t t e r n sa n dg e tah i g hp a r a l ls p e e d u p k e yw o r d s ：s e i s m i cd a t ap r o c e s s i n g ；p a r a l l e li o ；f i l e s y s t e m ；m p i ；o p e n m p n l 硕士学位论文 插图索引 图2 1 数据数据筛选技术5 图2 2 并行文件( p v f s ) 系统结构。7 图2 3 空间共享实例8 图2 4 作业复制实例8 图2 5 三种复杂的并行计算模型一1 0 图2 6 并行算法结构1 0 图2 7 加速比概念1 2 图2 8 等效率函数曲线1 3 图2 9 可扩展性概念1 3 图3 1 框架的体系结构一1 8 图3 2 网络并行开发模式1 9 图3 3 远程编译1 9 图3 4m i d e 2 1 图3 5 流程构建器2 2 图4 1 文件系统的体系结构2 8 图4 2 系统图形界面3 1 图4 3 系统应用实例3 3 图4 4 作业复制一3 3 图5 1s m p 集群体系结构3 6 图5 2m p i 程序的框架结构一3 7 图5 3 共享存储模型3 9 图5 4 并行地震处理模式复合4 3 图5 5s m p 集群混合编程模型m p i + o p e n m p 4 5 图5 6 混合模型并行地震数据处理流程4 6 图5 7 流程的加速比4 7 v i 地震数据处理中的并行计算技术研究 附表索引 表4 1p v f s 系性能测试( 4 个节点) 3 4 表4 2p v f s 系性能测试( 8 个节点) 3 4 表4 3 专用文件系性能测试( 4 个节点) 3 4 表4 4 专用文件系性能测试( 8 个节点) 3 4 表5 1m p i 模型在集群上的测试结果4 7 表5 2m p i + o p e n m p 模型在集群上的测试结果一4 7 v 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 作者签名： 粕恕日期：亏年；月7 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇 编本学位论文。 本学位论文属于 1 、保密团，在 1 年解密后适用本授权书。 2 、不保密口。 ( 请在以上相应方框内打“ j 作者签名：南芷 导师签名 日期： z o 田年；月刁日 醐洲孵朋矽日 硕士学位论文 1 1 课题来源 第1 章绪论 本课题来源于与美国n e x u s 公司合作项目“大规模地震数据并行处理系统”。 并部分受国家自然科学基金重大研究计划“重大工程的动力灾变”培育项目“网格 环境下地震模拟支撑系统的关键理论技术研究”资助( 9 0 7 1 5 0 2 9 ) 。 1 2 研究背景 高性能计算能力已经日益成为一个国家经济、科技与国防实力的重要组成 部分。由于科学工程计算和大规模商业事务处理需求的牵引，高性能计算中对 i o 处理能力的要求是无止境的。大规模多媒体应用要求大容量快速存储系统支 持，多用户事务处理环境要求快速i o 支持实时访问，而一些重大挑战性科学计 算课题更是追求计算机系统具有3 t 性能( e p 要求能提供1t e r a f l o p s 的计算能力， 1t e r a b y t e 的主存容量和1t e r a b y t e s 的i o 带宽) 。 近年来，随着大规模集成电路技术和网络技术的飞速发展，c p u 的性能大 约每三年就有一个较大的飞跃，网络带宽增长更快。而i o 设备的性能受制于机 械部件，发展缓慢。所以，高性能计算机系统中i o 系统与计算系统之间存在着 巨大的性能差距，而这种差距可能会成为未来大规模并行计算机的系统瓶颈。大 规模并行计算机计算能力与i o 处理能力不协调的问题越来越突出。怎样在大规 模并行计算机中进一步提高并行i o 能力，构成一个真正的超级并行计算环境， 以实现大规模并行处理，满足现代科学与工程技术研究发展的需要，是计算机科 学工作者必须要解决的问题和遇到的新挑战i 卜3 1 。 另一方面，石油勘探行业一直是高性能计算的主要应用领域之一。地震勘探 是利用人工激发的波场传播到地层，利用手工或计算机处理分析来自地层的波阻 抗界面的反射波、高速层的折射波，以确定地质构造和地层岩石的性质的过程【4 1 。 近年来，随着油气勘探深度的不断增大和勘探范围从陆地向海洋转移，所得到的 地震数据日趋庞大，对超级计算的软硬件提出了更高的需求。随着勘探工作程度 的加深，资源大量地被开采，地球物理勘探工作不断向新的深度和广度进军， 勘察精度的要求越来越高、难度变得越来越大，在处理方法上也提出了更新的要 求。 地震方法是油气勘探中最广泛使用的方法之一，由于采集数据量大、处理步 骤复杂，其数据处理通常都在大型计算机或工作站上进行。以往主要采用二维地 震控制构造形态，叠后偏移进行反射点归位，叠加次数一般为几十次。对于这些 地震数据处理中的并行计算技术研究 工作，当时的大型机还是可以满足需要。如今，为了查明不断缩小的勘察目标和 得到复杂构造的精确成像，勘探方式从二维勘探向三维勘探转移，处理方式从叠 后处理向叠前处理转移、常规处理向高精度处理转移，这些无疑都大大地增加了 数据处理量，普通大型计算机就难以满足需要了【5 ，6 】。 为并行地震数据处理系统设计一个高效，高可靠性的专用的并行文件系统。 用于将的海量n e t c d f ( - - 种面向数组型数据的描述和编码标准，目前广泛应用于 大气科学、水文、海洋学、环境模拟、地球物理等诸多领域) 格式的地震数据放 置到集群的i o 节点上，并建立高效的并行模型对并行文件系统中的数据进行处 理，对提高并行地震处理系统效率，充分利用超级计算机资源无疑具有相当重要 的意义。 1 3 本文主要工作 本文的主要工作体现在下面三个方面： 首先，设计并实现了网络化的并行地震数据处理框架，框架提供一个类似 v c 的模块集成开发环境( m i d e ) 可以实现不同地域的专业人员网络协作开发， m i d e 将并行分布式计算相关的操作封装好以a p i 的形式提供给用户，地球物理 专业程序员可以不需了解与分布式相关的知识，而专注于算法的开发，一个友好 的，多功能多用户图形流程构建环境，用户可以用它使用开发好的模块构建并行 作业流程并将流程提交给集群执行，实时监控集群上运行的流程，允许同时提交 多个流程并在同一个g u i 界面上监控。借助中间件可使油气勘探研究人员开发 并行数据处理和显示模块的效率大幅度提高。 其次，在深入分析原有文件系统和基于n e t c d f 地震数据格式特点的基础上， 为并行地震数据处理系统设计了一个基于n e t c d f 的高效，高可靠的专用并行文 件系统，专用文件系统采用一种全新的文件分片算法，且相对现有文件系统在容 错，数据备份恢复机制上有较大的改进。实验表明，文件系统可以使地震数据 处理最常见的简单并行达到很高的并行效率，且文件越大这种优势越明显非常适 合海量地震数据处理。 最后，首次将现有的基于消息传递( m p i ) 的并行地震处理模型与共享存储 ( o p e n m p ) 模型相结合，实现了一个适合于s m p 集群并行地震数据支撑库，将涉 及到消息传递的并行地震数据操作以直观的a p i 的形式提供给开发人员，利用 支撑库提供的a p i 开发了一些测试模块，实验证明，支撑库可支持现有地震数 据处理和显示模块的多种并行计算模型，并且能够获得较高的并行加速比和计算 效率。 2 硕士学位论文 1 4 本文的结构 全文分五章，本文的结构安排如下： 第一章概述了本文的课题来源，研究背景，研究目的及意义，主要工作及其 组织结构。 第二章详细介绍了背景知识及相关研究，工作站网络环境下提供高性能的 i o 所采取的主要解决方案，概述了在并行地震数据处理系统中，怎样建立并行 模型对数据服务器上的海量地震数据进行并行处理。 第三章介绍了网络化的并行地震数据处理框架的设计思想和框架的一些先 进特性，并简单介绍了用户在平台上开发地震数据处理模块的过程。 第四章从体系结构，数据的放置算法，数据备份恢复算法，应用实例等方面 详细介绍基于n e t c d f 数据格式的并行i o 子系统。 第五章将现有的基于消息传递( m p i ) 的并行地震处理模型与共享存储 ( o p e n m p ) 模型相结合，实现了一个适合于s m p 集群并行地震数据支撑库。 最后是全文的总结和展望。 3 地震数据处理中的并行计算技术研究 第2 章并行i o 及数据处理技术概述 地震数据处理和解释一直是高性能计算的主要领域之一，由于处理数据量大 数据读写次数频繁，i o 子系统一直是并行地震数据处理和解释系统的瓶颈，本 章前三节简述了在工作站网络环境下提供高性能的i o 所采取的主要解决方案， 以及国内外相应的研究进展。第四节概述了在并行地震数据处理系统中，怎样建 立并行模型对数据服务器上的海量地震数据进行并行处理。 2 1 并行i o 技术 2 1 1 提高i o 带宽解决方案 在工作站网络环境中，为了给应用提供高带宽的i o ，在硬件结构上一般使 用工作站网络的虚拟磁盘阵列。这时有两个问题需要考虑【7 1 。一是大文件的存储 结构。为了实现并行i o ，提高对文件的访问速度，并行文件系统一般都采用文 件分片的方式，将一个大文件分割成多个分片并以某种方式分布在磁盘阵列中。 二是i 0 子系统的实现方式。主要是如何实现一个高效的i o 子系统，采用什么方 式完成应用程序i o 请求。工作站网络的硬件结构在现有条件和环境下是基本固 定的，关键是在软件层面上采用什么方式来高效地实现i o 子系统。 通过上述分析，在工作站网络环境下提供高性能的i o 所采取的主要解决方 案是：( 1 ) 循环分片。将大文件进行分片并将其分布在工作站网络的各结点上，有 助于提高文件的并行读写效率。不同的分片方式对存取模式的i o 操作效率的影 响很大，关键是选择一种与工作站网络相适应的分片方式。这解决的是如何为大 的i o 请求提供高带宽的问题。工作站网络中的结点是平等关系，性能相近，循 环分片简单易管理，因此选择了循环分片方式。( 2 ) c o l l e c t i v e1 1 0 技术，目的是提 高磁盘存取操作的效率，特别是减少大量小的i o 请求带来的存取延迟，关键是充 分利用工作站网络的特点设计一种有效的c o l l e c t i v ei o 的体系结构。 提高i o 性能还有一种方案就是采用专用的并行文件系统比如o f s ( g l o b a l f i l e s y s t e m ) ，p v f s ( p a r a l l e lv i r t u a lf i l es y s t e m ) ，c o d a ( c o n s t a n td a t aa v a i l a b i l i t y ) 等，其中p v f s 的使用比较广泛，专用的并行文件系统虽然某些方面具有很高的 效率，也提供了通用的文件访问接口，但是每种文件系统都具有相应的缺点，因 此在实际应用中有很多人提出了改进方案，例如针对p v f s 并行文件系统法的元 数据服务器并行化，客户端缓存技术【 1 0 】。 2 1 2 聚合i o 技术 聚合( c o l l e c t i v e ) i o 是一种力图减轻由于映射关系导致的大量小请求所带来 4 硕士学位论文 的磁盘操作延迟的技术，基本思想是根据磁盘文件数据的分布信息，将各结点上 的进程所产生的大量d 、i 0 请求合并成少量大的i o 请求后再进行磁盘存取，提 高了一次磁盘读写的功效。c o l l e c t i v ei o 基于并行程序通常具备的对称性，当 i o 发生时，集群中所有节点运行到各自子进程的相同位置，因此会在一个很短 的时间间隔内各自发出i o 请求。c o l l e c t i v e i o 合并这些小的读写请求成为大的 读写请求，从而减少磁盘磁头移动和i o 次数，提高i o 速度【1 】。 c o l l e c t i v ei o 有不同的实现方案；如果在i o 服务器上合并文件请求则成为 s d i o ( s e r v e r d i r e c t e di o ) 1 1 l ：如果在磁盘这一层次把小而零散的i o 请求的请求 合并为大的请求，它就成为d d i o ( d i s kd i r e c t e di o ) 1 1 2 l ；如果客户端合并文件请 求则被称为两阶段i o ( t w op h r a s ei o ) 。 单独的c o l l e c t i v ei o 对于系统性能的提高并不充分，将数据筛选( d a t a s i e v i n g ) c o l l e c t i v ei o 相结合，能显著地提高并行i o 系统的性能f 7 1 。d a t as i e v i n g 基于读取数据的区域特征。如图2 1 所示当一个进程连续发出位置不连续的多个 读请求的情况时，这些请求的数据基本在某个区域内，因此可以连续读取整个区 域，再根据请求位置在内存中再次分配数据，从而减少程序的i o 次数。在几个 请求中间跨度很大情况下，d a t as i e v i n g 可能会因为读入太多的无效数据而降低 系统性能。智能的s i e v i n g 技术会判断s i e v i n g 的代价，再决定是否应该整片读 取数据。 用户请求一一1 系统缓冲0 一_ 一 2 乙j j j7 r 。 二： ： 一 蔓堇釜芦3 1 对多个不连续的缓冲区进行合并 2 从磁盘上读出连续的数据 3 根据请求将数据拷回用户缓冲区 2 2 并行文件系统 图2 1 数据数据筛选技术 2 2 1 概述 大型的仿真计算或数据密集型应用中，需要并行文件系统来完成大量的数据 文件的读入写出，p v f s ( p a r a l i e lv i r t u a lf i l es y s t e m ) 并行文件系统是在基于p c 的l i n u x 微机集群系统中最成功的并行文件系统之一，不仅有3 种用户访问模 式、简单方便的系统配置过程，更与m p i ( m e s s a g ep a s s i n gi n t e r f a c e ) 的主流实现 m p i c h 2 的m p i i o 有直接的接1 2 i m r o m i o 。p v f s 是迄今为止l i n u xp c 集群系 5 地震数据处理中的并行计算技术研究 统中最成功的并行文件系统之一，被广泛的应用和研究。 p v f s 往往是在l i n u xp c 集群上，与计算用的节点共享p c 硬件，这样部署 时，元数据服务- 器( m e t as e r v e r ) m g r 软件和数据服务：器( d a t as e r v e r ) i o d 软件 是直接安装在计算节点上的，也就是说集群上的每个节点既是计算用的节点也 适用于并行i o 的节点，因此这种方式会因为计算节点进行1 0 操作而影响正常 的计算处理，降低系统的效率。另外一种方式是形成单独的数据服务系统利用多 台p c 安装m g r 和i o d 来专门提供并行文件服务，这样可以实现计算任务与并 行文件i o 任务的分离，类似于通道处理器减轻主处理负担的作用一样，可提升 系统的计算性能和文件1 0 性能。 第一种方式影响性能而第二种方式的p c 硬件代价太高，因此需要开发一个 更高性价比的p v f s 系统以实现不影响计算节点的性能并降低系统整体成本。首 先分析系统中三个部件之间的互动与接口关系，然后设法通过软件开发与移植 来替换昂贵的p c 硬件基础上的数据服务器。 2 2 2 并行文件系统( p v f s ) 介绍 p v f s 的系统构成形式如图2 2 包括数据服务器( 运行i o d ) ，元数据服务器 ( 运行m g r ) ，和客户端( 运行l i b p v f s ) 数据文件通过条块化( s t r i p i n g ) j 丞段存储在各 个数据服务器上，因此可以并发地向客户端提供数据，在客户端的文件请求处理 过程中，需要先从元数据服务器获得文件数据在数据服务器上分布情况的有关信 息然后客户端才通过网络向数据服务器请求所需的数据块。图2 2 中计算节点通 过网络与p v f s 系统的元数据服务器，和数据服务起相连，元数据服务器是数据服 务器上数据的索引，计算节点需要访问数据服务器上的数据时先查找元数据服务 器，找到对应数据在数据服务器上的位置。据文件是通过条块化分配到多个数据 服务器上的。这个分配在创建文件时确定，因此对于一个特定的文件指定偏移量 的数据是固定在某个i o d 服务器上的。 客户机进行一次文件操作的过程如下：向运行m g r 程序的m a n a g e m e n t 节 点发出元数据请求，获得文件在数据服务器上的分布情况；然后根据分布情况 和数据偏移及数据量，可能对一个或多个数据服务器进行一次或多次读写，由 于是多个数据服务器同时向所有客户机服务，因此系统的总吞吐量是各个数据 服务器的总和。 由于i o d 与客户机和元数据服务器之间的联系完全通过网络进行，因此从 客户机和元数据服务器的角度上看，i o d 就是一个能够处理特定r e q 请求并返 回合适的a c k 响应数据的网络服务器，任何能够实现相同服务的实体替换这些 i o d 时，对于客户机和元数据服务器都是不可见的。同理，用相同功能的其它实 体替换客户机或元数据服务器也对另外的两种部件是不可见的。 6 硕士学位论文 图2 2 并行文件系统( p v f s ) 结构 2 3 并行地震数据处理技术 元数据 ，。一 e = = 爿 元数据 元数馆 地震勘探行业越来越广泛地采用大规模并行处理( m p p ) 系统解决数据处理 问题。地震作业最主要的是及时提交高质量的成果，成果的精度由算法的精度和 处理流程所决定，而时间则是由计算机的处理能力所决定。处理能力是指一定时 间内所完成的工作量。其两个重要的衡量指标是每小时处理道数和每节点小时 ( 一个节点是并行处理系统中的一个处理单元) 处理的道数。前者反映时钟时间， 后者反映完成工作所需的计算机资源。应当注意的是，处理能力不是处理周期， 处理周期是完成一个项目所需要的总时间。它可以通过充分发挥项目总许多处理 任务的效率而达到最优。 当我们把作业分配到更多的节点的时候，处理能力呈线性增长。但是，有一 个极限，当多余8 个节点后处理能力就不再提高，这是因为它达到了i o 带宽的上 限。此时再增加节点已经无济于事，因为新增加的节点不能调动更多的数据。但 是，可以将作业分解，使分解后的每个部分用8 个节点进行处理。这样6 4 个节点 的系统可以同时运行8 个作业，达到最大限度的利用m p p 节点处理能力的目的。 目前已经有五种基本的并行处理算法：空间共享，作业复制，流水线，主从 模式和以上各种方法的组合。以下将在一个3 2 个节点的m p p 系统上以实例说明每 种方法。实例图中的大写字母表示读带，叠加，绘图等作业，处理模块用小写字 母表示【1 3 1 卵。， 图2 3 是空间共享说明，它是并行处理的最简单的形式。每个作业在单个节 点上运行，每个节点只承担一项作业。每个作业独享一个c p u 和内存，但是和其 他作业竞争使用i 0 带宽。每个作业不依赖于其他任何作业进程。 7 旁 二务 一 一务 黼豫|丽螗11鬟器 数 = 赦 一 一数 地震数据处理中的并行计算技术研究 ae 。e日d 。zc q b a - dyc z ipr i hg fnos j k m lw vut 图2 3 空间共享实例 作业复制( 图2 4 ) 是在许多节点上同时运行相同作业，这样，同一个处理模块 形成的作业集同时处理不同的数据块。这要求每个输出数据子集仅依赖于各自的 输入数据子集。a 有3 2 份复制品，每个在不同的节点上运行，每个复制作业处理 不同数据子集。 a 1a 2a 3 a 4 a 5 a 6a 7a 日 a 9 a 1 0a 11a 1 2 a 1 3a 1 4a 1 5 a 1 6 a 1 7a 1 8a 1 9a 2 0a 2 1a 2 2a 2 3a 2 4 a 2 5a 2 6a 2 7a 2 日a 3 9a 3 0a 3 1a 3 2 图2 4 作业复制实例 流水线模型如图2 5 ( a ) 所示，输入输出和偏移作业模块分别运行在不同的节 点上整个流程构成一个流水线，流水也称为功能模块顺序分解：把不同功能模块 分配在不同处理机节点运行。这是最显而易见的。因为传统的地震处理过程总是 组织为一系列模块的“流程”，如果把这些模块分段放在不同处理机运行，就可 以构成流水方式。需要注意的是，一个作业被分割为不同的阶段，每个阶段包 括一个或多个顺序的模块，跨处理机分布。数据必须流经流水线的每个阶段。假 定我们有三个模块m 1 ，m 2 和m 3 ，分别在处理机p 1 ，p 2 和p 3 运行，需要的处理 机时间分别为t 1 ，t 2 和t 3 。可以看出，流程处理的第一个输出需要( t l + t 2 + t 3 ) 运 行时间，而在流水线充满后，其它输出需要的最长时间为流水段中的最长的时间 t m 。x 。理论上，如果不考虑处理机间通信的开销，获得1 1 个输出的并行加速比( 即 单处理机执行时间与多处理机执行时间之比) 为： 8 硕+ 学位论文 n v 磊 1 跏磐卷瓣。甄 其中，r m a x 是流水段中最长时间与总时间之比： r 一；tm 缸y 厶 一 对于处理输出循环很大的情况： ( 2 1 ) ( 2 2 ) s n = 0 0 暑y r 嗽r 2 3 1 即加速比依赖于最长流水段时间与总时间之比。 扇出扇入如图2 5 ( b ) 所示，偏移作业扇出为三份运行在三个不同的节点上， 扇出扇入模式，也称为克隆模式，克隆是复制一个模块，使它可以同时在许多 处理机运行。因此，我们可以有大量相同的模块对不同的数据工作。只有在模 块中确定读哪些数据的部分需要变化。这种设计模式的数据结构要求输出的子集 只依赖相应的输入子集。一般地讲，应用或作业的一部分是可以“克隆”的，而剩 余部分则必须在单一节点运行。我们称之为部分克隆。因此，必须从一个单处理 机扇出到“克隆”了的多个处理机，和从“克隆”了的多个处理机扇入回一个单处理 机。这里，每个节点接收的数据子集、所有模块同步运行，当处理完成时数据同 时输出。在一个处理循环中，如果一个模块m p 的计算量t p 特别大，采用流水方 式不可能获得高的加速比，这时可以利用克隆这个模块到m 个处理机的方法，其 理论上加速比为： 一撩。1 l _ m - l r p ( 2 4 ) 一西赫。 4 其中，r p 是克隆的模块运行时间占总时间的百分比，即 知 印丽 ( 2 5 ) 当处理机数较大时，系统可达到的理论加速比为： 1 鼬2 1 - r p ( 2 6 )一”， 某些包含数据结构太大的模块，不能放在单一节点存储器中，此时可采用扇 出扇入模型并行，如f k 域偏移和滤波等模块。 主从模式如图2 5 ( c ) 所示，作为例子，主节点从磁带或磁盘读输入道，并确 定输入道应该映射到的面元，传送输入道到该面元对应的从节点，然后读下一个 输入道等。这样，从节点在其输入满足后，开始计算，在计算完成后通知主节点， 并等待来自主节点的新输入。需要采用主从方式的模块是计算量大的模块，例如 k i r c h h o f f 偏移、d m o 和d m o 速度分析等模块。在d m o 情形下，每个节点使用全 部数据，计算输出道的子集。在d m o 速度分析的情形，每个节点使用所有数据， 计算速度扫描图的子集。 9 地震数据处理中的并行计算技术研究 输入 l 偏移 输出 a 流水线 2 4 并行算法的设计 日扇入，翕出 c 主从模式 图2 5 三种复杂的并行计算模型 2 4 1 设计原则 并行算法是并行计算的基础，与实现技术相结合，为高效率使用并行计算机 提供解决方案【1 , 2 1 。其基本原则简述如下： 1 并行算法与体系结构相结合，可以分为线性结构、维网格结构和超立方体 结构，如图2 6 ： 一，一 、，、厂 、厂 、厂 、一 一， 、厂 、厂 、厂、，、厂 一，一， 一， 、厂 、厂 、厂、，、厂 、 、厂 、，、厂 一，一，一， l厂 、厂 、厂、厂 、一 图2 6 并行算法结构 2 具有可扩展性：并行算法是否是随处理机个数增加而能够线性或近似线 性的加速，这是评价一个并行算法是否有效的重要标志之一。也就是说，如果一 个并行算法的加速比是s p ( q ) 一d ( q ) 或是s p ( g ) 一o ( q ( 1 + l o g ( q ) ) ) ，则可以称为具有 可扩展性的并行算法。 3 粗粒度：通常情况下，粒度越大越好。这是因为在每个处理机中有很多 需要计算的工作任务，如此可以充分发挥多处理机的作用。并行加速比对细粒度 问题一般情况下是不会很高的，这也是为什么并行计算需要求解大规模问题的原 1 0 囚囚 硕士学位论文 因所在。 4 减少通信：一个高效率的并行算法，通信是至关重要的。提高性能的关 键是减少通信量和通信次数，其中通信次数通常情况下是决定因素。 5 优化性能：一个算法是否有效，不仅依赖于理论分析的结果，也和在实 现的过程中采用的技术息息相关。性能主要看单处理机能够发挥计算能力的百分 比，然后是并行效率。影响并行算法效率的因素可能很多，但是这里所给出的几 条是主要因素。因此，在算法设计的过程中，如果能够将上述5 条加以仔细考 虑，就能够取得非常好的效果。 2 4 2 性能评价 大多数高性能现代计算机展示了并发性( c o n c u r r e n c y ) ，例如多处理是一种在 作业级或程序级达到并发性的方法，而指令预 驭( i n s t r u c t i o np r e f e t c h ) 是一种在指 令级达到并发性的方法。然而把每一种现代计算机均称为并行机是不恰当的，许 多机器的并发性对用户是不可见的。因此，在文献 1 6 1 9 采用下面的一些定义： 并行处理( p a r a l l e lp r o c e s s i n g ) ：并行处理是信息处理的一种有效形式，它强 调对数据元素的并发操作，这些数据元素属于解决一个单一问题的一个或多个进 程。 并行性主要是指同时性或并发性，并行处理是指对一种相对于串行处理的处 理方式，它着重开发计算过程中存在的并发事件。并行性通常划分为作业级、任 务级、例行程序或子程序级、循环、迭代级、语句和指令级。作业级的层次高， 并行处理粒度粗。粗粒度并行性开发主要采用m i m d 方式，而细粒度并行性开 发则主要采用s i m d 方式。开发计算机并行性的方法主要有：资源重复、时间重 叠和资源共享三种方法。 粒度：是各个处理机可独立并行执行的任务大小的度量。大粒度反映可并行 执行的运算量大，亦称为粗粒度。指令级并行等则是小粒度并行，亦称为细粒度。 加速比：串行执行时间为t s ，使用q 个处理机并行执行的时间为t p ( q ) ，则 加速比s p ( q ) 为： & ( q 卜蠡 ( 2 。7 ) 计算速度：求一个问题的计算量为，执行时间为z ，在8 0 年代采用f l o p s 作为计算速度单位；在9 0 年代使用m f l o p s 和g f l o p s ；在2 1 世纪普遍使用 g f l o p s 和刀咒d p 肛，目前也逐渐开始使用p f l o p s 。 州- 了w ( 2 8 ) 吞吐量( t h r o u g h p u t ) ：单位时间产生结果的数量。可以有许多方法改进吞吐 量，如何提高操作速度，增加并发性等。 1 1 地震数据处理中的并行计算技术研究 数据并行( d a t ap a r a l l e l i s m ) ：使用多个功能部件把同一操作同时应用到数据 集的元素上。如果没有增加与并行性相关的开销，则功能部件增加k 倍，系统 的吞吐量也增加k 倍。 a m d a h l 定律：在许多实时应用领域，计算负载的大小常固定。在并行机中， 此负载可分布至多台并行执行，获得加速比称为f i x e d 1 0 a ds p e e d u p 。问题规模不 随处理机变化而变化，而是看用并行技术能达到的最短时间是多少。一个问题的 负载可表示如下： w = w s + ( 2 9 ) 其中，职代表问题中不可并行化的串行部分负载，表示可并行化的部分 负载。在咒个节点情况下，加速比可以表示如下： + s n 。蒜 ( 2 - o ) 设串行因子口为串行部分所占的比例。代入即得a m d a h l 定律： 跏竺乎t 矗布 仁j