（计算机系统结构专业论文）基于集群系统并行求解线性方程组的设计与实现.pdf

li：j1j摘要由于大型线性方程组在油藏模拟、化学工程、常微分方程边值问题等领域的广泛应用，使得对其求解的研究一直是个热点。近些年来计算机硬件迅猛发展，人们对求解大型线性方程组以便适应新的计算环境的研究也从未停止过。基于目前并行处理系统已经成为许多科学工程或者科研中的主流计算环境，工业和科研等领域对线性方程组的求解已大多选择在并行机上进行，而集群系统又是最优秀的并行处理平台，那么作为重点课题之一的大型线性方程组的求解，其在集群系统环境下的并行求解方法的研究和设计，就具有非常重要的理论和实际意义。本文主要基于集群系统对线性方程组并行算法进行了研究、设计和实现，内容包括：( 1 ) 实现了m p i 和o p e n m p 多粒度混合编程的求解线性方程组的高斯算法。( 2 ) 由于服务器的特殊性，即实验测试程序与其他程序共享处理器内存，所以导致集群系统经常出现内存不足或内存不稳的情况，为解决该情况下大规模线性方程组的求解，本文根据经典g a u s s 算法提出d i v i g a u s s 算法，在a l t i x 3 7 0 0 服务器上测得实验数据并取得定的应用。( 3 ) 在求解三角形方程组部分，根据文件划分思想对列扫描算法进行了改进，进而保证了程序的顺利运行。由于本算法中文件划分思想的提出，该算法可以实现内存不足或不稳情况下的大规模三角形方程组的调入和求解，实验结果验证了算法的有效性。本文搭建了基于l i n u x 的a l t i x 3 7 0 0 服务器并行计算平台，构建了此平台下的m p i和o p e n m p 并行程序设计环境，并将本文提出的d i v i g a u s s 算法在此平台上进行测试，并对其性能分析，实验结果表明，本文设计的算法能够很好的在小内存的服务器上运行大规模线性方程组的高斯求解程序。关键词：m pi ；0pe n m p ；gat lss 消去；矩阵划分；三角形方程组-矗曩辅，-f遇疆嘎u。ii，i叠墨工珂蠢哩l留h a v ec h o s e nt os l o v i n gt h el i n e a re q u a t i o n s ss o l u t i o no nt h ep a r a l l e lm a c h i n es y s t e m ，t h ec l u s t e rs y s t e mi st h em o s te x c e l l e n tp a r a l l e lp r o c e s s i n gp l a t f o r m ，t h e nt h er e s e a r c h i n ga n dd e s i g n i n go ft h el a r g e s c a l el i n e a re q u a t i o n sp a r a l l e ls o l u t i o nm e t h o du n d e rt h ec l u s t e rs y s t e mh a st h ev e r yi m p o r t a n tt h e o r ya n dt h ep r a c t i c a ls i g n i f i c a n c e w i t ht h es c i e n c ea n dt e c h n o l o g yd e v e l o p m e n tr a p i d l y ，t h es y s t e mo fl i n e a re q u a t i o n ss c a l eu n c e a s i n gt oi n c r e a s ea l o n gw i t hi t ，t h i si sa l s og e t t i n gt h er e q u e s to fc o m p u t e rh a r d w a r eh i g h e ra n dh i g h e r ，t h i sa r t i c l em a i n l yc a r r i e ds t u d i e da n dr e a l i z e sb a s e do nt h es y s t e mo fl i n e a re q u a t i o n sp a r a l l e la l g o r i t h mo nt h ec l u s t e rs y s t e m ，t h ec o n t e n ti n c l u d e d ：( 1 ) h a sr e a l i z e dm p ia n do p e n m pt h em u l t i g r a n u l a r i t ym i xp r o g r a m m i n gs o l u t i o ns y s t e mo fl i n e a re q u a t i o n s sg a u s sa l g o r i t h m ( 2 ) a sar e s u l to fs e r v e r sp a r t i c u l a r i t y ，w h i c he x p e r i m e n tt e s to r d e rw i t ho t h e rp r o c e d u r es h a r i n gp r o c e s s o rm e m o r y ，t h e r e f o r et h ec l u s t e rs y s t e m sm e m o r yi n s u f f i c i e n c yo rs t e a d yf r e q u e n t l y ，i no r d e rt os o l v et h el a r g e s c a l es y s t e mo fl i n e a re q u a t i o nu n d e rt h i ss i t u a t i o n ，t h i sa r t i c l ea c c o r d i n gt ot h ec l a s s i c sg a u s sa l g o r i t h mt op r o p o s et h ed i v i g a u s sa l g o r i t h m ，o b t a i n st h ee m p i r i c a ld a t u mo nt h ea l t i x 37 0 0s e r v e r ( 3 ) i nt h ep a r to ft h es o l u t i o no ft r i a n g l ee q u a t i o n ，t h ea l g o r i t h mh a sp r e s e n t da c c o r d i n gt ot h ei m p r o v e m e n to fr o w - s c a n n i n ga l g o r i t h ma c c o r d i n gt ot h et h o u g h to ft h ef i l e - d i v i s i o n ，t h e ni th a sg u a r a n t e e dt h ep r o c e d u r es m o o t hm o v e m e n t b e c a u s eo fu s i n gt h et h o u g h to ff i l e d i v i s i o n ，t h i sa l g o r i t h mr e a l i z e sl a r g e s c a l el i n e a re q u a t i o n s sr o l l i na n ds o l v e sw h e nt h em e m o r yi si ni n s u f f i c i e n to rn o ts t e a d ys i t u a t i o n ，t h ee x p e r i m e n t a lr e s u l th a sc o n f i r m e dt h ea l g o r i t h mv a l i d i t y oj，辽宁师范人学硕士学位论文t h ep a r a l l e lc o m p u t i n gp l a t f o r i l lh a sb u i l tb a s e do nt h el i n u xa l t i x 3 7 0 0s e r v e r ，a n du n d e rt h i sp l a t f o r mm p ia n dt h eo p e n m pp a r a l l e lp r o g r a m m i n ge n v i r o n m e n tw e r ec o n s t r u c t e d ，t h ed i v i g a u s sa l g o r i t h mw h i c hp r o p o s e di nt h i sa r t i c l ec a r r i e so nt h et e s ti nt h i sp l a t f o r m ，a n da n a l y s i si t sp e r f o r m a n c e ，t h ee x p e r i m e n t a lr e s u l ti n d i c a t e dt h a tt h ea l g o r i t h md e s i g n e di nt h i sa r t i c l ec a nr u nl a r g e s c a l es y s t e mo fl i n e a rg a u s se q u a t i o n s sv e r yw e l lo nt h es m a l lm e m o r ys e r v e rt os o l v et h ep r o c e d u r e k e yw o r d s ：m p i ；o p e n m p ；g a u s se l i m i n a t e s ；d i v i s i o no fm a t r i x ；t r i a n g u l a rs o l v e ri i i 2 2 2 集群系统s g ia l t i x3 0 0 0 62 3 操作系统82 4 并行程序设计92 4 1m p i 及其实现92 4 2 多线程编程o p e n m p 92 4 3 并行算法及其评价l o2 4 4a l t i x 3 7 0 0 服务器上并行环境的搭建l13 基于m p i + o p e n m p 多粒度混合编程的线性方程组求解算法l53 1 高斯消去法。1 53 2 基于m p i + o p e n m p 多粒度混合编程模型高斯算法的实现l63 2 1m p i o p e n m p 混合编程模型163 2 2m i x g a u s s 算法的伪代码实现163 2 3 测试174 应对小内存集群的并行求解线性方程组的设计与实现1 84 1 问题的提出l84 2 算法思想184 3 算法步骤2 24 4 算法分析2 45 基于服务器并行求解三角形方程组的设计与实现2 65 1 算法思想与策略2 65 2 算法描述2 7辽宁师范人学硕士学位论文5 3 复杂度分析2 85 4 实验测试与结果分析3 06 模型计算与应用3 36 1a b e e m o x 模型简介3 36 2 实际模型计算3 46 2 1 模型说明3 46 2 2 数值实验计算结果3 6结论3 9参考文献4 0攻读硕士学位期间发表学术论文情况4 3致谢4 4一v 一辽宁师范大学硕士学位论文1 绪论1 1 研究背景及意义线性方程组是线性代数的主要内容，也是科学和工程计算中最常见的问题，对其求解的研究主要来自两方面，一是在电网络分析、计算机辅助几何设计、核物理、电磁场数值计算、数值天气预报等领域的广泛的实际应用；二是对数学研究本身的价值，因为线性方程组的数值解法在计算数学中具有重要地位，如数据插值、偏微分方程和积分方程问题的计算等，大量的科学技术问题，最终往往也会归结为解一个n 元线性方程组。在石油勘探、天气预报等问题中常常出现成百上千阶的方程组，也就产生了各种形式方程组数值解法的需求，研究大型方程组的解已经是目前计算数学中的一个重要方向和课题。在此研究中极具挑战性的就是求解大规模线性方程组，甚至是求解上百万阶规模的方程组的问题。目前各种类型的并行处理系统已经成为许多科学和工程的计算环境，并成为科研或求解重大规模挑战性问题的工具。针对一直以来计算的精度要求、计算模型的不断变化，为了适应新的计算环境或者追求更高的求解速度、求解容量等，集群系统作为具有良好性价比的并行处理机系统也已经被广泛用于科研和应用中。因此大型线性方程组在服务器并行环境下求解方法的研究也广受关注，另外国产y h 系列、曙光系列机的研制成功，再次使得对大规模线性方程组在集群系统下的并行求解成为研究的热点。目前基于集群并行求解线性方程组求解算法很多，但是由于矩阵类型、规模和集群的性能差别很大，针对不同的并行机，需要大量的实验才能找到比较理想的高效算法。s g ia l t i x3 0 0 0 系列服务器应用广泛，尤其在生命科学领域，从运算化学与分子模拟到生物信息学的各种任务中，充分展示出开放源代码的优势。而求解线性方程组在化学领域中更是解决科研问题的核心，比如用程序计算分子中的电荷分布时，随着分子规模的增大，程序对集群系统空闲内存的需求越来越大。而服务器的特殊性导致集群系统内存容量不稳定或者不足的情况时有发生，以至于求解分子电荷分布的程序无法运行，不利于对它的进一步科学研究，因而迫切需要实现一种应对小内存的程序以保证此时科研工作的持续进行。1 2 研究现状目前对线性方程组的研究已经出现大量的算法，如经典的g a u s s 算法、c h o l e s k y 算法等，对其解法的分类通常分为直接法和迭代法。直接法是在没有舍入误差的情况下，通过有限步求得方程的准确解，而迭代法则是建立迭代格式，从初始向量出发，产生向基丁集群系统并行求解线性方程组的设计与实现量序列，逐次逼近方程组的准确解。由于直接法的准确性和可靠性，对于中、小型方程组及一些大型稀疏方程组，常用直接法求解【l 。在数值计算历史上，直接解法和迭代解法交替生辉，一种解法的兴旺与计算机的硬件环境和问题规模是密切相关的。一般说来，对同等规模的线性方程组，直接法对计算机的硬件要求高于迭代法，故近些年来对线性方程组的研究多集中在直接法。对于中等规模的线性方程组，由于直接法的准确性和可靠性高，一般也都用直接法求解。直接法利用一系列递推公式计算有限步能直接得到方程组的精确解，高斯消去法作为是一个众所周知的古老方法，用在高性能集群系统中仍然十分有效。高斯消去法求解是将系数矩阵转换为三角矩阵进行回代求解。对于转换后的三角形方程组的求解，许多国外的专家学者都对其进行过研究和探讨，s c e i s e n s t a t t 认为三角方程组的求解方法可以划分为以下几类l l 】：( 1 )f a n o u t f a n i n ，此类算法的特点是有一系列的外部循环，在这个循环中，所有的处理器一起工作，互相之问环形通信，完成自己的分配任务及在计算和通讯之间轮换。在大规模问题和多处理器时，还有在拓扑数学中时，此法非常有效。( 2 ) w a v e f i r o t 一类算法的特点是通过打乱要解决的向量，把已经解决的结果重叠，内部元素累积成段，段的大小是一个可调节的参数，这个参数用来调节算法的颗粒度，它的缺点是大量通讯。( 3 ) c y c l i c是迄今为止最好的针对较少处理器( = 1 6 ) 的算法，当处理器数目多的时候，性能相对弱化，所以，有各种修改版本来改进它，它的优点是最低限度的通讯，用基础循环算法求解三角形方程组的代表文献见【m j 。针对三角性方程组的求解，国内学者提出了一种用于分布式并行环境下的新算法i5 1 ，该算法的特点是引用了一个一维p 阶的向量，用于保存方程组的p 个计算结果，引用这个向量的好处在于使得处理机间的通信次数明显下降，并且该算法也实现了计算和通信的部分重叠，这些都在一定程度上提高了算法效率，实验证明该算法优于列扫描算法。而专门针对基于p v m 的桌面p c 机环境，一种新的局域网求解三角形方程组的并行算法【6 】得以实现，该算法使用按行分块的卷帘存储方式，较好的实现了负载平衡，且行分块的大小可变化，使得并行算法减少了通信次数，处理机间的通信开销大大减少，此条件下优于算法【5 】。骆志刚等人提出的重叠算法i _ 7 1 充分利用了通信与计算重叠的技术求解阴影部分小三角形对应的方程组的新的并行算法及非阴影部分的代入并修改右端项的计算策略，在计算机能力比较好而通信相对较慢的分布式存储计算机环境中，相比列扫描算法的块版本在性能上有了较大提高。以上并行算法问题提出了一种基于硬盘与内存交换数据的思想，它采用了卷帘划分数据并卷帘存放子文件的方法。1 3 本文工作及内容安排服务器实验环境有它的特殊性，通常并行服务器由多用户共享，系统负载有较大的波动，比如在利用a b e e m o n 模型【9 】计算分子中的电荷分布时，。随着分子规模的增大，程序对空闲内存的需求也越来越大。可能会出现系统内存空闲时并行算法能调入内存运行，而系统内存繁忙时则无法调入的情况。实验所用的a l t i x 3 7 0 0 服务器系统同常运行内存占用率在5 0 8 0 之间，在用户提交任务高峰期甚至出现系统满负荷情况，从而导致在实际应用中想要的结果无法获取，针对a l t i x3 7 0 0 服务器内存不足的实际情况，本文提出了一种连续拆分系数矩阵文件的方案，划分简便且子文件规模可控，解决了程序无法调入的实际问题并在a b e e m o r c 模型电荷分布计算中取得了应用。在对集群系统中线性方程组的求解方法和并行算法的研究和分析的基础上，本文设计并实现了在小内存情况下对大规模线性方程组的求解算法。本文共分六章，其他章节的内容和结构安排如下：第二章阐述了并行计算、集群系统、m p i 并行程序设计等相关基本理论，并在a l t i x 3 7 0 0 服务器上搭建了基于s u s e 的m p i 并行计算平台。第三章介绍了线性方程组的解法，并基于m p i + o p e n m p 编制了多粒度混合线性方程组的m i x g a u s s 求解算法。，第四章应对小内存集群并行求解线性方程组算法的设计思想与d i v i g a u s s 算法的实现，以及算法性能分析。第五章基于服务器和文件划分思想并行求解三角形方程组的设计与实现。第六章模型计算与应用。基于集群系统并行求解线性方程组的设计与实现2 并行简介-2 1 并行计算概念计算机科学在许多领域中发挥着举足轻重的地位，如航天器设计、地震数据处理、密码破译、新药研制、生物信息处理、图像处理等等，在现代科学技术规模或者精密度的不断发展导致的数据规模急速增大的情况下，虽然计算机个体本身的硬件条件也在迅猛发展，然而单机运行仍存在例如内存、硬盘等诸多限制，或者运行时间过长等，也正是这种矛盾推动了从单机串行到多机并行计算的发展。并行计算是指同时使用多种计算资源解决计算问题的过程，也就是在并行机上所做的计算。并行计算的主要目的是快速解决大型且复杂的计算问题。简单来说，并行计算就是满足不断增长的计算力的需求，也是应用的需求。并行计算可以降低单个问题求解的时间，提高问题求解精度，增加问题求解规模并且可以实施无法替代的模拟计算，并行计算分为时间上的并行和空间上的并行。时间上的并行就是指流水线技术，而空间上的并行则是指用多个处理器并发的执行计算。2 2 并行机2 2 1 并行机的发展并行机的发展经历了1 9 6 4 至1 9 7 5 年的萌芽阶段、1 9 7 6 至1 9 9 0 年的向量机s m p发展和鼎盛阶段、1 9 9 0 至1 9 9 5 年m p p 出现和蓬勃发展阶段以及1 9 9 5 年后逐渐成为并行计算机主流的c l u s t e r 阶段。并行计算科学中主要研究的是空间上的并行。空间上的并行导致了两类并行机的产生，按照f l y n n 的说法分为：单指令流多数据流( s i m d ) 和多指令流多数据流( m i m d ) ，常用的串行机也叫做单指令流单数据流( s i s d ) ，它们的处理机制见下图2 1 。辽宁师范人学硕士学位论文静i n s t r u c tl o a da ( 2 )i 喇b c 静a 钟b 圆咖他c ( 2 1脯嘁h n a r u c tp r e yi n s l r u ai o t a ( n )喇b f n c ( 州i n l b i n |s t o 传c ( 1n e x ti l m n l c tp 2p n8 帅图2 1s i s d 、s i m d 、s i m d 处理机制f i g 2 1s i s d 、s i m d 、s 1 m dp r o c e s s i n gm e c h a n i s m即vi n s t r u c td 0 1 0 刚一l l p 陋w 3z m = c 1 1 )1 0c o n t i n u en e x ti n s t r u c t( 1 ) 共享存储体系结构s m p ( s m p 体系结构见图2 2 ) 瓶颈在访存带宽，限制了可扩展性，共享存储的机器可以运行各种编程模式的程序，包括串行程序、共享存储并行程序和消息传递并行程序。共享存储的机器利用多个处理器的并行处理性能，自动并行作用有限，需要其他编程方式的应用，如o p e n m p 。( 2 ) 分布式存储体系结构无共享的机器，m p p 和c l u s t e r ( 图2 3 图2 4 ) ，具有最好的可扩展性，采用消息传递编程，也可以通过d s m ( 图2 5 ) 软件的方式来模拟实现共享存储，性能受到影响，但可以运行o p e n m p 应用程序。围困回图2 2s m pf i g 2 2s m p回回回圈困圈图2 3m p pf i g 2 3m p p基于集群系统并行求解线性方程组的设计与实现回回回围困圈图2 4c l u s t e r c o wf i g 2 4c l u s t e r c o w圈圈圈图2 5d s mf i g 2 5d s m2 2 2 集群系统一s g ia i ti x3 0 0 0集群( c l u s t e r ) 并不是一个全新的概念，早在七十年代计算机厂商和研究机构就开始了对集群系统的研究和开发。对集群的研究起源于集群系统的良好的性能可扩展性。提高c p u 主频和总线带宽是最初提供计算机性能的主要手段，但是这一手段对系统性能的提供是有限的。接着人们通过增加c p u 个数和内存容量来提高性能，于是出现了向量机，对称多处理机( s m p ) 等。但是当c p u 的个数超过某一阈值，象s m p 这些多处理机系统的可扩展性就变的极差。主要瓶颈在于c p u 访问内存的带宽并不能随着c p u个数的增加而有效增长。与s m p 相反，集群系统的性能随着c p u 个数的增加几乎是线性变化的，图2 6 显示了这种情况。图2 6 几种计算机系统的可扩展性f i g 2 6s e v e r a lk i n do fc o m p u t e rs y s t e m se x t e n d i b i l i t y辽弓师范大学硕士学位论文集群系统由于无可比拟的性价比优势占据主流位置，它的主要优点还有：更高的计算能力、高性能( 负载平衡集群允许系统同时接入更多的用户) 、系统的高可用性( 集群中的一个节点失效，它的任务可以传递给其他节点，可以有效防止单点失效) 、良好的可扩展性、更高的性价比( 采用廉价的符合工业标准的硬件构造高性能的系统) 等。简单的说，集群就是一组计算机，它们作为一个整体向用户提供一组网络资源，这些单个的计算机系统就是集群的节点。s o la l t i x3 0 0 0 系列是基于l i n u x 操作系统的集群计算机系统，由于多年来不断的体系革新，s g i 早已被公认为高性能计算领域的领导者。支持6 4 位l i n u x 系统的s g ia l t i x3 0 0 0 系列产品基于s g in u m a f l e x 的体系结构，与所有6 4 位l i n u x 应用程序1 0 0 的二进制兼容。该解决方案融合了6 4 位n u m a 和集群技术的精髓，为l i n u x 用户和应用程序开发人员提供了超级计算的能力和更多的发展机会。n o d e0n o d e1s g ia l t i x3 0 0 0 系统是分布式共享内存的计算机系统，s g ia l t i x3 0 0 0 服务器和超级集群系列由s g ia l t i x3 3 0 0 和s g ia l t i x3 7 0 0 系列服务器组成，大量实际应用基准测试表明，s g ia l t i x3 0 0 0 系列服务器和超级集群系统在性能和性价比方面具有不可撼动的优势。即使当前最具竞争力的系统的速度翻番，s g ia l t i x3 0 0 0 系列服务器和超级集群系统都比它要快1 3 0 。基丁集群系统并行求解线性方程组的设计与实现s g ia l t i x3 0 0 0 系列的进步之处在于它能够在一个单一的集群节点中最多配置6 4 个处理器、4 t b 存储器，并且可以跨节点实现全局内存共享，这一过程通常会涉及到成百上千个处理器。强大的可升级计算环境可以把接近半个t b 的数据驻留在单一系统镜像中，结合并行架构软件，可以获得快上百倍的计算能力，从而使其可以在同一时阳j 内运行更多的工作，并对实验选项进行更广泛的测试。综合运用多种技术的结果使得s g ia l t i x3 0 0 0 系列表现出无与伦比的性能优势，大大缩减了进行计算所需的时间和资源。s g ia l t i x3 0 0 0 系列服务器和超级集群系统可在计算化学、生物科学和计算机流体力学等计算密集型领域发挥一流的性能。无论是对大规模蛋白质结构进行模拟还是预测催化剂的实验效果，6 4 位计算能力以及系统良好的伸缩性对于及时准确地得到实验结果具有重要的作用。生命化学领域的科研人员对于计算能力的需求正好和s g ia l t i x3 0 0 0 系列系统所表现出来的性能相吻合，所以仅仅在s o la l t i x3 0 0 0 系列系统推出的几个星期内，在生命化学领域应用广泛的计算软件工具都纷纷移植到了s g i 新的硬件系统中来。2 3 操作系统为了提供给用户一个良好的并行编程环境，很多厂商开发了有自己特色的平台，如i b m 公司的e u i 、i n t e l 的n x 、橡树岭的p v m 等，这些平台都开发了各自特有的消息传递包或者消息传递库，它们提供了相似的功能，在特定的平台上也具有优越的性能，缺点是在应用程序级互不兼容，移植性差。黑钳甜潮c 。u n t e 慧p m篙瓠铀ml i n u x4 4 38 8 6 0 1 7 1 8 9 1 5 72 6 9 6 2 5 8 3w i n d o w s51 o o 3 6 4 7 2 04 6 1 6 0 6u n i x2 24 4 0 1 3 5 7 7 2 61 7 2 9 7 8 1b s db a s e d1o 2 0 1 2 2 4 0 01 3 1 0 7 2m i ) ( e d2 95 8 0 3 5 7 3 9 9 34 3 8 6 5 6 2t o t a l s5 0 01o o 2 2 6 0 7 9 9 6 3 03 3 6 7 16 0 4 9 2图2 8 并行机采用的操作系统使用调查表f i g 2 8t h ep a r a l l e lm a c h i n eu s e so p e r a t i n gs y s t e mu s es u r v e yf o r m调查表明，在并行机中绝大多数采用l i n u x 操作系统，目前流行的l i n u x 操作系统大约有几百个版本，出名的有u b u n t u 、r e d h a t 、f e d o r a 、o p e n s u s e 、m i n t 、d e b i a n 、p c l i n u x o s 、r e d f l a g 等。其中s u s el i n u x 是国际技术的领导者，是开源操作系统软件的解决方案提供商。s u s e 是德国最著名的l i n u x 发行版，是具有较高声誉的版本之一，563圆0233m，协加的。钳盯瓤h41089o“u 31221ps251114辽j 师范大学硕士学位论文它独有的l i n u x 技术专长及其拥有的全世界最大的开源软件开发团队都给s u s e 带来了作为当今最完整l i n u x 解决方案的赞誉。它最显著的特点是全面的系统，友好的图形介面，广泛的商业用途，很适合做服务器。根据2 0 0 8 年t o p 5 0 0 提供的数据，s u s el i n u x企业版是当今世界上最大性能( h p c ) 超级计算机的首选l i n u x 版本。2 4 并行程序设计2 4 1 胛l 及其实现m p i ( m e s s a g ep a s s i n gi n t e r f a c e ) 是消息传递接e l 的工业标准，由m p i 论坛开发，支持f o r t r a n 和c ，被用在开发基于消息传递的并行程序中，它可以为用户提供一个实际可用的、可移植的、高效、灵活的消息传递接口库，是目前的主流并行编程模型之一。m p i 的发展经历了两个阶段，m p i1 i n m p i1 2 2 0 ，目前m p i 几乎被所有并行计算环境( 共享和分布式存储并行机、m p p 、集群系统等) 和流行的多进程操作系统( u n i x 、l i n u x 、w i n d o w s ) 所支持，提供了一个适合进程间进行标准消息传递的并行程序设计平台【1 0 i 。它的优点是允许静态任务分配，具有一系列优化的聚合通信子程序，可实现通信和计算重叠，基于它开发的应用程序具有最佳的可移植性、功能强大、效率高等多种优点。但m p i 也存在没有提供容错机制和不能对资源实现直接管理；分解、开发和调试程序开销巨大；粒度太小会导致通信开销大等缺陷。m p i 也是一个发展的平台，m p i - 2 已经增加动态进程管理和远程存储访问，功能将会越来越大和完善，相对其他并行编程环境而言，它还是具有诸多优势j 。目前国际上有多种m p i 的软件实现，其主要有l a m 、c h i m p 、m p i c h _ - 三个版本l l2 。，其中m p i c h ( 由a r g o n n e 国家实验室和m s u 研制) 和l a m 较为流行。l a m ( l o c a la r e am a c h i n e ) 是由o h i os t a t eu n i v e r s i t y 开发的基于异构网络集群的并行程序支撑环境。1 9 9 1年到1 9 9 4 年间，在a l a s d a i rb r a c e 、g o r d o ns m i t h 等主要开发人员的努力下，实现了免费的c h i m p 版本。其中在m p i1 1 阶段，m p i c h 是m p i 最流行的非专利实现，它i 扫a r g o n n e国家实验室和密西西比州立大学联合开发，具有更好的移植性，由于m p i c h 是一个与m p i 规范同步发展的版本，每当m p i 推出新版本，就会有相应的m p i c h 实现版【l 引。2 4 。2 多线程编程o p e n m p在并行计算领域，有两个流行趋势：一方面s m p 系统越来越多的成为高性能计算平台的基本结构：另一方面由于程序中对指令级并行性开发越来越难，单个处理器的结构也开始向开发线程级并行性转移，特别是近期，在单芯片频率达到近乎极限后，c p u进入了多核时代。多核是指在一枚处理器中集成两个或多个完整的计算引擎。在多c p u基于集群系统并行求解线性方程组的设计与实现或多核机器上开发多线程的并行程序时，多核机器和以前的多c p u 机器有很大不同，以前的多c p u 机器都是用在特定领域，比如服务器，或者一些可以进行大型并行计算的领域，这些领域很容易发挥出多c p u 的优势。多核c p u 中，要很好地发挥出多个c p u 的性能的话，必须保证分配到各个c p u 的任务有一个很好的负载平衡，否则一些c p u 在运行，另外一些c p u 处于空闲，无法发挥出多核c p u 的优势来。19 9 7 年1 0 月，h p 、s u n 、i b m 和i n t e l 等联合开发和推行一种新的共享主存编程模型的建议标准o p e n m p i l 4 l ，在应用层添加并行命令，通过编译器产生必须的代码，大大简化了所需的库调用。在基于单一库调用的p t h r e a d s 向基于编译制导命令的方法转变过程中，o p e n m p 得到了极大的推广与应用，成为业界的事实标准。随后o p e n m pa r b( o p e n m p 官方机构) 在1 9 9 8 年的1 0 月推出了o p e n m pc ( 3 + + a p i2 0 ，在此基础上合并了f o r t r a n 和c c + + ，于是在2 0 0 5 年5 月接着发布了最新的o p e n m pa p i2 5 规范。o p e n m p 的特点是简单易用，因而成为共享主存结构编程的事实标准，但是开发o p e n m p 并行程序也面临着很多性能问题，比如负载不均衡、存储访问效率不高等2 4 3 并行算法及其评价并行算法是指一次可执行多个操作的算法。现在对并行算法的研究已发展为一个独立的研究领域，很多用串行算法解决的问题也已经有了相应的并行算法。并行算法基本上是随着并行机的发展而发展的，一个好的并行算法要既能很好地匹配并行计算机硬件体系结构的特点又能反映问题内在并行性1 1 2 1 。在并行机上求解线性方程组，需要设计出适合该机的并行算法，并行算法设计的优劣会对并行机的效率产生很大影响。对于相同的并行计算模型可以有多种不同的并行算法来描述，不同的算法可以有几倍几十倍甚至上百倍的性能差异也是完全正常的。在设计并行程序时，应尽量优化并行算法、大并行粒度、顾及负载平衡、尽量减少通信次数、避免大消息( 1 m ，避免消息缓冲区的溢出，且效率较低) 、避免大消息打包( 内存拷贝开销大) 。并行性能的分析指标有执行时间、并行加速比、效率。1 、执行时间并行程序的运行时间通常由计算时间和通讯时间组成，计算时间是指处理器计算的时问，通讯时间是指处理器间互相传递消息消耗的时间，它通常是根据计算中的通信次数和通讯量计算所得，计算通讯时间的并行计算模型有l o g p 、b s p 等。对于一个n 阶矩阵的问题，算法的运行时间通常表示为n 的函数。2 、加速比辽宁师范人学硕十学位论文加速比是度量多节点并行处理比单节点处理的加速倍数，用来描述并行处理的效果。绝对加速比以当前解决问题的最好串行算法作为比较基准，着眼于并行处理相对于串行处理的优化效果上，用于评价并行算法。相对加速比定义为同一并行算法在单结点上运行时间与多个相同结点构成的并行处理系统上运行时间之比，它着眼于并行算法和计算机本身的可扩展性，用于评价计算机系统的性能。加速比的数值与处理器的个数有关，如果使用的处理器个数不相同，加速比就没有可比性，并行程序性能的分析可以由并行算法的加速比来衡量。在处理器资源独享的前提下，假设某个应用程序在某台并行单处理器上串行运行所花的执行时间为t s ，而该程序并行化处理后，p 个处理器运行所花的时间为t p ，则该并行程序在该并行计算机上的加速比公式可定义为驴号需要说明的是，t l 指处理器个数为1 时，并行程序的执行时间。通常情形下，t i大于t 。，因为并行计算时往往引入一些冗余的控制和管理开销。3 、效率另外一种衡量并行计算性能的参数为并行系统效率，并行系统效率e 被定义为。驴i其中s p 为并行加速比，p 为处理器个数。系统效率给定了处理器用于计算的时间比例。加速比和效率是衡量一个并行程序性能的最基本的评价方法，显然，执行最慢的进程将决定并行程序的性能。2 4 4a i tix 3 7 0 0 服务器上并行环境的搭建( 1 ) 安装s u s e l1 2 操作系统，安装时要开启防火墙和s s h 服务，在安装好后再关闭。( 2 ) 安装l a m 。m p i 以及o p e n m p首先一定要先安装o p e n m p ，o p e n m p 安装好后再安装l m m p i安装i c c 编译器，导入证书后自动检测安装环境，如果提示缺少g + + 则在s u s e控制面板里安装g c c ，g c c + + 以及g f o r t r a n 相关包，再次检测，如果提示缺少l i b s t d c + + s o 5 就需要安装l i b s t d c + + 3 3 这个包，然后从网上找到匹配操作系统版本的l i b s t d c + + 3 3 3 2 b i t 包安装，再次检测，提示安装成功。i f c 编译器的安装过程跟i c c 的安装过程一样。需要注意的是在i c c 和i f c 安装成功后要进入o p t i n t e l c o m p l i e r 11 i 0 4 6 b i n i m e l 6 4 文件夹中执行s o u r c e基丁集群系统并行求解线性方程组的设计与实现i f o r t v a r si n t e l 6 4 s h ，否则安装l a m 的时候就会提示找不到指定的i f o r t 编译器并报错，如果报错了请删除解压好的l a m 7 1 1 这个文件夹，重新解压安装，否则还是检测在i f o r t 编译器时报错。安装l a m m p i ：下载完整的t a r 格式的l a m 压缩包，解压、编译、安装，安装时指定安装路径，解压后执行c o n f i g u r e p r e f i x = u s r l o c a l l a m - 7 1 1 _ w i t h f c = i f o r t ，然后执行m a k e 、m a k ei n s t a l l ，提示安装成功，如果出现m a k e 命令失效，则需要在s u s e 控制面板中安装m a k e 包来解决。( 3 ) 安装服务：要执行l a m 并行程序必须要有r s h 服务或者s s h 服务其中一个，在y a s t控制面板中安装r s h 服务，从s u s e s e r v e r 版本的光盘中找到r s h s e r v e r 这个包安装，否则s u s e 不能开启r s h 服务，s s h 服务已经在安装s u s e 的时候打开，不需要另外安装。( 4 ) 配置服务：配置好本机i p 地址后输入v i e t c h o s t s ，更改成l2 7 0 0 1l o c a l h o s t拌s p e c i a li p v 6a d d r e s s e s：ll o c a l h o s ti p v 6 一l o c a l h o s ti p v 6 1 0 0 p b a c kf e 0 0 ：oi p v 6 1 0 c a l n e t肋0 ：oi p v 6 m c a s t p r e f i xf 内2 ：li p v 6 。a l l n o d e s册2 ：2i p v 6 a l l r o u t e r sf 内2 ：3i p v 6 a 1 1 h o s t s1 9 2 9 2 0 0 1 0 3p c l 0 31 9 2 9 2 0 0 1 0 2p c l 0 2执行v i e t c h o s t n a m e更改为本机的名字比如p c l 0 2执行v i e t c s y s c o n f i g n e t w o r k i f c f g e t h 0 ，改为b o o t p r o t o = b r o a d c a s t = 19 2 9 2 0 0 2 5 5 。e t h t o o lo p t i o n s = ”i p a d d r = l9 2 9 2 0 0 10 3 2 4 m t u = ”n a m e = r t l 8l11 8l6 8 bp c ie x p r e s sg i g a b i te t h e m e tc o n t r o l l e r n e t m a s k = 2 5 5 2 5 5 2 5 5 0 n e t w o r k l9 2 9 2 0 0 0 r e m o t ei p a d d r = s t a r t m o d e = a u t o u s e r c o n t r o l = n o 一1 2 一辽宁师范大学硕士学位论文执行v i e t c s s h s s h _ c o n f i g取消这两句注释r s a a u t h e n t i c a t i o ny e sp a s s w o r d a u t h e n t i c a t i o nn o执行v i e t c s s h s s h d _ c o n f i g取消这几句注释p u b k e y a u t h e n t i c a t i o ny e sa u t h o r i z e d k e y s f i l es s h a u t h o r i z e d _ k e y sp a s s w o r d a u t h e n t i c a t i o nn o执行v i e t c p r o f i l e找到c o m f o r t a b l e 后加入路径：u s r x 11 r 6 b i n ：u s r l o c a l l a m 一7 1 1 b i n执行v i h o m e m p i b a s h r c ，加入：e p o r tp a t h = $ p a t h ：o p t i n t e l c o m