（计算机应用技术专业论文）基于pc机群的矩阵相乘并行算法研究.pdf

桂林工学院硕士学位论文 摘要 机群系统目前已经成为高性能计算机的发展方向，而p c 机群因为自身的优势，获得 高校和科研机构的青睐，越来越多的并行问题的研究在p c 机群上进行。并行矩阵乘法是 解决大数据量矩阵乘法耗时过久的有效途径，而在p c 机群上进行并行矩阵乘法更是一种 性价比较高的方案。本文介绍了并行计算的基本理论、概念，并对p v m 并行编程环境进行 了分析；组建了p c 机群，并在机群上建立了基于p v m 的并行计算环境。对在该并行环境下 并行程序的设计原则、设计方法、编译、执行等问题进行了探讨，并在该环境下实现了 多种基于带状划分法和棋盘划分法的矩阵并行乘法 当前矩阵并行乘法多是基于s i 如( s i n g l ei n s t r u c t i o ns t r e a mm u l t i p l ed a t a s t r e a m ) 、m i m d ( m u l t i p l ei n s t r u c t i o ns t r e a mm u l t i p l ed a t as t r e a m ) 等并行计算机 的。而本文是在p c 机群上设计实现了属于上述两种划分方法的行列划分法、简单分块法、 c a n n o n 算法、f o x 算法、d n s 算法等矩阵并行算法。在算法实现中讨论并解决了矩阵的 不能均匀划分问题；实现了机群节点间一维的逻辑关系到二维、三维逻辑关系的映射， 减小了程序设计的难度，优化了程序设计。并对上述诸算法做了改进。改进主要在两个 方面，即提高任务间通信速度和加快数据计算；提高任务间通信速度是通过在机群上任 务间建立直接t c p 联接来实现：而加快数据计算是通过引入w i n o g r a d 算法，来减少各并行 任务的乘法执行次数来实现。 对各算法的测试，采用同一组数据，分不同的粒度在不同个数的节点上进行。根据 测得的实验数据，改进后的各算法性能较改进前均有了较大提高。四节点上各算法加速 比与效率均提高2 0 以上，九节点上加速比与效率均提高1 0 以上。并通过并行度、存储 有效性、加速比、效率、通信量等方面对在机群上实现的各种矩阵并行乘法进行了分析、 比较。对在实际应用中该选择何种方法，应注意的问题给出了一些建议。最后给出了一 些关于在p c 机群上进行大规模数据并行计算的一些有意义的结论。 关键字：机群系统，并行矩阵乘法，t c p 联接，性能评价 桂林工学院硕士学位论文 a b s t r a c t n o w a d a y sc l u s t e rs y s t e m sh a v eb e c o m et h ed e v e l o p m e n tt r e n do fh i g h p e r f o r m a n c ec o m p u t e r m e a n w h i l e ，t h ep cc l u s t e r s ，d u et oi t so w ns u p e r i o r i t y ， h a v eo b t a i n e dt h ef a v o ro fu n i v e r s i t i e sa n ds c i e n t i f i cr e s e a r c hi n s t i t u t i o n s m o r ea n dm o r ep a r a ll e lc o m p u t i n gr e s e a r c hh a sb e e nc a r r i e do nt h ep cc l u s t e r s t h ep a r a l l e lm a t r i xm u l t i p l i c a t i o ni sa ne f f e c t i r ew a yt os o l v et h et i m e c o n s u m i n gp r o b l e m so fl a r g e s c a l em a t r i xm u l t i p l i c a t i o n e s p e c i a l l y ，i fc a r r i e d o nt h ep cc l u s t e r s i tw i l lb eo fh i g h e rp e r f o r m a n c e - t o p r i c er a t i o t h i s d i s s e r t a t i o nf i r s ti n t r o d u c e dt h ee l e m e n t a r yt h e o r i e sa n dc o n c e p t so ft h e p a r a l l e lc o m p u t a t i o n ，t h e na n a l y z e dt h e p v m p a r a l l e lp r o g r a n h n i n g e n v i r o n m e n t ， a f t e rt h a te s t a b l i s h e dt h ep cc l u s t e ra n dt h ep v mp a r a l l e l c o m p u t a t i o ne n v i r o n m e n t ，t h e nd i s c u s s e dt h ed e s i g np r i n c i p l e ，t h ed e s i g nm e t h o d ， t h ec o m p i l a t i o na n dt h ee x e c u t i o no ft h ep a r a l l e lp r o g r a m su n d e rt h i se n v i r o n m e n t a n da tl a s t ，b a s e do nt h es t r i p e dp a r t i t i o n i n ga n dt h ec h e c k e rb o a r dp a r t i t i o n i n g m e t h o d ，r e a l i z e dt h em a t r i xp a r a l l e lm u l t i p l i c a t i o n t o d a y ，t h ep a r a l l e lm u l t i p l i c a t i o na l g o r i t h m sa r em o s t l yd e s i g n e df o r p a r a l l e lm a c h i n el i k es i m d ( s i n g l ei n s t r u c t i o ns t r e a mm u l t i p l ed a t as t r e a m ) a n d m i m d ( m u l t i p l ei n s t r u c t i o ns t r e a mm u l t i p l ed a t as t r e a m ) h o w e v e r 。i nt h i s d i s s e r t a t i o n ，v a r i o u sa l g o r i t h m ss u c ha sl i n e r o wd i v i s i o na l g o r i t h m ，s i m p l e p i e c e m e a la l g o r i t h m ，c a n n o n sa l g o r i t h m , f o x sa l g o r i t h m , d n sa l g o r i t h ma r e r e a l i z e do np cc l u s t e r sb a s e do nt h ea b o v em e n t i o n e dp a r t i t i o n i n gm e t h o d s i n t h ea l g o r i t h m s ，t h ep r o b l e ma sh o wt od i v i d em a t r i xe v e n l ya r er e s o l v e da n dt h e l o g i c a lr e l a t i o nm a p p i n gf r o mo n ed i m e n s i o nt ot w od i m e n s i o n sa n dt h r e ed i m e n s i o n s b e t w e e np cc l u s t e rn o d e sa r ei m p l e m e n t e d a n dt h u st h ed i f f i c u l t yo fp r o g r a m m i n g d e s i g n w a sg r e a t l yr e d u c e d t h e nt h ei m p r o v e m e n ti ns p e e d i n gu pd a t a c o m m u n i c a t i o na n dd a t ac o m p u t a t i o nw a sm a d et ot h et h o s ea l g o r i t h m s d a t a c o m m u n i c a t i o ni ss p e e d e du pb yd i r e c t l ye s t a b l i s h i n gt c p1 i n kb e t w e e nt a s k so n t h ep cc l u s t e r sw h i l ed a t ac o m p u t a t i o ni ss p e e d e du pb yu s i n gt h ew i n o g r a d a l g o r i t h mt or e d u c et h et i m e so fm a l t i p l i c a t i o ni ne a c hp a r a l l e lt a s k t h et e s t sf o rt h e s ea l g o r i t h m sa r ec a r r i e do np cc l u s t e r so fd i f f e r e n tn o d e s r e s p e c t i v e l yb yu s i n gt h es a m ed a t ai nv a r i o u sg r a n u l a r i t y a st h ee x p e r i m e n t a l d a t as h o w s ，t h ep e r f o r m a n c eo ft h e s ei m p r o v e da l g o r i t h m sh a sb e e n e n h a n c e dg r e a t l y t h ea c c e l e r a t i o nr a t i oa n dt h ee f f i c i e n c yh a sb e e ni m p r o v e da b o v e2 0 i nf o u r n o d e sa n da b o v e1 0 i nn i n en o d e s b ya n a l y z i n ga n dc o m p a r i n gt h ep a r a l l e ld e g r e e ， t h em e m o r ys i z e ，t h ea c c e l e r a t i o nr a t i o ，t h ee f f i c i e n c y ，t h ec o m m u n i c a t i o na n d s oo n， s u g g e s t i o n sa s h o wt oc h o o s et h ec o r r e c tm e t h o d sa n dw h a tq u e s t i o n t op a ya t t e n t i o nt oa r eg i v e nf o rt h ea p p l i c a t i o n f i n a l l y ，c o n c l u s i o n sa b o u t l a r g e - s c a l e p a r a l l e lc o m p u t a t i o no nt h e p cc l u s t e r sw a sg i v e n k e y w o r d = p cc l u s t e r s ，p a r a l l e lm a t r i xm u l t i p l i c a t i o n ，t c pl i n k ， p e r f o r m a n c ee v a l u a t i o n 玎 桂林工学院硕士学位论文 研究生学位论文独创性声明和版权使用授权说明 独创性声明 本人声明：所呈交的论文是我个人在刘羽副教授指导下进行的研究工作及取 得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包 含他人已经发表或撰写过的研究成果，也不包含为获得桂林工学院或其它教育机 构的学位或证书而使用过的材料对论文的完成提供过帮助的有关人员已在论文 中作了明确的说明并致以了谢意 学位论文作者( 签字) ：磊) 叠室 签字日期：本厶f f 版权使用授权说明 本人完全了解桂林工学院关于收集、保存、使用学位论文的规定，即：按照 学校要求提交学位论文的印刷本和电子版本；学校有权保存学位论文的印刷本和 电子版，并提供目录检索与阅览服务；学校可以采用影印、缩印、数字化或其它 复制手段保存论文；在不以赢利为目的前提下，学校可以公布论文的部分或全部 内容。( 保密论文在解密后遵守此规定) 学位论文作者( 签字) ：叠! 虱之 指导教师签字： j ! i 碰l 签字日期： 毖：数：之：! ! 桂林工学院硕士学位论文 1 1 本文研究的背景及意义 第1 章绪论 自2 0 世纪9 0 年代后，i t 界、大学、科研机构、企业界逐渐掀起了发展机群技术的 热潮，目前机群作为一项成熟技术，已得到了广泛的应用，并将具有长远的生命力。在 科学和工程计算中矩阵运算特别是矩阵相乘是最基本的运算之一，广泛应用于图像处理、 最短路径求解、遗传学、密码学、电力网和经济学等领域。矩阵运算可分为稀疏矩阵的 运算和稠密矩阵的运算；算法可分为串行和并行两类；串行算法在实现上有行优先和列 优先两种实现形式在大规模矩阵运算中矩阵的阶都很高( 元素很多) ，但处理机的计算 速度受到物理上的限制，不可能无限制的提高；因此大规模的矩阵运算在单机上运行时 往往要花费较长时间或无法完成。所以，创建和使用并行计算机将矩阵乘法并行化，就 成为解决单处理器速度瓶颈的最好方法之一现在多数矩阵相乘的并行算法是在s m p 、 m p p 、d s m 等大型机上实现，但上述类型的超级计算机在目前情况下很难广泛分布到一般 高校和科研机构。而机群系统，因其廉价、开放、高效、高性价比等特点，被高校和科 研机构接受；将来会有越来越多的并行算法被移植到机群上实现。因此在机群上对矩阵 相乘并行算法做一些有益的实践是有意义的。 1 2 本论文的主要工作 本文研究了在p c 机群环境中实现并行距阵乘法的相关问题。 论文首先研究利用现有计算机资源，组建小型的机群系统，建立了基于l i n u x 和p i m 的并行实验环境。在此基础上，介绍了开发p 、，m 并行程序的过程，并行程序编译与运行 的几种方法。并根据不同矩阵并行乘法的特点，设计实现了基于p v a 的各种矩阵并行乘 法；并且在并行实验环境中对各算法进行了测试，对其中的某些算法做出了改进。 本论文所做的研究和探索，主要包括以下工作： 第一，讨论并行计算机的体系结构，建立了基于l i n u x 和p v m 的机群并行实验环境； 给构建p c 机群提供了借鉴。 第二，研究了消息传递模式下影响并行程序性能的因素，通过编写测试程序，测试 了机群上节点间的数据传递速度：分析了打解包方式对数据传输的影响；并通过在程序 桂林工学院硕士学位论文 中建立直接t c p 通讯的方式，大大提高了数据通信速度。 第三，分析了机群系统并行程序设计模型，讨论了p v m 程序设计的基本模式、方法 和设计原则，以及在p v m 机群环境下开发并行程序的框架和过程。分析和给出了并行程 序编译和运行的几种不同方法。 第四，在自行建立的并行实验平台上，编程实现了基于带状划分和棋盘划分法的行 列划分算法、简单分块算法、c a n n o n 算法、f o x 、算法、d n s 算法。并通过提高任务间通 信速度和减少计算量两方面，对除d n s 外的算法进行了改进；对改进前后的各算法利用 同一组数据进行了测试。 第五，在程序设计中解决了矩阵不能均匀划分问题；完成了机群节点一维总线逻辑 结构( 或称为星形结构) n - - 维网状逻辑结构和三维超立方逻辑结构的映射；在矩阵块 间的乘法运算中引入w i n o g r a d 算法来减少乘法运算次数，提高算法性能 最后，根据理论研究和测试的结果，从并行度、加速比、效率、存储有效性、通信 量等方面对各种并行算法进行了分析、比较，得出一些有意义的结论，以及进一步改进 的思路 2 桂林工学院硕士学位论文 第2 章并行计算基础 并行计算是提高计算机系统计算速度和处理能力的一种有效手段。它的基本思想是 用多个处理器来协同求解同一问题，即将被求解的问题分解成若干个部分，各部分均由 一个独立的处理机来计算。并行计算系统既可以是专门设计的、含有多个处理器的超级 计算机，也可以是以某种方式互连的若干台独立计算机构成的机群。 并行计算基于一个简单的想法：n 台计算机应该能够提供n 倍的计算能力，不论当前 计算机的速度如何，都可以期望被求解的问题将在1 n 的时间内完成。显然这只是一个 理想的情况，因为被求解的问题在通常情况下都不可能被分解为完全独立的各个部分， 而是需要进行必要的数据交换和同步。尽管如此，并行计算仍然可以使整个计算机系统 的性能得到实质性的改进，而改进的程度取决于欲求解问题自身的并行程度。 2 1 并行计算的目标 目标：求解大规模问题和复杂系统。早期并行计算以加速求解问题为目的，这来源 予单处理机的计算速度受到物理上的限制，光速是其上限。随着计算在科学研究和实际 应用中发挥越来越大的作用，人们对计算已经产生了依赖，将数值模拟作为许多决策的 依据。现在人们已经习惯将计算作为科学研究的第三种手段，和传统的科学研究的理论 方法和实验方法并列。 并行计算的优点是具有巨大的数值计算和数据处理能力，能够被广泛地应用于国民 经济、国防建设和科技发展中具有深远影响的重大课题，如石油勘探、地震预测和预报、 气候模拟和大范围天气预报、新型武器设计、核武器系统的研究模拟、航空航天飞行器、 卫星图像处理、天体和地球科学、实时电影动画系统及虚拟现实系统等等。 目前，并行计算已经成为计算机科学研究和应用中的热点，各种并行计算系统层出 不穷，其中发展最快的当数基于l i n u x 平台的机群并行计算环境。 2 2 并行计算机的分类 随着并行处理技术的发展，并行机种类繁多。并行计算机常用的一种分类法为f l y n n 分类法，它是按照指令与数据流来分类；按f l y n n 分类法“”并行机可分为： 单指令多数据流( s i m d ) ：按同一条指令，并行机的各个不同的功能部件同时对不同 的数据进行不同的处理，例如：传统的向量机、8 0 年代初期的阵列机c m 一2 ，目前已经退 出历史舞台 多指令单数据流( m i s d ) ；至今没出现。 3 桂林工学院硕士学位论文 多指令多数据流( m i m d ) ：不同的处理器可同时对不同的数据执行不同的指令，目前 所有并行机均属于这一类；主要包括：对称多处理共享存储并行机( s m p ：s y m m e t r i c m u l t i p r o c e s s i n g ) ；分布共享存储并行机( d s m ：d i s t r i b u t e ds h a r e dm e m o r y ) ；大规模 并行机( m p p ：m a s s i v e l yp a r a l l e lp r o c e s s o r s ) ：工作站( 微机) 机群( c o w ：c l u s t e r o fw o r k s t a t i o n 、b e o w u l fp c - c l u s t e r ) ；并行向量多处理机( p v p = p a r a l l e lv e c t o r p r o c e s s o r s ) 。 2 3 并行计算机的体系结构 并行计算机体系结构“”是指并行处理系统( 主要是分布式系统) 中处理机或节 点机之间的互连方式，它直接影响并行算法的实现效率。也对并行算法的设计与分析有 影响。本节将简单介绍当前并行机主要采用的体系结构 ( 1 ) 总线结构 总线结构常出现于机群系统中它的处理机连接方式如图2 1 所示。 总线结构中各处理机共享同一条物理线路，同一时刻只允许由一个处理机发送消息， 当有多个处理机同时发送消息时，将使用仲裁机制决定消息发送顺序，从而导致通信开 销的增大。 图2 1 总线结构 ( 2 ) 网格结构 网格结构，即二维阵列结构，可分为环绕连接和无环绕连接两种方式。 无环绕连接网格结构如图2 2 所示。所有处理机按二维阵列方式排列，每一处理机 仅与其相邻处理器相联。这种结构特别适合于处理二维f 司题。 一一图2 2 二维阵列结构图2 3 三维超立方体结构 4 桂林工学院硕士学位论文 ( 3 ) 超立方体结构 n = 2 4 个节点可构成一个q 维超立方体。若用q 位二进制数a ”a ”a 0 对节点进行编号， 则超立方体结构中两个节点相联的充分必要条件是节点的编号有且仅有一位不同，每个 节点与q 个节点相连，所有节点的度为q ，图2 - 3 所示为3 维超立方体结构。 除上述总线、网格、超立方体结构之外，还存在树结构、树网结构、洗牌交换网结 构、蝶形结构等处理机连接方式。在这些处理机连接方式中网格结构应用较为广泛 2 4 并行算法的基本概念与分类 ( 1 ) 基本概念 并行算法；是一些可同时执行的主进程的集合，这些进程互相作用和协调动作，从 而达到对给定问题的求解。 性能：求解一个问题的计算量为w ，执行时间为t ，则性能( f l o p s ) 为p e r f = w t 在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 和t f l o p s ，目前也逐渐开始使用p f l o p s 粒度：是各个处理机可独立并行执行的任务大小的度量。大粒度反映可并行执行的 运算量大，亦称为粗粒度。指令级并行等则是小粒度并行，亦称为细粒度。 ( 2 ) 并行算法的分类 并行算法可以从不同角度加以分类，按研究内容的所属范畴，可以分为数值并行算 法和非数值并行算法；按并行算法中的进程间的同步方式可以分为同步算法、异步算法 和分布式算法；按并行算法在不同的并行机上实现可分为s i m d 机上的并行算法、m i m d 机 上的并行算法、v l s i 机上的并行算法。 2 5 并行计算模型 所谓计算模型就是硬件和软件之间的一种桥梁，使用它能够设计分析算法。并行计 算模型( 也称为编程模型、类型性模型、概念性模型或理想化模型) 是指将各种并行机( 至 少是某一类并行机) 的基本特征抽取出来，形成一个处于具体并行机之上的抽象并行计算 机。在串行计算时，冯诺依曼机就是一个理想的串行计算模型，在此模型上硬件设计者 可以设计多种多样的冯诺依曼机而无需考虑被执行的硬件，而软件开发者可以编写各种 在此模型上有效执行的程序而无需考虑所使用的硬件。但在并行计算时，尚未有一个类 似于冯诺依曼机的真正通用的并行计算模型。迄今为止，己经有多种并行计算模型存在， 如p r a m 模型、l o g p 模型、c 3 模型、b s p 模型、b d m 模型等，但其中的每一种只抽象了实 际并行机的一个或几个方面，尚无一种适用于所有并行机。 5 桂林工学院硕士学位论文 由于本文基于分布式系统研究并行算法，因此根据上述各模型特点，本文选用l o g p 模型作为_ 并行算法设计与分析的依据。下面对l o g p 模型及其扩展模型进行详细阐述。 l o g p 是一种分布存储的、点到点通信的多处理机模型，其中通信网络由一组参数来 描述。但它并不涉及到具体的网络结构。 l 表示在网络中消息从源到目的地所遭到的延迟； 0 表示处理器发送或接收一条消息所需的额外开销( 包含操作系统核心开销和网络 软件开销) ，在此期间它不能进行其他的操作； g 表示处理器可连续进行消息发送或接收的最小时问问隔； p 表示处理器存储器模块数 l o g p 模型的特点如下： 其中的三个参数比较准确地描述了分布式存储互连网络的特征，抓住了网络 与处理机之间的性能瓶颈。 处理机之间异步工作并通过处理机间的消息传送来完成同步。 消息延迟不确定，但延迟不大于l 鼓励编程人员采用一些好的策略，如作业分配，计算与通信重叠以及平衡的 通信模式( 不会出现大量消息同时涌入某个处理机) 等。 可根据参数分析算法的通信复杂度，预估算法的实际运行时间。 l o g p 模型适用于短消息的消息发送由于现代许多并行机均支持长消息的发送，放 l o g p 模型已不能满足需要。为此，a a l e a n d r o v 等人推广了l o g p 模型，得到了l o g g p t m j 模型。l o g g p 模型将长消息结合到l o g p 模型中。 2 6 并行算法设计策略与基本设计技术 ( 1 ) 并行算法设计策略 设计并行算法一般有三种策略： 检测和开拓现有的串行算法中的固有并行性而直接将其并行化，对很多问题此方 法有效； 从问题本身的描述出发，根据问题固有的属性，从头开始设计一个全新的并行算 法，虽此法有难度，但所设计的算法往往很高效； 借用已有的并行算法使之可以求解新的一类问题，这种属于难度较大的方法，对 初学者较难。 人类长期以来积累了很多优秀的串行算法，我们在设计并行算法的时候要充分利用 它们，尽量在其基础上直接并行化，这是我们在设计并行算法时的一种最先考虑的方法。 但是对于一类具有内在顺序性的串行算法则很难直接并行化：且并非任何优秀的串行算 6 桂林工学院硕士学位论文 法都可以产生很好的并行算法，或许一个不好的串行算法反而能产生好的并行算法。 ( 2 ) 并行算法基本设计技术 并行算法设计技术尽管理论上不是很成熟，带有一定的技巧性，但也不是无章可循。 经过多年的发展，已经总结出了一些基本的、带有普适性的并行算法设计技术。归纳起 来有：划分法( p a r t i t i o n i n g ) 是设计并行算法最自然朴素的方法，系将一个计算任务 分解成若干个规模大致相等的子任务而并行求解；流水线法( p i p e l i n i n g ) 是一种基于 空间并行和时间重叠的问题求解技术，是并行处理技术中普遍使用的方法；分治法 ( d i v i d e - a n d c o n q u e r ) 是求解大型问题的一种策略，系将一个大而难的问题，逐次化 为一些小规模可求解的子问题而递归求解；随机法( r a n d o m i z a t i o n ) 是一种不确定性 算法，在算法设计步中引入随机性，从而可望得到平均性能良好、设计简单的并行算法； 平衡树法( b a l a n c e dt r e e ) 、倍增法( d o u b l i n g ) 和破对称法( s y m m e t r yb r e a k i n g ) 等都是针对待求解问题本身的特点而采用的一些有效设计方法；迭代法( i t e r a t i o n ) 是 求解诸如线性方程组之类闯题的常用数值求解方法。 2 7 并行算法的性能评价 并行计算的性能评测大致可分为机器级、算法级、程序级在这里我们主要讨论算 法级的性能评测。算法级的性能评测主要包括加速比、效率、和可扩放性等“1 “ ( 1 ) 加速比 加速比是衡量并行算法性能的一个重要指标，它定量地描述了在对一个串行程序实 现并行化过程中过程中，由于执行时间的减少而获得性能。是对并行算法的并行化成度 的一种通用的度量。 加速比：串行执行时闻为t s ，使用q 个处理机并行执行的时间为t p ( q ) ，则加速比 为 s p ( q ) = t s t p ( q ) ( 2 ) 效率 一个并行算法有好的加速比并不能说明处理器的利用效率，所以引入算法效率的概 念，作为评价算法性能的一个指标。 效率：设q 个处理机的加速比为s p ( q ) ，则并行算法的效率为 e p ( q ) = s p ( q ) q 它度量了每个处理器有效使用部分占总的执行时间的百分比 ( 3 ) 可扩展性 可扩展性是并行算法在多大程度上能有效利用增加的多处理机的能力的一个量度。 随着处理机的增加，如果效率浊线基本保持不变，或者略有下降，则称该算法在所有并 7 桂林工学院硕士学位论文 行机上可扩展性好；如果效率曲线下降很快则称可扩展性差。 影响一个并行算法的可扩展性因素很多，如计算方法、粒度、加速比、效率、并行 系统与通信开销等，评判的准则也不尽相同。可扩展性目前成为并行计算研究的一个活 跃方向。 8 桂林工学院硕士学位论文 第3 章p c 机群搭建与p v m 并行编程环境 3 1p c 机群系统 机群“删是上世纪九十年代发展起来的高性能计算机体系结构，它将有长远的生命 力。目前p c 机群越来越得到用户的青睐，主要有以下方面的原因：性能价格比高、结构 灵活，技术更新快、存储容量大等。以前超级计算机主要用在科学研究，大规模数据计 算等领域；如：石油、矿产勘探、气象资料处理、军事等。自上世纪末以来在i n t e r n e t 网络处理，数据库、事务处理，e r p 、c r m 、电子商务等领域开始得到广泛应用。自2 0 世 纪9 0 年代后，i t 界、大学、科研机构、企业界逐渐掀起了发展机群技术的热潮。 机群系统是利用高速通用网络将一组高性能工作站或高档p c 机，按某种结构连接起 来，在并行程序设计以及可视化人机交互集成开发环境支持下，统一调度，协调处理， 实现高效并行处理的系统。从结构和结点间的通信方式来看，它属于分布存储系统。机 群系统中的主机和网络可以是同构的，也可以是异构的。 机群系统之所以能够从技术可能发展到实际应用，主要原因是它与传统的并行处理 系统相比有以下几个明显的特点： ( 1 ) 系统开发周期短。由于机群系统大多采用商用工作站或高档p c 机和通用l a n 网 络，节省了大量的研制时间。 ( 2 ) 系统价格低。构成机群的工作站或高档p c 机是批量生产的，因而售价较低。 ( 3 ) 用户投资风险小。机群系统不仅是一个并行处理系统，它的每个结点同时也是一 台独立的工作站，即使整个系统对某些应用问题并行效率不高，它的结点仍然可以作为 单个工作站使用。 “) 系统扩展性好。机群系统大多使用通用网络，系统扩展容易。 ( 5 ) 节约系统资源。由于机群系统的结构比较灵活，可以将不同体系结构，不同性能 的工作站连在一起，这样就可以充分利用现有设备。 。 ( 6 ) 用户编程方便。机群系统中，程序的并行化还是在用户熟悉的编程环境c 、c + + 或f o r t r a n 下实现的。 总之，随着网络技术的发展和对机群系统研究的深入，特别是高效通信机制的开发， 机群系统的通信性能将会接近专用的互联网络，并行编程环境和工具更加完善，有望在 机群系统上解决粒度更细的应用问题，使并行处理系统的应用领域更加广泛。 典型的机群系统结构如图3 - 1 所示 9 桂林工学院硕士学位论文 图3 - 1 机群系统结构图 3 2 机群系统中的网络通信问题 机群并行计算机系统中各个独立的计算机的性能已经不是问题了，机群并行计算技 术的一个关键问题是互联网络的效率问题。机群并行计算机系统进行并行计算时，各个 计算机需要通过互联网络进行大量的通信和同步操作。 例如在网络拓扑结构为总线结构的机群并行计算机系统中，当系统中任意两台计算 机互相通信的时候，由于它们相互通信时占用了系统的总线，因此系统中其它计算机之 间的通信会受到影响。这说明总线结构的互联网络的效率很低，将使通信发生阻塞，延 长并行处理时间，降低加速比，影响机群并行计算机系统的效率。类似的，在其他网络 拓扑结构的机群并行计算机系统中，也有上述问题。由此可见，网络通信是机群并行计 算系统中的一个瓶颈。 目前，机群并行计算机系统的互联网络主要以计算机局域网络为主，例如e t h e r n e t 、 t o k e n r i n g 等，也有一些系统使用了f d d i 、a t m 等高速网络。但是所有这些网络都具有顺 序通信的特点，不能很好的解决网络瓶颈问题 为了解决通信瓶颈问题，机群并行计算系统需要满足如下要求的高速通信网络： 高传输率。网络传输率是指网络每秒钟传输的数据量，以b p s 为单位，网络的传 输率和通信延迟是引起通信瓶颈的关键因素。为了提高传输率可以尽可能的提高网络带 宽，用交换机取代集线器。以太网集线器与交换机的最大区别在于交换机的每个端口都 是自身的逻辑划分。一台连接到交换机某一端口的单独计算机享有全部带宽，不需要和 其他计算机竞争，从而避免冲突。另外交换机具有地址处理能力，交换机读取每个数据 包文中的地址信息，并正确地将数据传往下一个接收者；集线器并不关心数据报文中的 地址信息，只把数据发往网络中所有设备。如果交换机没有正确的读取报文的地址和传 输数据的能力，它就不比集线器优越。表3 - 1 列出了集线器与交换机的主要区别 桂林工学院硕士学位论文 表3 - 1 以太网集线器与交换机的主要区别 集线器 交换机 网络总带宽取决于集线器的速度，也就是网络总带宽取决于交换机上的端口树木，也就 说无论他有多少端口，一个1 0 b a s e - t 集线 是说，有1 2 个端口的交换机能提供高达 器只能提供1 0 1 r i b 的带宽 1 2 0 0 1 v l b p s 的带宽，当然这是指交换机的总计最 大带宽 支持半双工通信，从而限制了端口连接速支持全双工通信，从而使每个连接的速度加倍， 度，1 0 1 r i b 端口仅提供1 0 m b 的连接。即可以达到1 0 0 1 r i b 到2 0 0 m b 的速度。 条步数规则限制了两台计算机问能连接的允许用户扩充网络。两台计算机间能连接的交 集线器数目。换机数目没有限制。 比交换机便宜比集线其稍贵 现在，国外一些厂商开发了专用硬件作为集群并行计算系统的互联网络。 低通信延迟单纯提高网络传输率，并不能解决集群并行计算系统的通行瓶颈问 题，还要降低通信延迟通信延迟主要由节点及发送和接收数据的软件开销决定，该开 销主要是数据的打包解包过程。在3 3 2 节中将进行详细讨论。 3 3p v m 并行编程环境 p v m 是一个在网络上的虚拟并行机系统的软件包。它允许将网络上基于u n i x 几i n u x 操作系统的并行机和单处理机的集合当成一台单一的“并行虚拟机”来使用。 3 3 1w _ 的结构、功能与特点 ( 1 ) p v m 的产生和发展 p v m ”删的开发最早开始于1 9 8 9 年夏天，目前它的开发队伍包括美国橡树岭国家实验 室( o r n l ) 、t e n n e s s e e 大学、e m e r y 大学以及伽等单位，并得到美国能源部、国家科 学基金以及田纳西州的资助。p v m 是一套并行计算工具软件，支持多种体系结构的计算机， 象工作站、并行机以及向量机等，通过网络将它们连起来，给用户提供一个功能强大的 分布存储计算机系统。p v m 支持c 和f o r t r a n 两种语言，目前已发展到3 4 版，由于它是 免费的，因此使用范围非常广泛。 p v m 软件系统允许把用异构网连接起来的串行和并行计算机用作一个统一的并发计 算资源( 并行机) p v m 系统支持消息传递编程模型，从而允许应用在整个过程中或某个 子过程中使用最合适的计算模型；处理单元( 或结点机) 可以是标量机、共享存储器型 多处理机、分布式存储器型多处理机、专用的图形引擎( e n g i n e ) 等，从而允许应用的 每个组成部分使用最适合的计算资源。这些特点对于象全球环境模型、流体力学仿真和 气象预报类的大型计算应用系统特别有实用价值。 桂林工学院硕士学位论文 ( 2 ) p v m 结构分析 一个完整的p 系统由三部分组成：p v m 守护进程( p d ) ，p w l 接口库和p w 监控 台进程。p v m 守护进程是整个p v m 的核心。它驻留在构成虚拟机的每台实际计算机上，完 成整个虚拟机的维护、任务的控制、消息的传递等工作。p v m 接口库里面包含了用户可调 用的p v m 库函数，如消息传递、任务创建、任务间协作同步及虚拟机的动态配置等，所 有p v m 应用程序都必须和该库相连。p v m 监控台则作为一个特殊的p v m 任务提供一个处理 机管理、任务管理等的交互式用户界面。它们一起为用户提供在松散藕合的网络上进行 并发计算的能力。 在p w l 中，应用通过一种标准接i e i 来访问网络中的处理单元。应用程序由多个组件 组成，每个组件是一个子任务，子任务的粒度比较大。在执行期间，可启动每个组件的 多个实例。 应用程序可把p v m 系统看成是一通用型，灵活的并行计算资源。该资源可以用三种 层次进行访问：透明模式、结构依赖模式和低级模式。在透明模式中，组件的实例被自 动送到最合适的处理单元中；在结构依赖模式中，用户可指明执行特定组件所需的特定 结构；在低级模式中，应用可直接指定要使用的机器。这种多层次访问方式具有灵活性， 并且保证了可以充分利用网上个别机器的特殊性能。 ( 3 ) p v m 的功能 从应用程序员的角度来看，p v m 的功能如下： 系统配置。p w l 系统中的结点机数目可以变化，另外新的机器类型也可以增加，坏 掉的机器可以从p v m 中删除，这些只要更改启动时的主机文件( h o s t f i l e ) 即可。另外 在应用程序中可用相应的函数进行处理机的增加删除操作。 通信和消息打包解包。在执行分布式程序时，多个子程序( 予任务或进程) 必须 进行通信，从而有效协作，共同完成计算任务。p v m 提供基于消息传递的通信设施。p v m 中提供了用于消息打包解包以及在不同的任务之间进行消息传送的函数。在p y m 通信模 型中保证了任何任务可把消息送给任何p v m 任务，并且对要发送的消息大小和数量没有 任何限制。在p v m 中实现的是阻塞发送、阻塞接收和非阻塞接收功能。p v m 模型保证了消 息的原有顺序，即先发先收另外消息缓冲区是动态分配的。 任务派生和管理。p v m 提供把用户进程变为p v m 任务的函数。在p v m 函数库中，有 启动和结束p v m 任务的函数，提供把任务与其他p v m 任务相联系的机制。每个任务都有 一整型任务标识号( t i d ) ，r i d 必须是唯一的。在p v m 计算模型中，任务划分工作由应用 程序员完成，而任务分配由系统控制，存在多种任务分配方式 异常情况处理。当p y m 系统中的某一个主机失败后，p v m 能自动检测出坏机器并把 它从虚拟机中删去。应用能查询主机的状态，并且能要求置换主机。值得指出的是，在 处理主机失败时，系统并不负责应用程序能正确恢复，这必须由应用程序自己来进行错 1 2 桂林工学院硕士学位论文 误恢复和任务迁移等。 调试功能。一般来说，调试并行程序比调试串行程序困难得多。在p v m 中提供了 两个子程序，p v m _ p e r r o r 用于自动检测错误情形是否发生：p v m _ s e r r o r 用于打印所发出 的错误状态。 ( 4 ) p 的特点 p v m 支持用户采用消息传递方式编写并行程序，计算以任务( t a s k ) 为单位，一个任 务就是一个进程，每个任务都有一个t a s k i d 来标识( 不同于进程号) p v m 支持在虚拟机 中自动加载任务运行，任务问可以相互通讯以及同步。在p v i l 系统中，一个任务被加载 到哪个结点上去运行，一般来说，对用户是透明的( p v m 允许用户指定任务被加载的结点) ， 这样就方便了用户编写并行程序。 归结起来，p v m 的特点有如下几点： c ) p v m 系统支持多用户及多任务运行，多个用户可将系统配置成相互重叠的虚拟机， 每个用户可同时执行多个应用程序。 易于编程。p v m 支持多种并行计算模型，用户使用p v m 提供的函数库可进行并行程 序或分布式程序的设计工作，使用传统的c 语言和f o r t r a n 语言。 系统提供了一组便于使用的通信原语，可实现一个任务向其它任务发消息，向多 个任务发消息，以及阻塞和无阻塞收发消息等功能，用户编程与网络接口分离。系统还 实现了通信缓冲区的动态管理机制，每个消息所需的缓冲区由p v m 运行时动态申请，消 息长度只受结点上可用存储空间的限制。 p v m 提出了进程组的概念，可以把一些进程组成一个进程组，一个进程可属于多个 进程组，而且可以在执行时动态改变。 支持异构计算机联网构成并行虚拟计算机系统且易于安装、配置。p v m 支持的异构 性分为三层：机器层、应用层和网络层。也就是说，p v m 允许应用任务充分利用网络中适 于求解问题的硬件结构；p v m 处理所有需要的数据转换任务；p v m 允许虚拟机内的多个机 器用不同的网络( f d