并行算法设计.ppt

《并行算法设计.ppt》由会员分享，可在线阅读，更多相关《并行算法设计.ppt（96页珍藏版）》请在三一办公上搜索。

1、,并行算法设计,主要内容,基本知识及现状并行计算性能评测并行算法的一般设计方法并行算法的基本设计技术并行算法的一般设计过程例子,现代计算机的共同特点：并行性,现代计算机的共同特点：并行性,并行:古老的思想!,“.并行计算并不是什么新的思想,只是将它扩展应用于计算机而已.作者也不认为这种扩展应用会存在什么无法克服的困难.但也不要期待有效的并行编程方法与技术能够在一夜之间诞生.期间还需要有许多的工作和实验要做.毕竟,今天的编程技术(串行)是若干年来艰苦的探索才取得的.现在编程工作似乎成了一种令人单调乏味的工作,事实上,并行编程的出现将会使重新恢复编程工作者们的探索精神.”(Gill,S.(1958

2、),“Parallel Programming,”The Computer Journal,vol.1,April,pp.2-10.),Parallel Programming with MPIby Peter Pacheco(2000),综述为什么要做并行计算,从系统的角度：集成系统资源，以满足不断增长的对性能和功能的要求从应用的角度：适当分解应用，以实现更大规模或更细致的计算,并行计算的功能?,降低单个问题求解的时间.增加问题求解规模.提高吞吐率(多机同时执行多个串行程序).,并行计算?,资料来源:Tim Mattson Intel Co.Com.Science Lab.Rudolf Ei

3、genmann Purdue Uni.School of Elec.and Comp.Eng.,分而治之!,并行计算现状(硬件),共享内存SMP并行计算机对称多处理器或共享内存处理器多个处理器通过系统总线或者交叉开关共享一个或者多个内存模块优点：使用简单，维护方便缺点：受系统总线带宽限制，只能支持少量处理器（十几个）并行编程方式：通常OpenMP，也可用消息传递(PVM/MPI)及HPF代表机型：SGI PowerChanlenge;SUN E10000等,并行计算现状(硬件),分布内存MPP型计算机Massively Paralleled Processors的简称指由大量具有局部内存的计算

4、节点通过高速系统网络连接而成的并行处理系统MPP系统的系统网络通常具有某种拓扑结构（Tree,Mesh,Torus,Hypercuber）,并行计算现状(硬件),DSM型并行计算机分布共享内:Distributed Shared Memory多个物理上具有独立内存的处理单元，通过高速网络连接在一起逻辑上作为共享内存并行机使用不同处理单元间内存的共享通过特殊的硬件/软件实现具有比SMP型计算机更好的可扩展性（超过100个CPU）代表机型：SGI Origina 2000/3000,并行计算现状(硬件),SMP/DSM机群多台SMP型/DSM型并行机通过互联网络连接而成目前国内外最高性能的并行机大

5、多是这种结构,并行计算现状(硬件),微机/工作站机群微机机群(PC cluster,又称Beowulf Cluster）,工作站机群(NOW,Network of Workstations):将联网的多台微机/工作站组织诚意台并行机。适用于中等规模的并行系统，(数百个处理器)根据机群中使用的机型分为同构型和议购型两种根据使用方式可分为专用型和兼用型，前者指专门用于并行计算。价格便宜、配置灵活，但规模及并行效率收网络设备的制约，配以适当的系统工具可以达到MPP的以适当的系统工具可以达到MPP的使用效果,并行计算现状(软件),:“并行软件开发远远落后于并行系统体系结构的发展.”:“与串行软件相比,

6、并行软件数量少,功能原始.”-悲观者,并行计算现状,:编程环境落后的并行编译器,调试器 vs.通用先进的串行编程环境.自动并行编译器远远满足不了程序并行化的要求.:算法并行模型的多样化 vs.串行编程中的唯一模型:冯.诺依曼模型对串行机而言,解法=唯一串行算法+计算程序(通用)对并行机而言,解法=某种并行算法+有针对性的计算程序(很难通用):人稀少而初级的并行编程人员 vs.成熟而经验丰富的串行程序员,并行计算现状,:“并行编程正处理蓬勃发展时期,机遇与挑战并存.”-乐观者,并行计算现状(并行编程模式),自动并行与手工并行在SMP/DSM并行机上编译系统通常具有一定的对用户程序进行自动并行化的

7、能力但需人工干预（制导语句，命令行选项），针对循环（细粒度)并行分布式内存并行机上不具备，需人工编写并行程序并行算法的设计和并行程序的编制成为大规模并行机应用的主要障碍。,并行计算现状(并行编程模式),OpenMP:串行程序的循环语句前插入特定的制导语句，告知编译系统一些有助于对其进行并行的信息，以及/或是强制编译系统按照指定的方式将其并行化主要是SMP/DSM，某些MPP也开始发展结合编译系统的自动并行化功能使用某些自动化工具，可对程序结构及数据流分析，自动插入适当的OpenMP语句优点：简单，不需对原算法/程序作大的改动，缺点：只适合某些机型，且可扩展性不如消息传递对某些具有强数据相关的过

8、程需改变计算顺序，或修改算法,并行计算现状(并行编程模式),DSM编程模式建立在某种内存协议之上，通过软件或者软硬件结合的方式实现处理器间内存的共享通过要求DSM并行程序中对内存的读写遵循一定的要求来减小维护内存一致性的开销,并行计算现状(并行编程模式),高性能FORTRAN(HPF)基于数据并行的编程语言，用户通过指导语句指示编译系统将数据分布到各处理器上，并根据分布情况生成并行程序，针对Fortran90/95适合于SMP/DSM/MPP/Cluster系统优点：编程简单，串并行程序一致缺点：并行过程对用户透明度不高，性能编译系统和用户对编译系统的了解程度；不同的编译器需做不通的优化，影响

9、移植性,并行计算现状(并行编程模式),消息传递编程模式并行程序由一组独立的进程组成，相互通过发送消息实现数据交换并行应用程序开发的最底层编程方式之一，很多其他并行开发语言/工具将程序转化成消息传递类型实现。常用的平台：PVM(Parallel Virtue Machine)和MPI(Message Passing Interface)优点：通用性好，用PVM和MPI编写的程序可用于任何并行机；缺点：编制、调试困难，有时需对程序算法做大的改动,并行计算现状(并行编程模式),MPI+OpenMP用于SMP组成的机群系统，节点间一消息传递方式，节点内不同处理器之间通过共享内存并行可以充分利用计算资源

10、,并行算法的概念,并行算法：是一些可同时执行的诸进程的集合，这些进程相互作用和协调动作从而达到给定问题的求解。并行性条件 数据相关性：流相关、反相关、输出相关相关性判别条件 输入集合I1,I2,输出集合U1,U2,I1U2=;I2U1=;U1U2=,并行算法的分类,数值并行算法：数值计算非数值并行算法：符号运算同步并行算法：向量算法、SIMD、MIMD同步异步并行算法：不需相互等待独立并行算法：进程间完全独立细粒度并行算法：基于向量和循环系级并行中粒度并行算法：较大的循环级并行大粒度并行算法：任务级并行（区域分解）,多线程库标准 Win32 API.POSIX threads.编译制导标准 O

11、penMP 可移植共享存储并行编程标准.消息传递库标准 MPI PVM,并行编程标准,并行算法的发展,基于向量运算的并行算法设计阶段基于多向量处理机的并行算法设计阶段SIMD类并行机上的算法设计阶段MIMD类并行机上的并行算法设计阶段现代并行算法设计以MIMD为主，要求可扩展性、可移植性,并行软件程序员的工作,指令层，非常细的粒度数据层，细粒度控制层，中粒度任务层，大粒度 前两层大都由硬件和编译器负责处理，程序员通常处理后两层的并行,并行计算性能评测,机器的峰值速度用户能得到的实际速度Benchmark top500 LINPACK www.top500.org加速比、效率可扩展性：体系结构、

12、软件、算法性能依赖因素：算法设计：并行性、计算量 程序设计：体系结构特点的利用（通信、存储、cache)、负载平衡、并行粒度,并行计算性能评测,加速比性能定律p/logp 1/fGustafson定律：时间不变，提高规模（精度）S=f+p(1-f)=p+f(1-p)=p-f(p-1)Sun和Ni定律:存储受限的加速定律S=(f+(1-f)G(p)/(f+(1-f)G(p)/p)G(p)=1:Amdahl;G(p)=p,Gustafson,并行计算性能评测,可扩放性评测标准（目的）确定某类问题用哪种并行算法与哪种并行体系结构结合，可以有效地利用大量处理器；运行于某种体系结构的并行机上的某种算法，

13、根据在小规模机器上的运行性能，预测在大规模机器上的性能对固定的问题规模，确定最有的处理机数和加速比指导改进算法、体系结构，以利用可扩充的大量处理器,并行计算性能评测,可扩放性评测标准：等效率度量标准:随着系统规模的增加，测量增加多少运算量会保持效率不变。E=s/p等速度度量标准：系统规模增加时，若保持速度不变，每个处理器增加浮点操作的量V=Wp/pTp等计算时间/通信开销比率度量标准：系统规模增加时，保持计/通比不变所需要增加的问题规模。计算时间/通信开销比率：并行计算时间与系统开销之比。,并行计算性能评测,基准测试程序：测试计算机系统的性能综合型核心型数学库应用型并行型,并行计算模型,什么是

14、并行计算模型？将并行计算机的基本特征抽象出来，形成一个抽象的计算模型，作为并行算法分析、设计、性能预测的基础。,编程模型计算模型体系结构模型机器模型,用户,系统,并行计算模型,PRAM模型(Parallel Random Access MAchine),并行速记存取机器，也叫共享存储的SIMD模型，一种抽象的并行计算模型容量无限大的共享存储器有限/无限个功能相同的处理器，具有简单的算术运算和逻辑判断功能；任何时刻各处理器均可以通过共享内存交换数据,并行计算模型,PRAM模型：优点：适合于并行算法的表达，分析和比较；使用简单处理器间通信、存储管理和进程同步等细节均隐含于模型中；易于设计算法，且稍

15、加修改即可运行于不同的处理机缺点：同步模型，不能反映现实中许多系统的异步性；假设每个处理器可在单位时间访问共享存储器的任一单元，忽略了存取竞争和有限带宽等是不现实的；假设处理机有限或无限，对并行任务的增大不加限制。,并行计算模型,BSP(Bulk Synchronous Parallel)模型处理器/存储器模块，（简称处理器）p处理器间点对点消息传递的选路器,g执行以时间间隔L为周期的路障同步器L计算由一系列用全局同步分开的周期为L的超步(Superstep)组成。在各步中，各处理器均执行局部计算，并通过选路器接收和发送信息；然后做全局检查，确定该步是否已由所有处理器完成：是进入下一超步；否则

16、，下一个L周期分配给为完成的超步。,并行计算模型,BSP模型特点：处理器与选路器分开，选路器只有点对点的消息传递路障方式实现的同步在粗粒度，提供了执行紧耦合同步式算法的有效方式假定局部操作在一个时间步完成，每一超步中，每一处理器至多传送或接收有限条信息每个PRAM模型所设计的算法，均可在每个BSP处理器上模拟一些PRAM处理器的方法实现。,并行计算模型,logP模型：分布存储的，点到点通信的多处理机模型，通信网络由一组参数来描述，不涉及具体的网络结构，也不假定算法一定用显示的消息传递操作描述。L(Latency)：网络中消息从源到目的地所遭到的延迟。O(Overhead)：发送/接收一条消息所

17、需的额外开销。G(Gap)：处理器可以连续进行消息发送/接收的最小时间间隔。处理器通信带宽的倒数P(Processor)：处理器/存储器模块数。L,g:反映网络的容量。L,o,g均可表示为处理器周期的整数倍,并行计算模型,logP模型的特点表述了分布存储并行机的性能瓶颈。隐藏了网络的拓扑结构无需说明编程风格或通信协议，可用于共享存储、消息传递和数据并行。如果g=0;L=0;o=0,logP 等同于PRAM，同时也是BSP的改进和细化,并行计算模型,C3模型：(Computation,Communication,Congestion)p处理器数，l信包的长度，s执行发送的建立时间；h表示延迟与体

18、系结构无关的粗粒度并行计算模型，旨在反映计算复杂度，通信模式和通信期间潜在的拥挤等因素对粗粒度网络算法的影响考虑了网络链路拥挤和处理器拥挤对并行算法的影响,并行计算模型,L:通信延迟时间o:CPU准备发送或接收开销g:CPU连续发送或接收的最小时间间隔，倒数为处理机的通信带宽P:处理机个数,并行计算模型,BSP和LogP的相互比较：本质等价，可互相模拟，BSP模拟LogP进行的计算，慢常数倍，反之慢对数倍BSP为算法和程序提供了更多的方便，LogP提供了较好的机器资源的控制BSP在结构化编程风格方面的优点大于精确度方面的损失,并行计算模型,并行化方法,分而治之模型并行、算法并行、程序并行自然并

19、行：数据并行、功能分割任务主从型、SPMD型、管道型（流水线）、二叉树型（分解与递归）,分而治之,Y=(A+B(C+DEF)+G 6Y=(A+G)+B(C+DEF)5Y=(A+G+BC)+BD*EF 3,并行化方法,C=A*B,P1P2P3P4,=,*,并行化方法,红黑格法,P1,P2,mem1,mem2,communication,并行化方法,并行二叉树技术：解决通信瓶颈问题，通信复杂度O(P)下降到O(log P),并行化方法,并行流水线技术：解决串行算法中不可避免的数据相关性，例如Gauss-Seidel迭代、双曲型方程中的上下游流场数据依赖问题等,并行化方法物理建模,Flight_dy

20、namics,control,atmosphere,body,Wing,Input_data,Tail,Wing,Rudder,如何做并行应用？,串行算法分析：模块化串行软件测试：找消耗90CPU的hot选择并行方法：分而治之从物理模型开始并行软件框架设计：流水线/主从/平等并行程序设计：MPI/PVM/OPEN MP等性能测试与分析：正确性、效率进一步优化：应用,并行算法的一般设计方法,并行算法的直接并行化从问题描述开始设计并行算法借用已有算法解新问题,并行算法的一般设计方法,并行算法的直接并行化 检测和开拓串行算法中固有的并行性而直接j将其并行化。对于一类具有内在顺序性的串行算法，难以直接

21、并行并非任何优秀的串行算法都可以产生好的并行算法，相反一个不好的串行算法可能产生很优秀的并行算法,并行算法的一般设计方法,从问题描述开始设计并行算法从问题的描述出发，寻求可能的新途径，设计出一个新的并行算法。不是完全排除串行算法设计的基本思想，而是更着重从并行化的具体实现上开辟新的设计方法,并行算法的一般设计方法,借用已有算法解新问题：借用已知的某类问题的求解算法求解另一问题。例：利用矩阵乘法求所有点对间最短路径。n个顶点加权有向图G(V,E)，矩阵Wnxn,购造矩阵D,di,j从vi到vj 的最短路径长度。dkij表示vi到vi 的经过至多-1个点的最短路径长度Dkij=wi,jdkij=m

22、indk/2il,dk/2lj。因此D可以经由D1逐次计算D2，D4，Dn-1，然后由D=Dn-1即可。由Dk/2求Dk，可以使用标准矩阵乘法，只是将原改为+；求和运算改为“min”操作。,并行算法的基本设计技术,划分设计技术分治设计技术平衡树设计技术倍增设计技术流水线设计技术,并行算法的基本设计技术,划分设计技术：将给定问题分成p个独立的几乎等尺寸的子问题交由p台处理机求解，关键：如何分组，使得子问题易于求解或者子问题的解易于组合成员问题的解。均匀划分技术方根划分技术对数划分技术功能划分技术,并行算法的基本设计技术,分治设计技术：将一个大而复杂的问题分解成若干特征相同的子问题分而治之将输入问

23、题分解成若干特征相同的子问题并行地求解各个子问题归并各子问题的解称为源问题的解,并行算法的基本设计技术,平衡树设计技术：此法成功的部分原因是树中能迅速的存取所需的信息。将输入元素作为叶节点构造一棵平衡二叉树，然后自叶向根往返遍历，可以推广到内节点的子节点数大于2的任意平衡数，对于数据的播送、压缩、抽取和前缀计算尤其有效。,并行算法的基本设计技术,倍增设计技术：也叫指针跳跃(Pointer Jumping)技术，特别适合处理以链表或有向根树之类表示的数据结构，在图论和链表算法中有着广泛的应用。每当递归调用时，所要处理的数据之间的距离将逐步加倍，经过k步即可完成距离为2k的所有数据的计算。,并行算

24、法的基本设计技术,流水线设计技术：流水线（pipelining)技术是一项重要的并行技术，在VLSI并行计算中表现尤为突出。基本思想：将一个任务t分成一系列子任务t1,t2,tm,使得一旦t1完成，后继的子任务就立即开始，并以同样的速率进行计算。,并行算法的基本设计技术,破对称技术（Symmetry Breaking）打破某些问题的对称性的一种设计方法。凸轮问题和随机算法中常用加速级联技术(Accelerated Cascading)：最优但不快的算法与非常快但不是最优的算法“串接”，没有普遍性随机法：引入随机性，随机选择下一执行步，设计简单，分析复杂，结果也可能不正确,并行算法的一般设计过程

25、,PCAM设计方法学从给定问题的描述出发，通过一系列步骤，最终设计出一个具有并发性、可扩放性、局部性、和模块性的并行算法。分为四步：1:划分（partitioning）、2:通信（communication）、3:任务组合(agglomeration)和4:处理器映射(Mapping).1,2考虑与机器特性无关的特性：并行性和可扩放性，寻求具有这些特性的算法3，4：局部性等与性能有关的问题,并行算法的一般设计过程:划分,使用域分解或者功能分解将整个计算分解成一些小的任务，以便充分利用其潜在的并行性和可扩放性。先集中数据的分解（域分解），然后是计算功能的分解（功能分解），两者互为补充。要点：计算

26、集、数据集互补相交，以避免数据和计算的复制,并行算法的一般设计过程:划分,划分标准任务数，是否至少高于目标机上处理器数的一个量级。（灵活性）是否避免了冗于的计算和存储要求。（扩放）划分的任务是否尺寸大致相当。（均衡）任务数是否与问题尺寸成比例。是否采用了几种不同的划分法，多考虑几种选择可提高灵活性，同时既考虑域分解，又要考虑功能分解。,并行算法的一般设计过程:通信,局部通信vs.全局通信局部：相邻的任务至今；全局：很多任务参与交换数据结构化通信vs.非结构化通信静态通信vs.动态通信静态、结构化，一任务的通信的伙伴形成规则的不变的模式；非结构化、动态：模式不归整且随时间变化。同步通信vs.异步

27、通信同步：双方知道何时进行通信，发送方显示的发给接收方；异步：不确定，接收方明确地从发送者请求数据。,并行算法的一般设计过程:通信,通信标准所有任务是否执行大致同样多的通信。(可扩放性)每个任务是否只与少许近邻通信猪通信操作是否能并行执行不同任务的计算能否并行执行,并行算法的一般设计过程:组合,目的：合并小尺寸的任务以减少任务数，理想情况每个处理器一个任务，得到SPMD程序。增加粒度：表面-容积效应：通信量比例于子域的表面积，计算比例于容积，通信/计算之比随任务的尺寸的增加而减少。重复计算（Replication Computation）,也叫冗余计算，有时可用冗余计算来减少通信。保持灵活性和

28、减少软件成本,并行算法的一般设计过程:组合,组合标准组合造成的重复计算，是否平衡了其收益？造成重复数据，是否已证实不会因限制问题尺寸和处理机数目而影响可扩放性？组合产生的任务是否具有类似的计算、通信代价？任务数目是否仍与问题尺寸成比例？,并行算法的一般设计过程:映射,指定每个任务到哪里执行，目的，减少算法的总的执行时间，(NP完全问题)。可并发执行的任务放在不同的处理器上，增强并行度需要频繁通信的任务置于同一处理器上以提高局部性。采用域分解技术，当分解算法复杂，工作量不一样，通信也许是非结构化的，此时需要负载平衡算法。基于功能分解，会产生一些由短暂任务组成的计算，它们在开始与结束时需与别的任务

29、协调，此时可采用任务调度算法。,并行算法的一般设计过程:映射,负载平衡算法：将划分阶段产生的细粒度任务组合成每个处理器一个粗粒度的任务。递归对剖局部算法概率方法循环映射块循环分配,并行算法的一般设计过程:映射,任务调度算法Master/Slave非集中式结束检测,并行算法的一般设计过程:映射,标准采用集中式负载平衡方案，管理者是否会成为瓶颈？动态平衡方案，是否衡量过不同策略的成本？采用概率或者循环法，是否有足够多的任务保证负载平衡？（10倍）设计SPMD程序，是否考虑过基于动态任务创建和消除的算法？后者可以得到简单的算法，但性能可能有问题。,并行程序设计方法,并行程序设计方法,四种设计模型：隐

30、式并行、数据并行、共享变量和消息传递 在实际的并行机上设计并行程序时，绝大部分均采用扩展Fortran和C语言的办法库函数法：一组支持并行性和交互操作的库函数新语言结构法：采用某些新的语言结构来实现并行性和交互操作的支持编译指导：,并行程序设计模型,并行编程风范(Parallel Programming Paradigms):构造运行在并行机上的并行算法的方法相并行（Phase Parallel），也叫松散并行分治并行(Divide and Conquer Parallel)流水线并行(Pipeline Parallel)主-从并行(Master-Slave Parallel)工作池并行(Wo

31、rk Pool Parallel),共享存储并行编程,X3H5共享存储模型POSIX(Portable Operating System Interface)Threads,即PthreadsOpenMP,共享存储并行编程,X3H5共享存储模型并行结构（区域）成对Parallel End Parallel。其中变量有共享/私有属性；可有并行块(MPMD)、并行循环(SPMD或单一进程。程序以单线程（基线程、主线程）串行模式开始，遇到Parallel时开启到并行模式，生成多个子线程；基线程及其子线程并行执行直到End Parallel;然后返回串行模式由基线程继续存储器的一致性：隐/显路障，栅栏

32、操作同步变量：闩锁(Latch)、锁、事件和顺序(Ordinal),共享存储并行编程,POSIX线程模型线程管理：线程库用于管理线程。Pthread_create()生成新线程；pthread_exit()结束调用线程；pthread_self()返回调用线程的ID；pthread_join等待其他线程结束。线程调度：pThread_yield()是调用者将处理器让位于其他线程；pthread_cancel()终止指定的线程线程同步：互斥变量和条件变量,分布存储并行编程,消息传递模型SPMD：单程序多数据流MPMD：多程序多数据流数据并行模型SIMD：单指令多数据流SPMD：分布存储的SIMD

33、体系结构上可以实现SPMD的数据并行；分布存储的MIMD体系结构上可以实现SPMD的数据并行；也可实现MPMD的消息传递,分布存储并行编程,基于消息传递：SPMD数据划分：尽量考虑负载平衡、存储空间的均衡使用和减少通信优化通信，提高计算/通信比全局操作：将各处理器的局部结果组合成最终结果SPMD程序有两种方式：主机/节点(HOST/Node)无主机(Hostless),分布存储并行编程,基于消息传递：MPMD子问题划分：考虑负载均衡，充分利用各处理器的独特能力，在全系统范围内合理分配各子问题与不同的处理器上；确定子问题之间的相互作用方式数据流方式：客户/服务器方式,分布存储并行编程,基于数据并

34、行模型数据并行程序是一个单一控制线程的、并行操作于不同数据项的、语句循环级同步的、单一地址空间的、通信可由变量指派而隐含地完成的一种并行程序。数据分布：数据按一定规则分配到处理器的存储单元任务分配：计算任务分配到各处理器同步通信：处理器拓扑结构：,并行编程标准比较,案例1：Geoil,Geoil:油气勘探的地震波数据处理系统炮：O(100)道：O(480-10000)采样点/道：O(20005000)输入数据/炮：4M-200M目前的高档微机/炮：4h,案例1：Geoil续,案例1：Geoil续,Geoil,曙光3000四个结点16个cpu4h12min,数据准备,数据收发,结果处理,炮偏移计

35、算,Master_Slave结构,案例1：Geoil续,案例2：矩阵乘,矩阵的划分带状划分：块带状划分、循环带状划分棋盘划分：块其棋盘划分、循环棋盘划分,案例2：矩阵乘,算法1 数组A，C分别分割为np个n0n的子区域，这里n0=n/np，第k（1knp）个子区域存放在第k-1个节点上。类似地，数组B分割为np个nn0的子区域，第k个子区域存放在第k-1个节点上。于是，整个计算由np步组成，每一步，各个节点id(0idnp)作自己的局部计算，后将B数组的子区域值向节点mod(id-1+np，np)传送。第np步只作计算不作数据传送。,案例2：矩阵乘,算法2 数组A，B，C均分割为n1xn1的子

36、块，这里n1=n/(np)1/2，并设(np)1/2为整数，子块个数各为(np)1/2(np)1/2。计算由(np)1/2步组成，每一步，各个节点作自己的局部计算，后将id节点上数组A的子块向mod(id-1+(np)1/2，(np)1/2)节点传送，而B的子块向mod(id-(np)1/2+np，np)传送。第(np)1/2步不作数据传送。,案例2：矩阵乘,总计算量：2*n3每迭代步每个节点的计算量：算法1：2n3/(np)2 VS.算法2：2*n3/(np*(np)1/2)。每迭代步每个节点的通信量：算法1：n2/np VS.算法2：2n2/np 总迭代次数：算法1：np VS.算法2：(

37、np)1/2 每迭代步计算量与通信量之比：算法1：np/(2*n)VS.算法2：(np)1/2/n,相关资料,MPI:http:/www.mpi-forum.orghttp:/www.mcs.anl.gov/mpi参考书目：Kai Hwang&Zhiwei Xu:Scalable parallel Computing Technology,Architecture,ProgrammingRajkumar Buyya:High Performance Cluster ComputingM.J.Quinn:Parallel Computing:Theory and Practice陈国良：并行计算：结构、算法、编程李晓梅等：可扩展并行算法的设计与分析,谢谢，欢迎交流!,