（计算机软件与理论专业论文）两种krylov子空间算法的并行性能改进研究.pdf

独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研 究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得重废自e 直太堂或其他教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡 献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：乏喜1 碗匆 签字日期： 歹卯9 年f 月烨日 学位论文版权使用授权书 本学位论文作者完全了解重麽由g 电太堂有关保留、使用学位论文的规 定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查 阅和借阅。本人授权重麽邮电太堂可以将学位论文的全部或部分内容编入 有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论 文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：赵害1 1 捌 签字日期：鲫1 年上月许日 导师签名：秽何如 签字日期儿彳私膨日 u 重庆邮电大学硕士论文 摘要 摘要 寻求大型稀疏线性方程组的高效并行解法是当前大规模科学计算中亟 待解决的热点问题。k r y l o v 子空间算法是求解大型稀疏线性方程组最流行 和最有效的迭代方法之一，其并行计算主要考虑矩阵向量乘和内积计算。 目前通过适当编码，矩阵向量乘在并行计算时不会造成严重性能降低的通 信问题。但内积计算并非如此，由于内积计算需要全局通信，在分布式并 行计算环境下其成为高效并行计算的瓶颈。 o r t h o m i n ( m ) 算法和g c r ( k ) 算法是两种k r y l o v 子空间算法，为减 少两算法内积计算引起的全局通信以提高并行性能，本文以油藏数值模拟 问题为应用背景分别对两算法做了如下工作： 首先利用o r t h o m i n ( m ) 算法的固有性质改变其计算次序，给出了该 算法的改进形式，其次对算法进行了并行设计、理论分析，最后通过求解 油藏数值模拟问题给出数值实验。同o r t h o m i n ( m ) 算法相比，改进算法 与o i 汀h o m i n ( m ) 算法具有相同的收敛性，在分布式并行计算环境下进行 并行计算时改进算法用连续内积计算代替了o r t h o m i n ( m ) 算法分离的内 积计算，消除了o r t h o m i n ( m ) 算法两次内积计算的数据相关性，使同步 开销次数减少为o r t h o m i n ( m ) 算法的一半进而加大了计算时间相对通信 时间的比重，提高了并行效率。理论分析表明当处理机台数较多时改进算 法比o r t h o m i n ( m ) 算法的并行计算时间要快，有更好的加速比及可扩展 性。数值实验结果也表明改进算法的并行性能要优于o i u h o m i n ( m ) 算法， 更利于油藏数值模拟问题的并行求解。 对于g c r ( k ) 算法，利用同样的方法给出了该算法的改进形式，并给出 算法的并行设计、理论分析，且通过求解油藏数值模拟问题给出数值实验。 与o r t h o m i n ( m ) 算法类似，改进算法与g c r ( k ) 算法具有相同的收敛性， 在分布式并行计算环境下进行并行计算时改进算法使同步开销次数减少 为g c r ( k ) 算法的一半，提高了并行效率。理论分析同样表明当处理机台 数较多时改进算法比g c r ( k ) 算法的并行计算时间要快，有更好的加速比 及可扩展性。数值实验结果也同样表明改进算法的并行性能要优于g c r ( k ) 算法，更利于油藏数值模拟问题的并行求解。 关键词：k r y l o v 子空间算法，非对称稀疏线性方程组，并行计算，同步开 销，油藏数值模拟 重庆邮电大学硕士论文 a b s t r a c t a b s t r a c t a tp r e s e n t ，ah o t s p o tp r o b l e mt ob es o l v e di st oi n v e s t i g a t eh i g he f f i c i e n t p a r a l l e lm e t h o d sf b rs o l v i n gl a r g es p a r s el i n e a rs y s t e m si nt h el a r g e - s c a l e s c i e n c ec o m p u t a t i o np r o b l e m s k r y l o vs u b s p a c ea l g o r i t h m sa r eo n eo fm o s t e f f e c t i v ea n dm o s tp o p u l a ri t e r a t i v em e t h o d s ，a n dt h ek e yp o i n t sf 0 rt h e i r p a r a l l e lc o m p u t a t i o na r et oc o m p u t em a t r i x v e c t o rm u l t i p l i c a t i o n sa n di n n e r p r o d u c t s b yp r o g r a n l m i n gp r o p e r l y t h e c o m p u t a t i o n o fm a t r i x v e c t o r m u l t i p l i c a t i o n sc a nn o tp r o d u c eh i g hg l o b a lc o m m u n i c a t i o nw h i c hc a nr e d u c e p a r a l l e lp e r f o r m a n c ea tp r e s e n t d i f 诧r i n gf r o mm a t r i x - v e c t o rm u l t i p l i c a t i o n s ， t h a ti n n e rp r o d u c t se n f 0 r c i n gg l o b a lc o m m u n i c a t i o ni st h eb o t t l e n e c ko fh i g h e f f i c i e n t p a r a l l e lc o m p u t a t i o n o nt h ed i s t r i b u t e d p a r a l l e lc o m p u t a t i o n e n v i r o n m e n t o r t h o m i n ( m ) a l g o r i t h ma n dg c r ( k ) a l g o r i t h mw h i c ha r et w ok r y l o v s u b s p a c ea l g o r i t h m sa r es t u d i e df o rr e d u c i n gg l o b a lc o m m u n i c a t i o ne n f o r c e d b yi n n e rp r o d u c t sa n di m p r o v i n gt h e i rp a r a l l e lp e r f 0 r m a n c e sr e s p e c t i v e l y i n t h i s p a p e rt h et w oa l g o r i t h m sa r ed i s c u s s e db a s e d0 nt h eb a c k g r o u n di n n u m e r i c a ls i m u l a t i o no fo i lr e s e r v o i ra sf 0 1 l o w ： f i r s t ly e m p i o y i n ga ni n t r i n s i cp r o p e r t yo fo r t h o m i n ( m ) a l g o r i t h ma n d c h a n g i n g t h e c o m p u t a t i o ns e q u e n c e i n o r t h o m i n ( m )a l g o r i t h m ， a n i m p r o v e dp a r a l l e la l g o r i t h mo fo r t h o m i n ( m ) a l g o r i t h mi sp r o p o s e df o r i m p r o v i n g t h ep a r a l l e l p e r f o r m a n c e o ft h e o r t h o m i n ( m )a l g o r i t h m s e c o n d ly ，t h e i rp a r a l l e lf 0 r m sa r ed e s i g n e da n dt h et h e o r e t i c a l a n a l y s i si s g i v e n i nt h ee n d ， n u m e r i c a l e x p e r i m e n t i sd o n e b ys o l v i n g n u m e r i c a l s i m u l a t i o no fo i lr e s e r v o i r p r o b l e m s t h ec o n v e r g e n c eo ft h e i m p r o v e d a l g o r i t h mi sa st h es a m ea so r t h o m i n ( m ) a l g o r i t h m ，b u tt h es e p a r a t ei n n e r p r o d u c t sc o m p u t a t i o n i no r t h o m i n ( m ) a l g o r i t h m i s r e p l a c e db yt h e s e q u e n t i a li n n e rp r o d u c t sc o m p u t a t i o ni nt h ei m p r o v e da l g o r i t h m ，a n dt h ed a t a i n t e r d e p e n d e n c ef o ri n n e rp r o d u c t sc o m p u t a t i o ni no i u h o m i n ( m ) a l g o r i t h m i se l i m i n a t e d ，w h e nw ec o m p u t eb yt h ei m p r o v e da l g o r i t h mo nt h ed i s t r i b u t e d p a r a l l e lc o m p u t a t i o ne n v i r o n m e n t a sa r e s u l t ， t h e t i m e so ft h e s y n c h r o n i z a t i o no v e r h e a da r er e d u c e db yaf a c t o ro ft w o ，t h ec o m p u t a t i o n t i m ei si n c r e a s e dc o m p a r e dw i t hc o m m u n i c a t i o nt i m ea n dt h e p a r a l l e l i i p e r f o r m a n c ei si m p r o v e d t h et h e o r e t i c a la n a l y s i sp r o v e st h a tt h ec o m p u t a t l o n t i m eo ft h ei m p r o v e da l g o r i t h mi sl e s st h a nt h a to fo r t h o m i n ( m ) a l g o r i t h m ， a n db o t ht h es p e e d u pa n dt h es c a l a b i l i t yo ft h ei m p r o v e da l g o r i t h ma r eb e t t e r t h a nt h a to fo r t h o m i n ( m )a l g o r i t h m a st h en u m b e ro fp r o c e s s o r sa r e r e l a t i v e l yl a r g e t h en u m e r i c a lr e s u l t sa l s op r o v e t h a tt h ep a r a l l e lp e r f b r m a n c e o ft h ei m p r o v e da l g o r i t h mi sb e t t e rt h a nt h a to fo i 己t h o m i n ( m ) a l g o r i t h m ， a n dt h ei m p r o v e da l g o r i t h mi sm u c hm o r ei n f a v o ro fs o l v i n gn u m e r i c a l s i m u l a t i o no fo i lr e s e r v o i rp r o b l e m si np a r a l l e l i z a t i o n t og c r ( k ) a l g o r i t h m ，e m p l o y i n gt h es a m em e t h o da so i u h o m i n ( m ) a l g o r i t h m ，a ni m p r o v e dp a r a l l e la l g o r i t h mo fg c r ( k ) a l g o r i t h mi sp r o p o s e d f o ri m p r o v i n gt h ep a r a l l e lp e r f o r m a n c eo ft h eg c r ( k ) a l g o r i t h ma n dt h e i r p a r a l l e lf o r m sa r ed e s i g n e d t h e nt h et h e o r e t i c a la n a l y s i si sg i v e na n dt h e n u m e r i c a le x p e r i m e n ti sd o n eb ys o l v i n gn u m e r i c a ls i m u l a t i o no fo 订r e s e r v o i r p r o b l e m s s i m i l a r l yw i t ho r t h o m i n ( m ) a i g o r i t h m ，t h ec o n v e r g e n c eo ft h e i m p r o v e da l g o r i t h mi sa st h es a m ea sg c r ( k ) a l g o r i t h m ，b u tt h et i m e so f t h e s y n c h r o n i z a t i o no v e r h e a da r er e d u c e db yaf a c t o ro ft w oa n dt h ep a r a l l e l p e r f o r m a n c ei si m p r o v e d ，w h e nw ec o m p u t eb yt h ei m p f o v e da l g o r i t h mo nt h e d i s t r i b u t e dp a r a l l e lc o m p u t a t i o ne n v i r o n m e n t t h et h e o r e t i c a la n a l y s i sa l s o p r o v e st h a tt h ec o m p u t a t i o nt i m eo ft h ei m p r o v e da l g o r i t h mi sl e s st h a nt h a to f g c r ( k ) a l g o r i t h m ，a n db o t ht h es p e e d u pa n dt h es c a l a b i l i t yo ft h ei m p r o v e d a l g o r i t h ma r eb e t t e r t h a nt h a to fg c r ( k )a l g o r i t h ma st h en u m b e ro f p r o c e s s o r si sr e l a t i v e l yl a r g e t h en u m e r i c a lr e s u l t sa l s op r o v et h a tt h e p a r a l l e lp e r f o r m a n c eo ft h ei m p r o v e da l g o r i t h mi sb e t t e rt h a nt h a to fg c r ( k ) a l g o r i t h m ，a n dt h ei m p r o v e da l g o r i t h mi s m u c hm o r ei nf a v o ro fs o l v i n g n u m e r i c a ls i m u l a t i o no fo i lr e s e r v o i rp r o b l e m si np a r a l l e l i z a t i o n k e yw o r d s ：k w l o vs u b s p a c ea 1 9 0 r i t l l r i l s ，n o n s y m m e t r i cs p a r s e l i n e a rs y s t e m s ， p a r a l l e lc o m p u t a t i o n ，s y n c h r o n i z a t i o no v e r h e a d ，n u m e r i c a ls i m u l a t i o no fo i l r e s e r v o i r i n 重庆邮电大学硕士论文 目录 目录 摘要i a b s t r a c t i i 第一章绪论1 1 1 研究背景1 1 2k r y l o v 子空间算法的并行化研究现状2 1 3 论文主要工作3 1 4 论文结构4 第二章并行计算及k r y i o v 子空间算法5 2 1 引言5 2 2 并行计算机模型_ 5 2 2 1 并行计算机结构模型5 2 2 2 并行计算模型7 2 2 3 并行编程模型9 2 3 并行算法设计1 0 2 3 1 并行算法的定义和分类1 0 2 3 2 并行算法设计方法1 0 2 3 3 并行算法性能度量1 2 2 4k r y l o v 子空间的概念及其算法分类13 2 4 1k r y l o v 子空间的概念1 3 2 4 2k r y l o v 子空间算法的分类1 4 2 5k r y l o v 子空间算法的并行化策略：1 5 2 6 小结l7 第三章o i u h o m i n ( m ) 算法的并行计算1 8 3 1 引言1 8 3 2k r y l o v 子空间方法一g c r 算法18 3 3 o r t h o m i n ( m ) 算法及其改进2 0 3 3 1o r t h o m i n ( m ) 算法的并行设计2 0 3 3 2 改进算法的并行设计2 2 3 4 算法分析与比较2 5 3 5 数值实验一油藏数值模拟问题的求解2 8 3 6 小结31 第四章g c r ( k ) 算法的并行计算3 2 i v 重庆邮电大学硕士论文目录 4 1 引言3 2 4 2g c r ( k ) 算法及其改进3 2 4 2 1g c r ( k ) 算法的并行设计3 2 4 2 2 改进算法的并行设计3 4 4 3 算法分析与比较3 7 4 4 数值实验一油藏数值模拟问题的求解3 9 4 5 小结4 2 第五章总结及未来的工作4 4 5 1 总结4 4 5 2 未来的工作4 5 致谢4 6 攻读硕士学位期间从事的科研工作4 7 参考文献4 8 v 重庆邮电大学硕士论文 第一章绪论 1 1 研究背景 第一章绪论 从计算机诞生之日起，人们就不断努力加倍提高计算机的运行速度， 并且已经取得非常显著的成绩。然而这种努力不用多久就会因趋于物理器 件的极限而终止。然而人们对计算机性能的要求使无止境的，为了充分挖 掘计算机应用潜力以提高计算机处理效率，一个重要途径就是采用并行处 理技术。并行处理随之也成为了当今计算机技术发展的主要方向之一。随 着科学技术的发展，并行处理技术得到了飞速发展。现代并行处理技术经 历了从单指令多数据流的阵列机( s i m d ) 、并行向量机( p v p ) 、共享存储的 对称多处理器系统( s m p ) 、分布存储的大规模并行处理系统( m p p ) 到分布共 享存储结构( d s m ) 的并行机系统和计算机集群系统( c l u s t e r ) 的演变过程。 特别是近十年来，c p u 芯片的性能翻了几番，计算机科学家发明了虫蚀寻 径( 、r m h o l e ) 技术，找到了更符合实际的l o g p 及l o g p q 等并行计算模 型，构建了上百种不同规模、不同拓扑结构的并行平台，加之f o r t r a n9 0 和h i g hp e r f o r m a n c ec c + + 等己逐渐成熟的并行编程语言和并行编译系 统，并行计算及并行处理将在社会生活中发挥越来越重要的作用【2 】。 科学与工程计算的许多重要领域如数值天气预报、核物理与流体力学 计算、石油地震数据处理、电力系统优化设计、地球物理勘探、材料模拟 与设计、电磁场计算等都离不开微分方程的数值求解。而其通过有限体积、 有限元或有限差分法等进行离散后最终可以归结为线性方程组特别是稀 疏线性方程组的求解问题。大量的实践经验表明，线性代数方程组的求解 时间在整个问题的总计算时间中占有非常大的比重，如在油藏数值模拟软 件中，其解法器涉及油藏模拟方程离散化后得到的大型稀疏线性代数方程 组的求解，其占据了8 0 以上的计算量，是整个问题计算的瓶颈【3 】。因此 线性代数方程组的高效求解成为计算数学中的重要课题之一。求解线性代 数方程组的存储需求与计算量相当大，为实现其高效性处理，采用并行计 算技术是求解这类问题的必然选择。 求解稀疏线性方程组的方法有直接法和迭代法【4 】二种，直接法中，由 于要对稀疏矩阵进行分解，而在分解过程中将引入许多填充元素( 即非零 元素) ，从而增加存储开销，为了减少这种开销，需要在分解过程中，对 重庆邮电大学硕士论文第一章绪论 矩阵的行与列进行重新排序( 即对矩阵进行置换) ，这就必须为减少填充元 付出一定代价。相对直接法，迭代法的存储开销大大减少，一般地每步迭 代的计算开销与矩阵本身所需的存储开销同量阶。k r y l o v 子空间算法是求 解稀疏线性方程组最流行和最有效的迭代方法之一，也是当前研究的热 点，其主要思想是为各迭代步递归地构造残差向量”】。通常，迭代多项式 的选取应使所构造的残差向量在某种内积意义下相互正交，从而保证某种 极小性( 极小残差性) ，达到快速收敛的目的。k r y l o v 子空间算法的并行形 式主要考虑的是矩阵向量乘积和内积计算【6 墙】。目前，只要适当编码，矩 阵向量乘积在现代并行计算机上不会造成严重性能降低的通信问题，即使 对相对小规模的问题也是这样。但内积计算并非如此，由于内积计算需要 全局通信，在分布式并行计算环境下其成为高效计算的瓶颈。如何减少内 积计算所带来的全局通信开销成为k r y l o v 子空间方法并行算法设计与实 现的研究热点，也是目前的一个挑战【7 ，引。所以研究减少k r y l o v 子空间算 法并行化时内积计算所带来的全局通信开销具有重要意义。 1 2k r y l o v 子空间算法的并行化研究现状 关于k r y l o v 子空间算法的并行化策略，前人已经做了很多工作。k r y l o v 子空间算法的并行形式主要考虑的是矩阵向量乘积和内积计算问题。关于 矩阵向量乘积的问题，对向量多处理机情形，需要使用硬件的聚积一分散 对矩阵向量乘积有效地向量化。在分布式环境中，为极小化通讯和提高负 载平衡，矩阵向量乘积可用块行划分( 可能结合一些数据的预处理) 进行并 行化，还可考虑通信与计算重叠进行，矩阵在处理机上的分布尽量使得只 有邻居一邻居的通信。还有许多处理稀疏矩阵向量乘积的方法，如对具有 多个右端项的方程组，k r y l o v 子空间算法对不同的右端项生成不同的子空 间，可努力构造一个稍微大点的子空间来近似所有不同的子空间的并集， 即所谓块方法。虽然从计算复杂性的观点来看这不是十分有效，因为这样 的子空间通常对任何一个各自方程组都不是最优的，但对并行处理和有限 快速局部存储系统，许多计算可被局部组合，这导致更好的使用局部数据 和更少的通信开销。通过这些方法适当编码，矩阵向量乘积在现代并行计 算机上已经不会造成严重降低性能的通信问题。 关于内积计算的问题，我们既需要归约化操作也需要对聚集的内积广 播进行整体通信，因为所有处理机都需要知道结果。在分步式并行计算环 境下，除预条件外，其成为高效计算的一个重要瓶颈。1 9 8 7 年m e r u r a n t 【9 】 2 讨论了如何减少c g 算法在并行机上的同步开销，19 9 2 年d a z e v e d o 等人 【1 0 】也对c g 算法进行了修改，得到了改进的c g 算法，其主要思想是：将 分离的内积计算通过数学变换，利用可以并行执行的连续内积计算来代 替，从而减少全局通信次数，提高了并行计算效率。19 9 6 年s t u r l e r 【及 19 9 7 年b a s e r m a n n 【1 2 】提出了另一种并行处理内积计算的方法，其基本思想 是：重排迭代法的计算顺序，使解的校正延迟一个迭代步，即解的校正不 必等待内积的计算完成，从而达到计算与通信的重叠，提高了并行计算效 率。2 0 0 1 年m a t h e s w a r a n 等人【1 3 】通过改变c g s 算法的计算顺序，得到 m c g s 算法，改进算法使得同步开销减少为原算法的一半。2 0 0 1 年l a u r e n c e 等人重排迭代法的计算顺序使计算与通信的重叠得到i c g s 【1 4 】算法，2 0 0 2 年他们又提出了一种两项循环l a n c z o s 过程，得到i b i c g s t a b 【1 5 】等算法。 2 0 0 5 年刘杰等人【1 6 j 为提高t f q m r 算法的并行计算效率，给出了i t f q m r 算法。2 0 0 5 年李晓梅等人【7j 对k r y l o v 子空间方法的并行化策略给出总结。 2 0 0 6 年刘杰等人【l 7 】又给出了共轭残差算法的改进形式i c r 算法。2 0 0 8 年 张理涛等人【l8 】对平方共轭残差算法做了改进使其更适合分布式并行计算。 1 3 论文主要工作 本文对采用截断技术和再启动技术的广义共轭残差( g c r ) 算法即 o i 玎h o m i n ( m ) 算法和g c r ( k ) 算法进行了研究并做了一定的改进。本文的 主要工作包括： 1 ) 针对o r t h o m i n ( m ) 算法中内积计算引起的全局通信相对计算时 间比重过大，利用该算法的固有性质改变其计算次序，对该算法做出了改 进，并给出了算法的并行设计。从算法的并行计算时间、加速比、可扩展 性三个方面对改进算法和o r t h o m i n ( m ) 算法进行了理论分析比较，通过 求解油藏数值模拟问题给出数值实验。理论分析及数值实验结果均表明改 进算法比o r t h o m i n ( m ) 算法并行效率要高，同时数值实验结果还表明改 进算法与o r t h o m i n ( m ) 算法具有相同的收敛性，且更利于油藏数值模拟 问题的并行求解。 2 ) 同样针对g c r ( k ) 算法中内积计算引起的全局通信问题，利用与改 进o r t h o m i n ( m ) 算法同样的方法，对g c r ( k ) 算法做出了改进，并给出了 算法的并行设计。同样从算法的并行计算时间、加速比、可扩展性三个方 面对改进算法和g c r ( k ) 算法进行了理论分析比较，通过求解油藏数值模 拟问题给出数值实验。理论分析及数值实验同样表明改进算法比g c r ( k ) 3 本文共分五章，各章节安排如下： 第一章介绍了本文的课题背景、k r y l o v 子空间方法的研究状况、本文 的主要工作及论文结构。 第二章首先介绍了并行计算技术的相关基础理论，包括并行计算机结 构模型，并行计算模型，并行编程模型，并行算法的设计方法及性能度量 等相关知识。然后介绍了k r y l o v 子空间的基本概念、理论和方法并分析了 k r y l o v 子空间方法的基本性质，及其k r y l o v 子空间算法的并行化策略。 第三章讨论了通过k r y l o v 子空间生成g c r 算法的方法。阐述了采用 截断技术的g c r 算法一o r t h o m i n ( m ) 算法及其基本性质，并对该算法进 行了改进。对改进算法和o r t h o m i n ( m ) 算法进行分析比较并通过对油藏 数值模拟问题的求解给出数值实验结果。 第四章阐述了采用再启动技术的g c r 算法一g c r ( k ) 算法及其基本性 质，并对该算法进行了改进。对改进算法和g c r ( k ) 算法进行分析比较， 同样通过对油藏数值模拟问题的求解给出数值实验结果。 第五章为全文结论，并对进一步研究工作做出讨论和展望。 4 重庆邮电大学硕士论文第二章并行计算及脚l o v 子空间算法 2 1 引言 第二章并行计算及k r y l o v 子空间算法 并行计算技术汇集了从计算机硬件到数学方法等众多学科的精华，以 实现高计算性能为最终目的。并行软件和并行计算机构成了并行计算的 软、硬两个基本内容。并行计算的进展在各个方面呈现出不平衡性，总的 看来：软件落后于硬件，数据传输速度落后于数据处理能力。在硬件方面， 存储器技术发展不能满足处理器速度的增长；相对处理器和内存储器而 言，外存储系统研究长期被忽视；i o 速度与c p u 速度严重不匹配使i o 瓶颈问题日益严重【19 1 。并行通信系统的发展也不平衡，其最重要的两个技 术指标一传输带宽的增长与启动时延的改进速度相差近十倍，尤其是消息 传递的启动时延( 也常称为系统开销) 长期以来居高不下，它既是并行系统 设计的技术难点，也是应用软件设计中所要关注的焦点之一。随着硬件速 度的不断提高，对并行程序设计及其并行软件开发的需求日益迫切。 科学与工程计算中的许多问题如油藏数值模拟、天气预报、结构分析、 地球物理勘探等都可以归结为求解线性方程组问题。k r y l o v 子空间方法是 求解稀疏线性方程组最流行和最有效的迭代方法之一，也是当前研究的热 点。随着科学计算技术的发展，求解问题的规模越来越大、复杂性越来越 高，单处理机的计算已不能适应各领域科学计算的发展，应用问题的并行 化是必由之路，研究求解大型稀疏线性方程组的高效并行算法十分重要。 因此研究求解稀疏线性方程组的有效迭代法一k r y l o v 子空间算法的并行 化策略也变得尤为重要。本章从并行计算机模型和并行算法设计两方面对 并行计算技术基础理论进行了论述。同时讨论了k r y l o v 子空间概念及算 法，分析了k r y l o v 子空间方法的基本性质及其算法的并行化策略。 2 2 并行计算机模型 2 2 1 并行计算机结构模型 并行计算机体系结构是指并行处理系统( 主要是分布式系统) 中处理机 或节点机之间的互连方式。由于在不同的结构上实现相同的并行算法时， 5 重庆邮电大学硕士论文第二章并行计算及l 畸l o v 子空间算法 处理机间的通信问题是截然不同的。因此，并行计算机体系结构严重影响 着并行算法的实现效率，导致不同算法适合的最佳体系结构有所不同。大 型并行机系统一般可分为六类【2 0 ，2 1 1 ，简述如下。 1 ) 单指令多数据流系统s i m d 这是计算机体系结构历史上的一个重要分类，对于数据并行类问题， 这类计算机能够达到很高的处理速度。s i m d 计算机有一个指令流，可能 有多个单元在执行，然而在任何时间点只有一条指令在执行。所以该类计 算机的主要特征是：同步的，确定的，适合指令操作级并行。s i m d 计算 机多为专用，处理机阵列和流水线向量机属于该类计算机。 2 ) 并行向量处理机 并行向量处理机p v p ( p a r a l l e lv e c t o rp r o c e s s o r ) 系统中使用了专门设计 的高带宽的交叉开关网络将向量处理器v p 连向共享存储模块，存储器可 以兆字节每秒的速度向处理器提供数据。这样的机器通常不使用高速缓 存，而是使用大量的向量寄存器和指令缓冲器。c r a yc 9 0 、c r a yt 9 0 、 n e cs x 4 和我国的银河1 号等都是p v p 。 3 ) 对称多处理机 对称多处理机s m p ( s y m m e t r i cm u l t i p r o c e s s o r ) 系统使用商品微处理器 ( 具有片上或外置高速缓存) ，它们经由高速总线( 或交叉开关) 连向共享存储 器。这种机器最大特点是系统对称。由于这个特性，每个处理器可等同地 访问共享存储器、i o 设备和操作系统服务，这为开拓较高的并行度开创 了前提。现在，多核处理器的p c 机可以看作是一种廉价的s m p ，这也为 s m p 赢得了广阔的市场空间。i b mr 5 0 、s g ip o w e rc h a l l e n g e 、d e ca l p h a 服务器8 4 0 0 和我国的曙光l 号等都是这种类型的机器。 4 ) 大规模并行处理机 大规模并行处理机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 ) 一般是指超大型 ( v e r yl a r g e s c a l e ) 计算机系统。它具有如下特性：处理节点采用商品微 处理器；系统中有物理上的分布式存储器；采用高通信带宽和低延迟 的互连网络( 专门设计和定制的) ；能扩放至成百上千乃至上万个处理器； 它是一种异步的m i m d 机器。程序系由多个进程组成，每个都有其私有 地址空间，进程间采用传递消息相互作用。m p p 的主要应用是科学计算、 工程模拟和信号处理等以计算为主的领域。i n t e lp a r a g o n 、c r a vt 3 e 、i n t e l t f l o p s 和我国的曙光1o o o 等都是这种类型的机器。 5 ) 工作站机群 工作站机群c o w ( c l u s t e ro fw o r k s t a t i o n s ) 的特征是：c 0 w 的每个 6 重庆邮电大学硕士论文第二章并行计算及脚1 0 v 子空间算法 节点都是一个完整的工作站( 不包括监视器、键盘、鼠标等) ，这样的节点 有时叫做“无头工作站”，一个节点也可以是一台p c 或s m p ；各节点通 过一种低成本的商品( 标准) 网络( 如以太网、f d d i 和a t m 开关等) 互连( 有 的商用机群也使用定做的网络) ：各节点内总是有本地磁盘，而m p p 节 点内却没有；节点内的网络接口是松散耦合到i o 总线上的，而m p p 内 的网络接口是连到处理节点的存储总线上的，因而可谓是紧耦合式的； 一个完整的操作系统驻留在每个节点中，而m p p 中通常只是个微核，c o w 的操作系统是工作站u n i x 加上一个附加的软件层，以支持单一系统映像、 并行度、通信和负载平衡等。b e r k e l e yn o w 、a 1 p h af a r m 、d i g i t a lt r u c l u s t e r 等都是c o w 结构，在有些情况下，机群往往是低成本的变形的m p p 。 6 ) 分布共享存储多处理机 分布式共享存储多处理机d s m ( d i s t r i b u t es h a r e dm e m o r y ) 具有高速缓 存目录d i r ，其用以支持分布高速缓存的一致性。d s m 和s m p 的主要差 别是，d s m 在物理上有分布在各个节点中的局部存储器，从而形成了一个 共享的存储器，这样就形成了一个单地址的编程空间，方便实现。s t a n f o r d d a s h 、g r a yt 3 d 和s g i c r a y0 r i g i n 2 0 0 0 等属于此类结构。 2 2 2 并行计算模型 并行计算模型是对并行计算机特征性能的抽象，因而也可称为抽象机 模型。它是连接并行算法和并行计算机间的桥梁，也是并行算法设计者从 事算法设计的抽象平台。并行计算模型能够足够准确地给出并行计算机的 特征参数，提供体系结构与并行算法之间的接口，使得跨平台的算法移植 成为可能，同时也能够有效的预测并行算法的预期性能。由于并行机体系 结构具有多样性，不存在类似串行计算中的“冯诺依曼”( v 0 nn e u m a n n ) 模型这样统一的计算模型。在并行计算领域存在多种并行计算模型，主要 包括p r a m ，l o g p 和b s p 模型等。各种并行计算模型可在同构性、同步性、 交互机制、地址空间和存储器模型等语义属性上加以区别。其中同构性描 述各处理器行为的相似程度，交互机制主要是指进程间的通信方式。依据 并行计算模型应能够预测并行算法的相对代价，因而它必须包括刻划并行 平台性能的基本属性，如机器规模、工作负载等。对于分布式存储环境下 消息传递并行而言，启动时间如和渐进带宽名( m b s ) 是两个重要的性能属 性。依据h o c k n e y 时间模型，二者决定了点到点通信开销f 。= 气+ 朋乞其中 聊为消息长度。 7 重庆邮电大学硕士论文第二章并行计算及k d r i o v 子空间算法 p r a m ( 并行随机访问机) 模型是共享存储的s i m d 模型，假定存在容量 无限的共享存储器，多处理机可通过共享变量( 共享存储器) 进行通信，处 理机个数没有限定。p r a m 模型的优点就在于其简单性，它将并行进程间 的通信、同步和存储管理等细节隐藏起来，使得依据它设计算法简单易行， 因此p r a m 模型至今