《[互联网]第3章分布式系统中的并行计算.ppt》由会员分享，可在线阅读，更多相关《[互联网]第3章分布式系统中的并行计算.ppt（36页珍藏版）》请在三一文库上搜索。
1、第三章 分布式计算环境下的 并行计算,本章主要内容,数据相关性和可并行化 并行算法的定义与分类 并行计算模型 并行算法性能分析 并行算法的语言结构 并行算法应用举例,相关性与可并行化,伯恩斯坦准则 I1O2，即P1的输入变量集与P2的输出变量集不相交； I2O1，即P2的输入变量集与P1的输出变量集不相交； O1O2，即P1和P2的输出变量集不相交 可并行处理,数据相关,P1： AB+C P2： DAB 其中，变量A是导致P1和P2发生数据相关的原因。为了保证程序执行的语义正确性，变量A必须是先在P1中写入后方可从P2中读出，即必须先写后读。 显然，P1和P2不能并行执行。,数据反相关,P1：
2、 ABC P2： CE+D P1通过变量C数据相关于P2。为保证语义正确性，必须等P1将变量C读出后，P2方可向变量C进行写入操作，即必须先读后写。 也不可并行化,数据输出相关,P1： AB+C P2： ADE 为保证语义正确性，必须保证P1先写入A，然后允许P2再写入A。 P1和P2不可并行执行,并行算法的定义与分类,算法是解题的精确描述 并行算法是一些可同时执行的诸进程的集合，这些进程互相作用和协调从而达到给定问题的求解。 并行算法就是对并行计算过程的精确描述 并行算法可以从不同的角度分类为 数值计算并行算法和非数值计算并行算法 同步并行算法和异步并行算法 共享存储并行算法和分布存储并行算
3、法,数值算法与非数值算法,数值计算是指基于代数关系运算的计算问题 如矩阵运算、多项式求值、线性代数方程组求解等。求解数值计算问题的算法称为数值算法（Numerical Algorithm）。 科学与工程中的计算问题如计算力学、计算物理、计算化学等一般是数值计算问题。 非数值计算是指基于比较关系运算的计算问题 诸如排序、选择、搜索、匹配等符号处理，相应的算法也称为非数值算法（Non-numerical Algorithm）。 非数值计算在符号类信息处理中获得广泛应用，如数据库领域的计算问题、海量数据挖掘等， 近年来广泛关注的生物信息学主要也是非数值计算,并行算法的表达,描述语言 可以使用类Alg
4、ol、类Pascal等 在描述语言中引入并行语句。 并行语句示例 Par-do语句 for i=1 to n par-do end for for all语句 for all Pi,where 0ik end for,并行算法的复杂性度量,串行算法的复杂性度量 最坏情况下的复杂度 期望复杂度 并行算法的复杂性度量指标 运行时间t(n)：包含计算时间和通信时间 处理器数p(n) 并行算法成本c(n)：c(n)=t(n)p(n) 总运算量w(n)：并行算法求解问题时所完成的总的操作步数。,并行计算模型,计算模型是对计算机的抽象 计算模型为设计、分析和评价算法提供基础 冯.偌依曼机就是一个理想的串行
5、计算模型 但现在还没有一个通用的并行计算模型,常见的并行计算模型,PRAM模型：由Fortune和Wyllie1978年提出，又称SIMD-SM模型。有一个集中的共享存储器和一个指令控制器，通过SM的R/W交换数据。 异步模型(APRAM) ：又称分相(Phase)PRAM或MIMD-SM。每个处理器有其局部存储器、局部时钟、局部程序。 BSP模型：块同步模型，是一种异步MIMD-DM模型，支持消息传递系统，块内异步并行，块间显式同步。 logP模型：由Culler(1993)年提出，是一种分布存储的、点到点通讯的多处理机模型。,PRAM模型,PRAM（Parallel Random Acce
6、ss Machine）模型，即并行随机存取模型，是一种抽象的并行计算模型。 假设存在着一个容量无限大的共享存储器； 每台处理器有简单的算术运算和逻辑判断功能； 在任何时刻各处理器均可以通过共享存储单元交换数据。,PRAM模型,C：Concurrent(允许并发操作)E：Exclusive(排斥并发操作) PRAM模型又可以细分为 PRAM-EREW模型：在同一时刻只允许一个处理器对同一存储单元进行读/写，但不允许多个存储器对同一存储单元同时读/写。 PRAM-CREW模型：在同一时刻允许多个处理器对同一存储单元并发读但不允许并发写。 PRAM-ERCW模型：在同一时刻允许多个处理器对同一存储单
7、元并发写但不允许并发读。 PRAM-CRCW模型：在同一时刻允许多个处理器对同一存储单元并发读和并发写。,PRAM模型,SIMD-PRAM计算模型,PRAM模型,优点：适合并行算法表示和复杂性分析，易于使用，隐藏了并行机的通讯、同步等细节。 缺点：不适合MIMD并行机，忽略了SM的竞争、通讯延迟等因素。 不现实，首先容量无限大的存储器是不存在的；其次全局访问通常要比预想的慢；最后PRAM忽略了通信带宽的影响。,APRAM模型,指令类型 全局读：将全局存储单元中的内容读入局部存储单元中。 局部操作：对局存中的数执行操作，其结果存入局存中。 全局写：将局存单元中的内容写入全局存储单元中。 同步：是
8、计算中的一个逻辑点，在该点各处理器均需等待别的处理器到达后才能继续执行其局部程序。,APRAM模型,优缺点 易编程和分析算法复杂度，但与现实相差较远，其并行算法非常有限。,BSP(Bulk Synchronous Parallel)模型,模型参数 p:处理器数(带有存储器) l:同步障时间(全局同步之间的时间间隔) g:选路器吞吐量(带宽因子) s:处理器计算速度。 优缺点： 强调了计算和通讯的分离，提供了一个编程环境，易于程序复杂性分析。但需要显式同步机制。,LogP 模型,充分说明了互连网络的性能特点，而未涉及网络的结构。模型主要由4个参数描述。 L（Latency） 源处理机与目的处理机
9、进行消息（一个或几个字）通信所需要的等待或延迟时间的上限。 o（overhead） 处理机准备发送或准备接受每个消息的时间开销（包括操作系统核心开销和网络软件开销），在这段时间里处理机不能执行其他操作。 g（gap） 一台处理机连续两次发送或连续两次接受消息时的最小时间间隔，其倒数即为处理机的通信带宽。 P（Processor） 处理机的个数。,LogP 模型,揭示了分布存储并行计算机的性能瓶颈，用L、o、g三个参数刻画了通信网络的特性， 但屏蔽了网络拓扑、选路算法和通信协议等具体细节 参数g反映了通信带宽 在任何时刻，最多只能有L/g条消息从一个处理器传到另一个处理器，这就是网络容限，当一台
10、处理机发送的消息达到这个容限时，在发送的消息就会被阻塞； 设想LogP模型中的L、o、g都为0，那么LogP模型就等同于PRAM模型,各种计算模型比较,并行算法的性能评价,计算时间（时间复杂度） 需要的处理器个数 需要的机器模型 加速比与并行效率,加速比定律,在给定的并行计算系统上给定的应用，并行算法（并行程序）的执行速度相对于串行算法（串行程序）加快的倍数，就是该并行算法（并行程序）的加速比。 对于同一个要解决的问题，假设其串行算法时间复杂度为Ts,并行算法的时间复杂度为Tp,处理器复杂度为P，则 加速比=Ts/Tp 效率=Ts/PTp,并行算法的语言结构,结构1 FOR variable=
11、1 TO n DO IN PARALLEL S1 S2 END PARALLEL n个处理器中的每一个同时执行相同的指令S1，S2Sn。FOR语句的运行变量variable表示处理器的下标。,并行算法的语言结构,结构2： FOR xS DO IN PARALLEL S1 S2 END PARALLEL 每个处理器同时执行相同的指令S1，S2。同时运行的处理器个数是S中元素的个数。,基于二叉树网络模型的并行算法,问题1：对N个数的求和 网络模型：二叉树 输入：数组A（1:n）,n=2k 输出：数组值的总和存于A(1)中,BEGIN P=n/2 WHILE p0 DO FOR i=1 TO p D
12、O IN PARALLEL A(i)=A(2i-1)+A(2i) END PARALLEL p=p/2 END WHILE RESULT=A(1) END,算法分析,时间复杂度：O(1bn) 处理器复杂度：O(n) 并行模型：PRAM-EREW,并行算法应用例题,例题：当n=8时，在二叉树环境下，计算8个数的累加和。(51，17，42，34，85，11，19，54) 解： 1、将8个数分成两组，每组4个数 组1：A(1),A(3),A(5),A(7) 组2：A(2),A(4),A(6),A(8) 2、使用4个处理器，分别执行组1和组2对应数的相加操作，包括三个阶段 第一阶段： A(1) A(1
13、)+ A(2)=68 A(2) A(3)+ A(4)=76 A(3) A(5)+ A(6)=96 A(4) A(7)+ A(8)=73 第二阶段： A(1) A(1)+ A(2)=144 A(2) A(3)+ A(4)=169 第三阶段： A(1) A(1)+ A(2)=313（最后结果）,二叉数设计环境下8个数的求和图,问题2：求任意两个向量的内积 计算模型：PRAM-EREW 输入：数组a(1:n)和数组b(1:n) 输出：内积的值存于变量c1中 条件：两个向量a=(a1,a2an),b=(b1,b2bn),ab=a1b1+a2b2+anbn,并行算法实现,BEGIN FOR i=1 TO
14、 n DO IN PARALLEL ci=ai*bi END PARALLEL p=n/2 WHILE p0 DO FOR i=1 TO p DO IN PARALLEL ci=ci+ci+p END PARALLEL p=P/2 END WHILE END,算法分析,时间复杂度：O(1bn) 处理器复杂度：O(n) 并行模型：PRAM-EREW,串行程序并行化的几个步骤,从一个串行程序得到一个并行程序的工作由四个步骤构成： 1. 将计算的问题分解成任务 2. 将任务分配给进程 3. 在进程之间组织必要的数据访问， 通信和同步。 4. 将进程映射或绑定到处理器,参考书： 1、陈国良著.并行算法的设计与分析.高等教育出版社.2009.8 2、陈国良著.并行计算结构算法编程(修订版).高等教育出版社.2005.10,