（系统分析与集成专业论文）矩阵运算中矩阵规模与处理器个数问题研究.pdf

摘要 随着超级计算需求的扩大，人们把高性能计算更多的应用于数据挖掘应用、 图像处理业务、基因测序比对处理、过程控制、气象检测等大型数据处理领域。 科学计算的规模迅速膨胀，使得传统的串行计算机已经不能满足需求，从而提出 了并行计算的概念。 在谈到并行计算之前，我们先谈一下并行计算机，并行计算机是指有多个处 理器的计算机，只有一个处理器的计算机称为串行机，在串行机上进行的计算称 为串行计算，在并行计算机或者通过网络共享方式模拟的并行计算机环境下进行 的运算称为并行计算。它将进程相对独立的分配于不同的节点上，由各自独立的 操作系统调度，享有独立的c p u 和内存资源；进程间通过消息传递相互交换信息。 m p i 是1 9 9 4 年5 月发布的一种消息传递接口，是为消息传递程序提供的标 准库1 1 1 。m p i 以语言独立的形式来定义这个接口库，并提供了与c 和f o r t r a n 语 言的绑定，是目前高效率的超大规模并行计算最可信赖的平台。 目前，i n t e r n e t 连接着大量的个人p c 机和各种超级计算机，汇集了大量的计 算资源。为了利用i n t e m e t 上广泛分布的空闲计算资源，目前已经有多个分布式 计算项目，比如：s e t i h o m e ，g i m p s 等等。这些项目已经证实了这种计算模 型的可行性。不过这些系统的资源高度不稳定、用户不可信任、通信带宽有限、 延迟巨大。 本文在分析了当前国内外并行运算矩阵运算的有关算法后提出了一些算法 研究结论和改进建议，并在网络环境下通过共享的方式模拟并行机，运用m p i 方式编程测试，用测试结果来验证研究结论的正确性、实用性、可行性。着重讨 论了当矩阵规模远大于处理器个数的情况下的矩阵运算。 关键字：并行运算矩阵运算m p i a b s t r a c t w i t ht h eg r o w i n gd e m a n df o rs u p e rc a l c u l a t i o n ，p e o p l ea p p l i e dt h e h i g hp e r f o r m a n c e c o m p u t i i l gt ot h ed a t am i n i n ga p p l i c a t i o n ，i m a g ep r o c e s s i n g ，g e n es e q u e n c i n gn l a w h i n g 仃e a 仃i l e n t ， p r o c e s sc o n t r o la n dm e t e o r o l o g i c a ld a t ap r o c e s s i n gf i e l d t e s te r e t h er a p i de x p a n s i o no fs c i e n t i f i c c o m p u t m g ，m a k et h et r a d i t i o n a ls e r i a lc o m p u t e ra l r e a d yc a n n o ts a t i s f yt h er e q u i r e m e n t ，i tp u t s f o r w a r dt h ec o n c e p to fp a r a l l e lc o m p u t i n g b e f o r et h ep a r a l l e lc o m p u t i n g ，w e l lt a l ka b o u tp a r a l l e lc o m p u t e r t h ep a r a l l e lc o m p u t e r i st h e c o m p u t e rw h i c hh a sm u l t i p l ep r o c e s s o r s t h ec o m p u t e rw h i c hh a so n l yo d e p r o c e s s o rw ec a l l e d s e d a ln l a c h i n e ，i ns e r i a lk i l l i n gc a l c u l a t i o n sc a l l e ds e r i a l c a l c u l a t i o n ，i np a r a l l e lm a n n e r , 0 r t h r o u g ht h en e t w o r kc o m p u t e rs i m u l a t i o np a r a l l e lc o m p u t e re n v i r o n m e n to p e r a t i o n c a l l e dp a m l l e l c o m p u t i n g i tw i l lp r o c e s sr e l a t i v e l yi n d e p e n d e n ta m o n g d i f f e r e n tn o d e s ，b yi l l d e p e n i i e n to p e n l t i o n s v s t e ms c h e d u l e r , e n j o yt h ec p ua n dm e m o r yr e s o u r c e si n d e p e n d e n t l y , t h r o u g ht h ep r o c e s so f e x c h a n g i n gm e s s a g e sb e t w e e n i n f o r m a t i o n m p lw a sp u b l i s h e di nm a y19 9 4 ，i tw a sam e s s a g er e l a yi n t e r f a c e ，w h i c hw a sd e s i g n e df o r m e s s a g er e l a y i tw a sas t a n d a r dl i b r a r y m p i h a si t si n d e p e n d e n tl a n g u a g ew h i c hs u p p o r ti t s j n t e r f a c el i b r a r y , a n dp r o v i d e dc f o r t a n ，i tw a s c u r r e n te f f i c i e n c yo fl a r g es c a l ep a r a l l e lc o m p u t i n g s m o s tt r u s t e dp l a t f o r m c 唧n t l y , t h e r ea r el o t so fi n d i v i d u a lp c sa n dv a r i o u ss u p e rc o m p u t e r i nt h ei n t e r a c t ，w i t ha l a r g ec o l l e c t i o no fc o m p u t i n gr e s o u r c e s ，i no r d e r t ou s et h eh u g er e s o u r c e ，n o wt h e r ea r em u l t i p l e d i s 舶u t e dc o m p u t i n gp r o j e c t s ，e g ：s e t i h o m e ，g i m p sa n d s oo n t h ep r o j e c th a sb e e np m v e d t h ef e a s i b i l i t yo ft h i sc a l c u l a t i o nm o d e l , b u tt h e s es y s t e mh a ss o m ef a u l t s ：s y s t e mr e s o u r c eh i g h l y u n s t a _ b l e u s e r _ sd on o tt r u s t ，l i m i t e dc o m m u n i c a t i o n sb a n d w i d t h ，h u g ec o m m u n i c a t i o n d e l a y b a s e do nt l l ea n a l y s i so ft h ec u r r e n td o m e s t i ca n di n t e m a t i o n a lp a r a l l e lc o m p u t i n gm a t r i x 叩e m t i o na f t e rt h ea l g o r i t h mp r o p o s e ds o m es u g g e s t i o n st oi m p r o v ea n da 1 9 0 r i m m i i ln e m o r k e n v i r o 姗e n t ，a l l ds h 锄_ e db yw a yo fu s i n gm p ip a r a l l e l s i m u l a t i o na n dt e s t ，t h ew a yw i t h p r o g r a m i n i n gt e s tr e s u l t st ov e r i f yt h ec o r r e c t n e s so f t h er e s e a r c hr e s u l t sa n dp r a c t i c a la n df e a s i b l e k e y w o r d s ：p a r a l l e lc o m p u t i n g m a t r i xc o m p u t i n gm p i 湖北大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取 得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其 他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果 由本人承担。 论文作者签名：障傍彳争 醐：1 泪 学位论文使用授权说明 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即： 按照学校要求提交学位论文的印刷本和电子版本；学校有权保存并向国家有关部门 或机构送交论文的复印件和电子版，并提供目录检索与阅览服务；学校可以允许采用影 印、缩印、数字化或其它复制手段保存学位论文；在不以赢利为目的的前提下，学校可 以公开学位论文的部分或全部内容。( 保密论文在解密后遵守此规定) 作者签名： 障f 毒碲日期：力呷年，月乡眇日 艚刻醛名兽彬移醐”， 引言 引言 4 0 年代开始的现代计算机发展历程可以分为两个明显的发展时代：串行计算 时代、并行计算时代。每一个计算时代都从体系结构发展开始，接着是系统软件 ( 特别是编译器与操作系统) 、应用软件，最后随着问题求解环境的发展而达到顶 峰。 对于可扩展的并行计算机体系结构根据指令流和数据流的不同，可把计算机 系统分为：单指令流单数据流、单指令流多数据流、多指令流单数据流、多指令 流多数据流，按同时执行的程序和数据的不同，可把计算机系统分为：单程序单 数据并行计算机、单程序多数据并行计算机、多程序单数据并行计算机、多程序 多数据并行计算机。五种实际并行计算机物理模型为：并行向量机、对称多处理 机、大规模并行处理机、工作站机群、分布共享存储多处理机。创建和使用并行 计算机的主要原因就是因为并行计算机是解决单处理器速度瓶颈的最好方法之 但是高性能计算机的昂贵价格，使得高性能计算仍然只能停留在高端领域，严重 限制了并行计算的发展，目前，硬件技术的快速发展促进了超级计算走向并行计 算。但是在并行计算领域，相对于硬件，并行软件技术几十年来没有获得突破性 的进展。特别是分布式计算技术，自动并行识别技术等，软件技术的缓慢发展阻 止了并行计算走向中低端。 并行编程要达到良好的可编程性，必须解决结构性、通用性和可移植性问题。 并行编程的可编程性和用户并行编程能力的提高是走向普及的两个方面，网络并 行计算软件环境是现代并行计算的关键技术之一【2 1 。并行编程的最大的难题是要 解决数据依赖和控制依赖问题，几十年来始终处于研究过程中，没有达到 m s d o s 到w i n d o w s 量级的提高，令用户失望。 m p i 是为消息传递程序提供的标准库，由标准消息传递函数及相关辅助函数 构成，进程通过调用这些函数( 类似调用子程序) 进行通信。m p i 以语言独立的形 式来定义这个接口库，并提供了与c 和f o r t r a n 语言的绑定，是目前高效率的超 大规模并行计算最可信赖的平台。 m p i 提供了一种与语言和平台无关、可以被广泛使用的、编写消息传递程序 的标准，用它来编写消息传递程序实用、可移植、高效和灵活，为并行软件技术 湖北大学硕十学位论文 的发展提供了一个良好的平台【3 1 。 本文的所有程序设计都是在m p i 的环境下用v c 进行编写和测试、运行。本文讨论的 重点是在局域网环境下构建并行机环境，并讨论当矩阵规模远人于处理器个数的情况下如何 用带状划分实现矩阵的乘法运算，提高算法的运行效率。 2 第一章并行计算简介 第一章并行计算简介 1 1 从超级计算到高性能计算 超级计算，从技术上的意义上来说，是为了在问题的求解上追求更快的速度、 更高的精度、更大的规模、更高的性价比而采用的非主流计算的设备和方式。计 算速度是第一追求目标。 超级计算主要用于科学计算。早期的应用仅涉及格点差分模式计算( 气象预 报软件m m s ) ，有限元计算，空气动力学分析。几乎和数据处理无关。 超级计算中标准测试( b e n c h m a r k ) 的重点为浮点运算速度测试，包括如下几个 标准： 1 1 9 7 6 年发布的d h r y s t o n e ，主要用于测整数计算能力，计算单位是d m i p s 。 2 1 9 7 6 年发布的w h e t s t o n e ，主要用于测浮点计算能力，计算单位是 m f l o p s 。 3 1 9 8 0 发布的l i n p a c k ，为解线性方程和线性最小二乘问题的子程序包。主 要用于测浮点计算能力。 随着超级计算需求的扩大，上世纪8 0 年代初期出现了小巨机的概念，随着 超级计算应用面的扩大，上世纪8 0 年代后期又出现了高性能计算的概念，把超 级计算推向了各个领域，超级计算追求的单一计算指标也转变成为追求高性能的 综合指标。 1 2 高性能计算应用领域的变迁 目前，科学和工程问题的数值模拟与仿真问题日益呈现以下显著特点： 计算密集； 数据密集； 网络密集； 并且要求在合理的时限内完成计算任务。见表1 1 3 湖北人学硕士学位论文 秒级制造业 分钟级短时天气预报( 当天) 小时级 中期天气预报( 3 1 0 天) 尽可能快 长期大气预报( 气候) 可计算湍流模拟 表卜1 任务计算时限 数据库技术的成熟，生物基因技术的发展，历史数据的几何级膨胀使人们把 高性能计算更多的应用于数据挖掘应用、图像处理业务、基因测序比对处理等数 据处理领域。随着科学计算规模的迅速膨胀，使得传统的串行计算己经不能满足 要求，从而提出了并行计算的概念。如下图1 1 所示： 存储嚣器量 1 3 并行计算的概念 图卜1 科学计算的规模的发展 并行计算，是相对于串行计算来讲的。简单的说，并行计算就是在并行计算 机上进行的运算，并行计算机就是由多个处理单元( 以下也简称为处理器或者 c p u ) 组成的计算机系统，这些处理单元相互通信和协作，能快速、高效地解决 4 一 耋塞 懈 饼 一 懈 第一章并行计算简介 大型复杂问题。 传统的串行运算，分为“指令”和“数据”两个部分，在程序执行时“独立 地申请和占用”内存空间，并且所有计算都局限于该内存空间。如图1 2 所示： 厂j ； 避年蟹1 i ； 。 、。 ：二薨缓幽一 ：二蓊缓缓燃一 图卜2 串行运算 所谓并行运算分为时间上的并行和空间上的并行。时间上的并行就是指流水 线技术，而空间上的并行则是指用多个处理器并发的执行运算。并行计算将进程 相对独立的分配在不同的节点( 处理器) 上，由各自独立的操作系统进行调度， 享有独立的c p u 和内存资源( 内存可以共享) ；进程间通过消息传递相互交换信 息。如下图1 3 所示： = j 二。三 图1 - 3 并行运算 1 4 可扩展的并行计算机体系结构 1 4 1 根据指令流和数据流的不同的计算机系统分类 1 4 1 1 单指令流单数据流( s i s ds i n g l ei n s t r u c t i o ns i n g l ed a t a ) 这是传统的冯诺依曼串行机概念，一次只执行一条指令。s i s d 也常被称 为串行标量计算机( s e r i a ls c a l a rc o m p u t e r ) 。当今，s i s d 计算机已经被整体淘汰了。 即使是个人计算机或单片机也实现了一定的并行性以取得较高的性能，现行的 c p u ，大多数情况下，它们能同时执行两条或更多的指令【4 1 。 1 4 1 2 单指令流多数据流( s i m ds i n g l ei n s t r u c t i o nm u l t i p l e d a t a ) 5 湖北大学硕士学位论文 它是指单一指令同时对不同的数据进行同一操作。在这样的机器中，单一的 控制部件操纵多个分开的处理部件。s i m d 机器能支持向量处理，它在单一控制 部件操纵下分派向量元素到各个处理部件并行完成任务计算。p e n t i u mm m x 和 p e n t i u mi i i i iw 等处理器，在多媒体数据处理过程中即呈现出这种s i m d 结构， 一条m m x 指令可以对打包数据中的2 个、4 个或8 个以上数据同时进行操作。 1 4 1 3 多指令流单数据流( m i s dm u l t i p l ei n s t r u c t i o ns i n g l e d a t a ) 它的直接含义是几个指令对同一数据片操作。有两种方式来解释m i s d 类机 器的组织。一种方式是：它有几个处理部件能接收几个不同的指令对同一数据进 行操作，这己被证明是不可能的也无实际意义和必要：另一种方式是考虑让数据 流通过一串处理部件，像向量处理机和搏动式阵列( s y s t o l i ca r r a y ) 这样的高度 流水线式结构，可以被认为是属于这种方式的m i s d 结构。流水线结构通过一系 列阶段( 段或步) 来完成向量处理，每一段完成一个具体的功能并产生一个中间结 果。流水线的各个段代表施加于这个向量的多个指令，向量的各个元素可以认为 是属于同一数据片：因此可看作是m i s d 结构。 1 4 1 4 多指令流多数据流( m i m dm u l t i p l ei n s t r u c t i o nm u l t i p l e d a t a ) 它是指机器有多个处理部件，多条指令能同时对不同的数据进行处理。多处 理机系统、多计算机系统和数据流计算机都可算作此类。这类机器通过并行处理 实现最大的效能。并行不仅指多个处理器同时操作，而且指多个程序( 进程) 在同 一时间片被执行。多处理机和多计算机之间的主要差别在于存储器共享和处理机 间通信机制的不同。多处理机系统中的处理机通过公用存储器的共享变量实现相 互通信。多计算机系统中的每个处理机有只属于本结点的本地存储器，处理机之 间的通信通过结点间的消息传递来实现。数据流计算机的指令由操作包和数据令 牌组成，用数据令牌传送数据和激活指令。它的指令不是在中央控制器控制下顺 序执行的，而是在数据的可用性控制下并行执行的，故也将其划入m i m d 类。 p e n t i u mi i i i i 处理器实现了指令的乱序执行，即：够执行条件的数据不分先后 可激活该指令的执行。 6 第一章并行计算简介 数据个 s 图1 - 4 根据指令流和数据流 指令个数m 1 4 2 按同时执行的程序和数据的不同的计算机系统分类 按同时执行的程序和数据的不同进行分类，我们把并行计算机系统可以分 为：单程序单数据并行计算机( s p s ds i n g l ep r o g r a ms i n g l ed a t a ) 、单程序多数 据并行计算机( s p m ds i n g l ep r o g r a mm u l t i p l ed a t a ) 、多程序单数据并行计算机 ( m p s dm u l t i p l ep r o g r a ms i n g l ed a t a ) 、多程序多数据并行计算机( m p m d m u l t i p l ep r o g r a mm u l t i p l ed a t a ) 。 其中多程序多数据流，除初始启动多个可执行代码，其它与s p m d 模式一样。 1 4 3 五种实际物理机模型 并行计算机系统除少量专用的s i m d 系统外，绝大部分为m i m d 系统，实际的 机器体系结构包括： 1 4 3 1 并行向量机( p v p p a r a l l e lv e c t o rp r o c e s s o r ) 典型的并行向量处理机的结构如下图1 7 ，c r a yc 9 0 、c r a yt - 9 0 、n e cs x 4 和我国的银河1 号等都是p v 。系统中专门设计定制的向量处理器v p ，每个至少 具有1 g f l o p s 的处理能力，专门设计定制的高带宽交叉开关网络与共享存储模块 连接起来，一般不使用高速缓存，而是使用大量的向量寄存器和指令缓冲器。 7 湖北大学硕七学位论文 总线 图卜7 并行向量机( v p - 向量处理器s m - s h a r em e m o r y 共享存储器) 1 4 3 2 对称多处理机( s m ps y m m e t r i cm u l t i p r o c e s s o r ) 典型的对称多处理机结构如下图1 8 。s m p 系统一般使用商品化微处理器 ( r m 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 等) ，具有片上或外置高速缓存， 经由高速总线( 或交叉开关) 连向共享存储器。每个处理器可等同地访问共享存储 器、i o 设备和操作系统服务【5 】。s m p 的主要特点是：单一操作系统映像，全系统 只有一个操作系统驻留在共享存储器中，它根据各个处理器的负载情况，动态地 分配各个进程到各个处理器，并保持各个处理器间的负载平衡；低通信延迟，各 个进程通过读写操作系统提供的共享数据缓存区来完成处理器间的通信，其延 迟通常小于网络通信延迟；共享总线带宽，所有处理器共享总线带宽，完成对内 存模块和i 0 模块的访划6 1 。同时，s m p 也具有如下一些问题：欠可靠，总线、存 储器、操作系统失效可能导致系统崩溃；可扩展性较差，由于所有处理器都共享 总线带宽，而总线带宽每3 年才增加2 倍，赶不上处理器速度和存储容量的增长 步伐，因此s m p 的处理器个数一般少于6 4 个，且只能提供每秒数百亿次的浮点 运算。 图1 - 8 对称多处理机 p c ( m i c r o p r o c e s s o ra n dc a c h e ) 微处理器和高速缓存 s m ( s h a r e dm e m o r y ) 共享存储器 8 第一章并行计算简介 1 4 3 3 大规模并行处理机( m p pm a s i v e l yp a r a l l e lp r o c e s s o r ) m p p 一般采用商品化微处理器和专门设计的互连网络，它具有如下几个特 性：处理节点采用商品微处理器；系统中有物理上的分布式存储器；采用 高通信带宽和低延迟的互连网络( 专门设计和定制的) ；系统可以扩展到数千 个甚至更多个处理器【7 】；它是一种异步的m i m d 机器，程序系由多个进程组成， 每个都有其私有地址空间，进程间采用传递消息相互作用。m p p 的主要应用是 科学计算、工程模拟和信号处理等以计算为主的领域。其机构图如下图1 - 9 。一- - 。i一一 - _ _ - _ - - _ - o 图1 9 大规模并行处理机 p c ( m i c r o p r o c e s s o ra n dc a c h e ) 微处理器和高速缓存 m b ( m e m o r yb u s ) 存储器总线 n i c ( n e t w o r ki n t e r f a c ec i r c u i t r y ) 网络接口电路 l m ( l o c a lm e m o r y ) 本地存储器 1 4 3 4 工作站机群( c o wc l u s t e ro fw o r k s t a t i o n ) c o w 的每个系统都是一个完整的工作站，一个节点可以是一台p c 或s m p ， 各个节点一般由商品化的网络互连，每个节点一般有本地磁盘，节点上的网络接 口是松散藕合到i o 总线上的，在每个节点上驻留一个完整的操作系统【8 1 。本文 中所使用的并行机环境就是一个基于局域网的工作站机群环境。其结构如下图 】0 9 湖北大学硕十学位论文 图卜1 0 工作站机群 m ( m e m o r y ) 内存 b ( b u s ) 总线 l d ( l o e a l d i s k ) 本地硬盘 m b ( m e m o r y b u s ) 存储器总线 n i c ( n e t w o r k i n t e r f a e e c i r e u i t r y ) 网络接口电路 p c ( m i c r o p r o c e s s o r a n d c a e h e ) 微处理器和高速缓存 i o b ( i o b u s ) i o 总线 1 4 3 5 分布共享存储多处理机( d s md i s t r i b u t e ds h a r e dm e m o r y ) 高速缓存目录d i r 用以支持分布高速缓存的一致性。处理器对物理分布的共 享存储器的访问是不对称的，这也是d s m 与s m p 的区别所在阻3 。 d s m 具有如下主要特征： 物理上分布存储。内存模块局部在各个节点上，并通过高速互连网络互 连，避免了s m p 访问总线的带宽瓶颈，增强了并行机的可扩展能力： 单一内存地址空间。尽管内存模块分布在各个节点上，但是所有这些内 存模块都由硬件进行了统一编址，并通过互连网络形成了并行机的共享 】0 第一章并行计算简介 存储器。各个节点既可以访问自己的局部内存单元( 本地访问) ，又可以 直接访问其他节点的局部内存单元( 远端访问) ： 非一致内存访问模式( n u m a ，n o n u n i f o r m m e m o r y a e c e s s ) 。由于远 端访问必须通过高性能互连网络，而本地访问只需要直接访问局部内存 模块，因此远端访问延迟一般是本地访问延迟的3 倍以上： 单一的系统映像。类似于s m p ，在d s m 中，用户只看到一个操作系统， 它可以根据各节点的负载情况，动态地分配进程： 基于c a c h e 的数据一致性通常采用基于目录的c a c h e 一致性协议来保 证各节点的局部c a c h e 数据和存储器中数据的一致性。同时，这种d s m 也称为高速缓存相关的非致性内存访问( c c n u m a ， c a c h e c o h e r e n t n o n u nif o r m m e m o r y a e e ess ) 结构。 d s m 较好地改善了s m p 的可扩展性能。一般地，d s m 可以扩展到上百个节点， 能提供每秒数千亿次的浮点运算功能。但由于受c a c h e 一致性要求和互连网络性 能的限制，当节点数目进一步增加时，d s m 并行机的性能也将大幅下降。其结构 图如下图1 - 1 1 ： 。一一。1。4 + 一。一。一。、 m b：m b： 图1 - 1 1 分布共享存储多处理机 d i r ( c a c h ed i r e c t o r y ) 高速缓存目录 l m ( l o e a l m e m o r y ) 本地存储器 m b ( m e m o r y b u s ) 存储器总线 n i c ( n e t w o r k i n t e r f a e e c i r e u i t r y ) 网络接口电路 p c ( m i e r o p r o c e s s o r a n d c a e h e ) 微处理器和高速缓存 湖北大学硕士学位论文 综上所述，除了近来逐步完善并走向实用化的数据流计算机之外，5 0 年来 计算机系统结构虽取得重大进展，但并没有发生革命性的变化，现已实用化的计 算机仍是以冯诺依曼机器为原型，在此基础上加入并提高并行处理实现的手段 和并行处理的能力。 s m p 、m p p 、d s m 和c o w 等并行结构趋向融合，d s m 是s m p 和m p p 的 自然结合，m p 和c o w 的界限逐渐模糊【1 0 1 。在中国现在使用p v p 并行向量机很 少，使用最多的是s m p 、d s m 、c l u s t e r 架构的并行计算机。国内主要的高性能 计算机厂商如曙光、联想、浪潮生产的都是c l u s t e r 架构的并行计算机。节点为 2 4 个处理器的s m p ，互连网络为千兆网、m y r i n e t 等，节点操作系统一般为l i n u x 。 和s m p 、d s m 等相比，集群在较低的费用下，具有高性能、可扩展性、高 吞吐量、易用性等特点【1 1 1 。按照应用目的( 科学计算商业计算) 分类，集群可分为 高性能集群和高可用集群；按照节点硬件分类，可以分为p c 集群、工作站集群、 s m p 集群；按照节点操作系统分类，可以分为l i n u x 集群、n t 集群等；按照节 点体系结构和操作系统的类型，可分为同构集群、异构集群等。 1 5 并行计算机硬件结构抽象模型( 自然模型) 并行计算机硬件结构抽象模型包括： 1 共享存储的模型和语言( 适于s m p ) a n s ix 3 h s 0 ，o p e n m p t l 2 】 2 消息传递的模型和语言( 适于m p p 、c l u s t e r 、c o w ) m p i ( f o r t r a n ，c ) p v m ( f o r t r a n ，c ) 3 数据并行的模型和语言( 适于在m p p c l u s t e r 上实现、s p m d 应用) h p f ( h i g hp e r f o r m a n c ef o r t r a n ) f o r t r a n9 0 4 基于程序构造的模型c s pl i n d a ( f o r t r a n ，c ，g a u s s i a n ) g l o b a l ( m o l p r o ， c o l u m b u s ) 5 基于问题描述的模型和语言g a m m au n i t y 6 基于并行计算理论的模型p r a i v lb s pl o g p 1 6 并行计算机的发展 并行计算机是由一组处理单元组成的，这组处理单元通过相互之间的通信 1 2 第一章并行计算简介 与协作，以更快的速度共同完成一项大规模的计算任务。因此，并行计算机的两 个最主要的组成部分是计算节点和节点问的通信与协作机制。并行计算机体系结 构的发展也主要体现在计算节点性能的提高以及节点间通信技术的改进两方面。 从8 0 年代开始，微处理器技术一直在高速前进。稍后又出现了非常适合于 s 方式的总线协议，而伯克利加州大学则对总线协议进行了扩展，提出了 c a c h e 一致性问题的处理方案【1 3 】。从此，c m m p 开创出的共享存储多处理器之路 越走越宽。现在，这种体系结构已经基本上统治了服务器和桌面工作站市场。 同一时期，基于消息传递机制的并行计算机也开始不断涌现。8 0 年代中期， 美国加州理工成功地将6 4 个i 8 0 8 6 i 8 0 8 7 处理器通过超立方体互连结构连结起 来。此后，便先后出现了i n t e l i p s e 系列、i n m o s t r a n s p u t e r 系列、i n t e l p a r a g o 以 及i b m s p 的前身v u l c a n 等基于消息传递机制的并行计算机。 8 0 年代末到9 0 年代初，共享存储器方式的大规模并行计算机又获得了新的 发展。i b m s 将大量早期r i s c 微处理器通过蝶形互连网络连结起来。人们开始 考虑如何才能在实现共享存储器缓存一致的同时，使系统具有一定的可扩展性 ( s c a l a b i l i t y ) 。9 0 年代初期，斯坦福大学提出了d a s h 计划，它通过维护一个保 存有每一缓存块位置信息的目录结构来实现分布式共享存储器的缓存一致性。后 来，i e e e 在此基础上提出了缓存一致性协议的标准。 9 0 年代以来，主要的几种体系结构开始走向融合。属于数据并行类型的 c m 5 除大量采用商品化的微处理器以外，也允许用户层的程序传递一些简单的 消息。c r a y t 3 d 是一台n u m a 结构的共享存储型并行计算机，但是它也提供 了全局同步机制、消息队列机制，并采取了一些减少消息传递延迟的技术。 随着商品化微处理器、网络设备的发展，以及m p 工p v m 等并行编程标准 的发布，集群架构的并行计算机出现。i b m s p z 系列机群系统就是其中的典型代 表。在这些系统中，各个节点采用的都是标准的商品化计算机，它们之间通过高 速网络连接起来。 今天，越来越多的并行计算机系统采用商品化的微处理器加上商品化的互连 网络构造，这种分布存储的并行计算机系统称为集群。国内几乎所有的高性能计 算机厂商都生产这种具有极高性能价格比的高性能计算机。并行计算机从此进入 了一个新的时代，并行计算的应用达到了前所未有的广度和深度。 1 3 湖北人学硕十学位论文 1 7 本章小结 本章从并行计算的角度出发，着重讨论了当代科学和工程计算问题中说要求 的高性能并行计算机系统，包括并行计算机系统的互连技术、并行计算机的系统 结构模型、存储访问模型和存储结构模型。值得注意的是，所介绍的并行计算机 系统，与计算机体系结构或并行处理技术等的出发点不一样，着重介绍了并行计 算的分类和物理模型。本文中说采用的是c o w ( 工作站机群) ，对并行计算机的讨 论也只是点到为止，没有进行很深入的研究讨论。 1 8 论文的主要内容 论文针对并行环境下矩阵运算过程中矩阵的规模过大，而实际中并行机处理 器的个数在小于或者远小于矩阵的规模( 或者基于局域网环境下模拟并行机环 境) 时运算算法的研究和性能改进，所做的工作主要有g ( 1 ) 研究和讨论了并行计算机的基本知识，并在局域网环境下模拟并行机环 境，在搭建的并行机环境下用m p i 和p v m 进行并行程序的调试和运行。 ( 2 ) 研究矩阵的一些常见的运算，以及这些运算在串行机环境下和并行机环 境下的矩阵运算算法的区别和联系。 ( 3 ) 分析和讨论了矩阵乘法运算在矩阵规模远大于处理器个数的情况下，对 理想状态( 处理器个数大于等于矩阵规模情况) 下矩阵并行乘法算法的改进，提 出了自己的一些方案。 1 9 论文内容组织 论文共分为五章： 第一章介绍了并行计算出现的历史和基本概念，并讨论了并行计算机的分类 和物理模型。 第二章介绍了m p i 的基本知识和在w i n d o w s 系统下搭建m p i c h 并行编程 环境。 第三章介绍了并行程序设计的基本理论知识、并行算法的实现以及评估并行 算法的性能的加速比性能定律。 1 4 第一章并行计算简介 第四章介绍了并行任务的划分，矩阵运算的并行算法性能研究和改进，着重 分析了在处理器个数远小于矩阵规模情况了矩阵运算的算法性能分析和算法的 可行性。 第五章总结了论文所做的工作中存在的一些不足和对未来工作的一些展望。 1 5 湖北人学硕士学1 奇= 论文 第二章m p i 并行机环境的搭建与使用 2 1m p i 编程简介 在当前流行的并行机上主要的编程环境有消息传递、共享存储和数据并行。 其中消息传递具有良好的可移植性、可扩展性，具有完备的异步通信功能。 m p i ( m e s s a g ep a s s i n gi n t e r f a c e ) 是1 9 9 4 年5 月发布的一种消息传递接1 2 1 ， 是为消息传递程序提供的标准库，由标准消息传递函数及相关辅助函数构成，进 程通过调用这些函数( 类似调用子程序) 通信；一个程序同时启动多份，形成多个 独立的进程，在不同的处理机上运行，拥有独立的内存空间，进程间通信通过调 用m p i 函数来实现；每个进程开始执行时，将获得一个唯一的序号。 m p i 实际上是一个消息传递函数库的标准说明，以语言独立的形式来定义这 个接口库，并提供了与c 和f o r t r a n 语言的绑定，是目前高效率的超大规模并行 计算最可信赖的平台。它能运行在所有的并行平台上，包括s m p 和p v p 。程序 设计语言支持c 、f o r t r a n 和j a v a 。在国产的三大并行机系列：神威、银河和曙 光上都实现了对m p i 的支持。 m p i 标准化涉及到大约6 0 个国家的人们，他们主要来自于美国和欧洲的4 0 个组织，这包括并行计算机的多数主要生产商，还有来自大学、政府实验室和工 厂的研究者们工厂的研究者们。1 9 9 2 年4 月，并行计算研究中心在w i l l i a m s b u r g ， v i r g i n i a ，召开了一个关于消息传递的标准的工作会议，会议上讨论了标准消息 传递的必要的、基本的特点，并建立了工作组继续进行标准化工作。 1 9 9 2 年1 0 月，m p i 的初步草稿m p l l 形成，m p l l 主要包含的是在 w i l l i a m s b u r g 工作组会议上讨论的基本消息传递的接口，因为它的基本目的就是 促进讨论并继续此项工作，所以它主要集中在点对点的通信。1 9 9 3 年1 月，第 一届m p i 会议在d a l l a s 举行，1 9 9 3 年2 月m - p n 修定版本公布；之后定期召开 了一系列关于m p i 的核心的研讨会；1 9 9 3 年1 1 月m p i 的草稿和概述分别发表 于s u p e r e o m p u t i n g 9 3 和t h e p r o e e e d i n g s 。直到1 9 9 4 年5 月，m p i 标准正式发布。 1 9 9 4 年7 月发布了m p i 标准的勘误表。 1 6 第二章m p i 并行机环境的搭建与使用 2 1 1m p i 基本函数 m p i 由一组库函数组成，在f o r t r a n 7 7 、f o r t r a n 9 9 、c 和c + + 语言中皆可以直 接对这些函数进行调用。作为一种消息传递式的并行编程环境，m p i 并行程序要 求将任务分块，同时启动多个进程并发执行，各进程之间通过调用m p i 的库函 数实现消息传递。m p i 所有的通信功能可以用它的6 个基本调用来实现【1 4 】： m p i 初始化：m p ii n i t o 是m p i 程序的第一个调用，它完成m p i 程序所 有的初始化工作，也是m p i 程序的第一条可执行语句。 m p i 结束：m p if i n a l i z e ( ) 是m p i 程序的最后一个调用，它结束m p i 程序 的运行，也是所有m p i 程序的最后一条可执行语句。 获取当前进程标识：m p i c o m mr a n k ( c o m m ，r a n k ) ，返回调用当前进程在 给定通信域中的标识号，这样不同的进程就可以将自身和其他的进程区 别开来，实现各进程的并行。对n 个进程，其标识为o , - 一n _ l 。 通信域包含的进程数：m p ic o m m ，e)，返回给定通信域中size(comm s i z 所包括的进程的个数，不同的进程通过这一调用得知在给定的通信域中 一共有多少个进程在并行执行。 消息发送：m p i _ s e n d ( b u f , c o u n t ，d a t a t y p e ，d e s t ，t a g ，c o m m ) ，m p i s e n d 将发 送缓冲区b u f 中的c o u n t 个d a t a t y p e 数据类型的数据发送到目的进程 d e s t ，t a g 是个整型数，它表明本次发送的消息标志，使用这一标志，就可 以把本次发送的消息和本进程向同一目的进程发送的其他消息区别开 来。m p is e n d 操作指定的发送缓冲区是由c o u n t 个类型为d a t a t y p e 的连 续数据空间组成，起始地址为b u f o 消息接收：m p l r e c v ( b u f , c o u n t ，d a t a t y p e ，s o u r c e