《2009并行计算-3》由会员分享，可在线阅读，更多相关《2009并行计算-3（43页珍藏版）》请在金锄头文库上搜索。
1、并行计算结构算法编程2可扩放性评测标准并行计算的可扩放性（Scalability）也是主要性 能指标可扩放性最简朴的含意是在确定的应用背景下，计算 机系统（或算法或程序等）性能随处理器数的增加而 按比例提高的能力 提高加速比的因素：处理器数与问题规模影响加速比的因素：求解问题中的串行分量并行处理所引起的额外开销（通信、等待、竞争、冗 余操作和同步等）加大的处理器数超过了算法中的并发程度3可扩放性评测标准增加问题的规模有利于提高加速的因素：较大的问题规模可提供较高的并发度；额外开销的增加可能慢于有效计算的增加；算法中的串行分量比例不是固定不变的（串行部分所 占的比例随着问题规模的增大而缩小）。增
2、加处理器数会增大额外开销和降低处理器利 用率，所以对于一个特定的并行系统（算法或 程序），它们能否有效利用不断增加的处理器 的能力应是受限的，而度量这种能力就是可扩 放性这一指标。 4可扩放性评测标准可扩放性:调整什么和按什么比例调整并行计算要调整的是处理数p和问题规模W，两者可按不同比例进行调整，此比例关系（可能是 线性的，多项式的或指数的等）就反映了可扩放的 程度。 并行算法和体系结构 可扩放性研究的主要目的：确定解决某类问题用何种并行算法与何种并行体系 结构的组合，可以有效地利用大量的处理器；对于运行于某种体系结构的并行机上的某种算法当 移植到大规模处理机上后运行的性能；5可扩放性评测标
3、准对固定的问题规模，确定在某类并行机上最优的处 理器数与可获得的最大的加速比；用于指导改进并行算法和并行机体系结构，以使并 行算法尽可能地充分利用可扩充的大量处理器 目前无一个公认的、标准的和被普遍接受的严 格定义和评判它的标准 6等效率度量标准 令tie 和t io 分别是并行系统上第i个处理器的有用 计算时间和额外开销时间（包括通信、同步和空 闲等待时间等）Tp 是p个处理器系统上并行算法的运行时间，对 于任意i显然有Tp = tie +t io ，且 Te+ To= pTp 问题的规模W为最佳串行算法所完成的计算量 W=Te 7等效率度量标准 如果问题规模W 保持不变，处理器数p增加，开
4、 销To增大，效率E下降。为了维持一定的效率（介 于0与1之间），当处理数p增大时，需要相应地增 大问题规模W的值。由此定义函数f E（p）为问题规模W随处理器数p 变化的函数，为等效率函数（ISO-efficiency Function）（Kumar1987） 8等效率度量标准曲线1表示算法具有很好的扩放性；曲线2表示算法是 可扩放的；曲线 3表示算法是不可扩放的。 优点：简单可定量计算的、少量的参数计算等效率函 数 缺点：如果To无法计算出（在共享存储并行机中）9等速度度量标准 p 表示处理器个数，W表示要求解问题的工作量或称 问题规模（在此可指浮点操作个数），T为并行执行时 间，定义并行
5、计算的速度V为工作量W除以并行时间T p个处理器的并行系统的平均速度定义为并行速度V除 以处理器个数 p：W是使用p个处理器时算法的工作量，令W表示当处理 数从p增大到p时，为了保持整个系统的平均速度不变 所需执行的工作量，则可得到处理器数从 p到p时平 均速度可扩放度量标准公式 10等速度度量标准 那么当等平均速度时，即 当p=1时， 11等速度度量标准优点：直观地使用易测量的机器性能速度指标来度 量缺点：某些非浮点运算可能造成性能的变化12平均延迟度量标准 Ti为Pi的执行时间，包括包括延迟Li，Pi的总延迟时间 为“L i+启动时间+停止时间”。定义系统平均延迟时间 为pTpara =T
6、o+ Ts 在p个处理器上求解工作量为W问题的平均延迟 在p个处理器上求解工作量为W问题的平均延 迟当处理器数由p变到p，而推持并行执行效率不变， 则定义平均延迟可扩放性度量标准为 13平均延迟度量标准优点：平均延迟能在更低层次上衡量机器的性 能缺点：需要特定的软硬件才能获得平均延迟14第四章 并行算法的设计基础4.1 并行算法的基础知识4.1.1 并行算法的定义和分类4.1.2 并行算法的表达4.1.3 并行算法的复杂性度量4.1.4 并行算法中的同步和通讯15并行算法的定义和分类并行算法的定义算法并行算法：一些可同时执行的诸进程的集合，这些进 程互相作用和协调动作从而达到给定问题的求解。并
7、行算法的分类数值计算和非数值计算同步算法和异步算法分布算法确定算法和随机算法16并行算法的表达描述语言可以使用类Algol、类Pascal等；在描述语言中引入并行语句。并行语句示例Par-do语句 for i=1 to n par-do end forfor all语句 for all Pi, where 0ik end for 17并行算法的复杂性度量串行算法的复杂性度量期望复杂度(Expected Complexity)最坏情况下的复杂度(Worst-CASE Complexity) 并行算法的几个复杂性度量指标运行时间t(n):包含计算时间和通讯时间，分别用计算 时间步和选路时间步作单位
8、。n为问题实例的输入规模 。处理器数p(n)并行算法成本c(n): c(n)=t(n)p(n)总运算量W(n): 并行算法求解问题时所完成的总的操 作步数。18Brent定理Brent定理令W(n)是某并行算法A在运行时间T(n)内所 执行的运算量，则A使用p台处理器可在 t(n)=O(W(n)/p+T(n)时间内执行完毕。19Brent定理证明：将T(n)分成若干个时间步(并行步),对应 第i个时间步的计算量为Wi(n),在p个处理机时可用不超过 并行步进行模拟，那么该算法在p个处理机上的执行时间为： 20并行算法的复杂性度量W(n)和c(n)密切相关P=O(W(n)/T(n)时，W(n)和
9、c(n)两者是渐进 一致的对于任意的p，c(n) W(n)21并行算法的同步同步概念同步是在时间上强使各执行进程在某一点必须 互相等待；可用软件、硬件和固件的办法来实现。22并行算法的同步同步语句示例算法4.1 共享存储多处理器上求和算法 输入：A=(a0,an-1),处理器数p 输出：S=ai Begin (1)S=0 (2.3) lock(S) (2)for all Pi where 0ip-1 do S=S+L(2.1) L=0 (2.4) unlock(S) (2.2) for j=i to n step p do end for L=L+aj End end for23并行算法的通讯
10、通讯共享存储多处理器使用：global read(X,Y)和 global write(X,Y)分布存储多计算机使用：send(X,i)和receive(Y,j)24并行算法的通讯通讯语句示例算法4.2 分布存储多计算机上矩阵向量乘算法 输入：处理器数p, A划分为B=A1n,(i-1)r+1ir, x划分为w=w(i-1)r+1;ir 输出：P1保存乘积AX Begin (1) Compute z=Bw (2) if i=1 then yi=0 else receive(y,left) endif (3) y=y+z (4) send(y,right) (5) if i=1 then rec
11、eive(y,left) End 25并行算法的设计基础4.2 并行计算模型4.2.1 PRAM模型4.2.2 异步APRAM模型 4.2.3 BSP模型4.2.4 logP模型26并行计算模型什么是并行计算模型？ 将并行计算机的基本特征抽象出来，形 成一个抽象的计算模型，作为并行算法分 析、设计、性能预测的基础。编程模型计算模型体系结构模型机器模型用户系统27PRAM模型基本概念由Fortune和Wyllie1978年提出，又称SIMD-SM 模型。有一个集中的共享存储器和一个指令控 制器，通过SM的R/W交换数据，隐式同步计算 。结构图Control UnitInterconnection
12、 NetworkPLMPLMPLMPLMShared Memory28PRAM模型分类PRAM-CRCW并发读并发写CPRAM-CRCW(Common PRAM-CRCW)：仅允许写入 相同数据PPRAM-CRCW(Priority PRAM-CRCW)：仅允许优先级 最高的处理器写入APRAM-CRCW(Arbitrary PRAM-CRCW)：允许任意处 理器自由写入 PRAM-CREW并发读互斥写 PRAM-EREW互斥读互斥写 29PRAM模型计算能力比较PRAM-CRCW是最强的计算模型，PRAM-EREW可 logp倍模拟PRAM-CREW和PRAM-CRCW 30PRAM模型证明
13、： 我们采用模拟论证。用一个运行时间为O(logP)的 EREW计算过程来模拟CRCW算法的每一步操作。因 为两种计算机的处理能力是相同的，所以我们仅重点 讨论存储器存取操作。在此我们仅对并发写操作进行 模拟以证明定理。对并发读操作的模拟与此类似。 我们引入一个长度为p的数组A，使EREW PRAM 中的p个处理器模拟CRCW算法中的并发写操作。 PRAM-EREW可logp倍模拟PRAM-CREW和PRAM-CRCW 31PRAM模型证明： 对i=0,1,p-1，当CRCW处理 器pi要求把一个数据xi写入存储 单元li时；每个相应的EREW处理器pi把 序对(li,xi)写入存储单元 Ai
14、中 。因为每个处理器对不同的存储 单元进行写操作，所以这些写操 作都是互斥的。然后，把数组A按其有序对的 第一个坐标在O(log p)的时间内 进行排序,这样就使得写到同一 个存储单元的所有数据在输出时 被放在一起。 32PRAM模型现在，对i=1,2,p-1，每个EREW处理器pi检查Ai=(lj,xj)， Ai-1=(lk,xk)其中0j,kp-1。如果ljlk或i=O，则对i=1,2,.,p-1，处理器pi把数据xj写到全 局存储器的存储单元lj中。否则处理器不作任何操作。因为数组A已按其第一个坐标排序，所以实际上只有一个对 任何给定存储单元执行写操作的处理器成功地执行操作，因 此该写操作是互斥的。所以这一过程在O(log p)时间里实现了 普通的CRCW模型中的并、发写操作
