并行算法的同步课件.ppt
2023/3/14,Parallel Algorithms Chapter 1 Foundation of Parallel Algorithms,Spring,2017,2023/3/14,主要内容,1.1 并行计算机体系结构并行计算机的分类并行计算机的互连方式1.2 并行计算模型 PRAM模型异步APRAM模型BSP模型LogP模型1.3 并行算法的一般概念并行算法的定义和分类相关性与可并行化并行算法的表示并行算法的复杂度并行算法的WT表示加速比性能定律并行算法的同步和通讯,2023/3/14,1.1 并行计算机的体系结构:并行计算机分类,Flynn分类（1966年）(1)单指令流单数据流机SISD，即传统的单处理机(2)单指令流多数据流机SIMD(3)多指令流单数据流机MISD，实际中不存在的机器(4)多指令流多数据流机MIMD并行机的结构模型实际的机器体系结构 SIMD(Single Instruction Multiple Data,单指令流多数据流机)PVP(Parallel Vector Processor,并行向量机)SMP(Symmetric Multiprocessor,对称多处理机)MPP(Massively Parallel Processor,大规模并行处理机)COW(Cluster of Workstation,工作站机群)DSM(Distributed Shared Memory,分布共享存储多处理机)注：SIMD是专用并行机，后5种属于MIMD并行机。,2023/3/14,SISD computer-Von Neumanns model,1.1 并行计算机的体系结构:并行计算机分类,SIMD computer,2023/3/14,Symmetric multiprocessor MIMD-SM,1.1 并行计算机的体系结构:并行计算机分类,Massively parallel processor MIMD-DM,2023/3/14,Cluster of workstations MIMD-DM,1.1 并行计算机的体系结构:并行计算机分类,2023/3/14,结构模型物理机模型,1.1 并行计算机的体系结构:并行计算机分类,2023/3/14,结构模型物理机模型,1.1 并行计算机的体系结构:并行计算机分类,2023/3/14,1.1 并行计算机的体系结构:互连方式,静态互连网络(固定连接)connected graph vertices=processing nodes edges=communication links(1)一维线性连接LA(1-D Linear Array)一维阵列 不带环绕的1-D LA，带环绕的1-D LA(2)网孔连接MC(Mesh Connected)二维阵列 不带环绕的MC，带环绕的MC,2023/3/14,1.1 并行计算机的体系结构:互连方式,静态互连网络(3)树形连接TC(Tree Connected)二叉树，胖树,2023/3/14,1.1 并行计算机的体系结构:互连方式,静态互连网络(4)树网连接MT(Mesh of tree),2023/3/14,1.1 并行计算机的体系结构:互连方式,静态互连网络(5)金字塔连接(Pyramid)(6)超立方连接HC(Hypercube Connected)3立方，4立方(7)立方环连接CCC(Cube Connected-Cycles)(8)洗牌交换连接SE(Shuffle Exchange)(9)蝶形连接(Butterfly Connected),2023/3/14,1.1 并行计算机的体系结构:互连方式,静态互连网络:嵌入将网络中的各节点映射到另一个网络中去用膨胀（Dilation）系数来描述嵌入的质量，它是指被嵌入网络中的一条链路在所要嵌入的网络中对应所需的最大链路数 如果该系数为1，则称为完美嵌入。环网可完美嵌入到2-D环绕网中 超立方网可完美嵌入到2D环绕网中,2023/3/14,1.1 并行计算机的体系结构:互连方式,静态互连网络:嵌入,Ring onto 2-D torus Hypercube onto 2-D torus,2023/3/14,1.1 并行计算机的体系结构:互连方式,动态互连网络(非固定连接)(1)总线Bus(2)交叉开关Crossbar Switcher：一种高带宽网络(3)多级互连网络Multistage Interconnection Network 一种大型开关网络,2023/3/14,主要内容,1.1 并行计算机体系结构并行计算机的分类并行计算机的互连方式1.2 并行计算模型 PRAM模型异步APRAM模型BSP模型LogP模型1.3 并行算法的一般概念并行算法的定义和分类相关性与可并行化并行算法的表示并行算法的复杂度并行算法的WT表示加速比性能定律并行算法的同步和通讯,2023/3/14,1.2 并行计算模型:PRAM模型,描述由Fortune和Wyllie1978年提出，称为并行随机存取机器PRAM，又称SIMD-SM模型。有一个集中的共享存储器和一个指令控制器，通过SM的R/W交换数据，隐式同步计算。假设SM的容量无限有限/无限个功能相同的处理器本地指令和SM的R/W操作都取单位时间结构图,2023/3/14,1.2 并行计算模型:PRAM模型,分类PRAM-CRCW并发读并发写CPRAM-CRCW(Common PRAM-CRCW)：仅允许写入相同数据PPRAM-CRCW(Priority PRAM-CRCW)：仅允许优先级最高的处理器写入APRAM-CRCW(Arbitrary PRAM-CRCW)：允许任意处理器自由写入 PRAM-CREW并发读互斥写 PRAM-EREW互斥读互斥写 计算能力比较PRAM-CRCW是最强的计算模型，PRAM-EREW可logp倍模拟PRAM-CREW和PRAM-CRCW。令Tm是在模型M上的运行时间，则：1979年，Eckstain曾经使用二叉树方法来解决冲突问题 解决读冲突：只允许一个PE从共享存储单元取内容。解决写冲突：用树作一种竞赛机构，确保仅有一个PE在写。,2023/3/14,1.2 并行计算模型:PRAM模型,优点适合并行算法表示和复杂性分析，易于使用，隐藏了并行机的通讯、同步等细节。缺点不适合MIMD并行机，忽略了SM的竞争、通讯延迟等因素推广存储竞争模型：将Memory分成一些模块，每个模块一次可处理一个访问，可以在模块级处理存储器的竞争。延迟模型：考虑了信息的产生到能够使用之间的通信延迟。局部PRAM模型：考虑了存储带宽，假定每个PE均有无限局存，而访问全局存储器是十分昂贵的。分层存储模型：将存储器视为分层的存储模块，每个模块由其大小及传送时间表征。异步PRAM模型,2023/3/14,1.2 并行计算模型:SIMD-IN模型,描述又称SIMD-DM模型，分布式存储，处理器通过互连网络相连，用传递数据方式实现通讯，算法时间复杂性考虑计算和选路(时间)，结构图如下：常见模型SIMD-LC 一维线性连接SIMD-MC 网孔连接SIMD-TC 树形连接SIMD-MT 树网连接SIMD-HC 超立方连接SIMD-CCC 立方环连接SIMD-SE 洗牌交换连接,2023/3/14,1.2 并行计算模型:异步APRAM模型,描述又称分相（Phase）PRAM或MIMD-SM。每个处理器有其局部存储器、局部时钟、局部程序；无全局时钟，各处理器异步执行；处理器通过SM进行通讯；处理器间依赖关系，需在并行程序中显式地加入同步路障。指令类型(1)全局读(2)全局写(3)局部操作(4)同步,2023/3/14,1.2 并行计算模型:异步APRAM模型,计算过程由同步障分开的全局相组成，*号表示局部操作。,2023/3/14,1.2 并行计算模型:异步APRAM模型,计算时间 设局部操作为单位时间；全局读/写平均时间为d，d随着处理器数目的增加而增加；同步路障时间为B=B(p)非降函数。令 为全局相内各处理器执行时间最长者，则APRAM上的计算时间为 优缺点 易编程和分析算法的复杂度，其上并行算法比较有限，不适合MIMD-DM模型。,2023/3/14,1.2 并行计算模型:BSP模型,描述由Valiant(1990)提出的，“块”同步模型，是一种异步MIMD-DM模型，支持消息传递系统，块内异步并行，块间显式同步。模型参数p：处理器数(带有存储器)L：同步障时间(Barrier synchronization time)g：选路器吞吐率（带宽因子）发送一个消息所用的时间，带宽因子(time steps/packet)=1/bandwidth,2023/3/14,1.2 并行计算模型:BSP模型,计算过程 由若干超级步组成，每个超级步计算模式为右图优缺点 强调了计算和通讯的分离，提供了一个编程环境，易于 程序复杂性分析。但需要显 式同步机制，限制至多h条 消息的传递等。,2023/3/14,1.2 并行计算模型:LogP模型,描述由Culler(1993)年提出的，是一种分布存储的、点到点通讯的多处理机模型，其中通讯由一组参数描述，实行隐式同步。模型参数L(Latency)：通迅延迟o(overhead)：通讯额外开销g(gap)：g=1/bandwidth,处理器可连续进行消息发送或接收的最小时间间隔P：#processors注：L和g反映了通讯网络的容量,2023/3/14,1.2 并行计算模型:LogP模型,优缺点 捕捉了MPC的通讯瓶颈，隐藏了并行机的网络拓扑、路由、协议，可以应用到共享存储、消息传递、数据并行的编程模型中；但难以进行算法描述、设计和分析。BSP vs.LogPBSPLogP：BSP块同步BSP子集同步BSP进程对同步LogPBSP可以常数因子模拟LogP，LogP可以对数因子模拟BSPBSPLogP+Barriers OverheadBSP提供了更方便的程设环境，LogP更好地利用了机器资源BSP似乎更简单、方便和符合结构化编程,2023/3/14,1.2 并行计算模型:各种计算模型比较,2023/3/14,主要内容,1.1 并行计算机体系结构并行计算机的分类并行计算机的互连方式1.2 并行计算模型 PRAM模型异步APRAM模型BSP模型LogP模型1.3 并行算法的一般概念并行算法的定义和分类相关性与可并行化并行算法的表示并行算法的复杂度并行算法的WT表示加速比性能定律并行算法的同步和通讯,2023/3/14,1.3 并行算法的一般概念:定义和分类,并行算法 一组可同时执行且可互相协作的诸进程的集合。分类 VLSI并行算法：在VLSI计算模型上开发的并行算法,2023/3/14,1.3 并行算法的一般概念:并行算法的表示,par-do语句 for i=1 to n par-do 或 for i=1 to n do in parallel.end for end forfor all语句 for all Pi,where 0ik do.end for,2023/3/14,1.3 并行算法的一般概念:并行算法的复杂度,串行算法的度量一些记号平均情形复杂度、最坏情形复杂度,2023/3/14,1.3 并行算法的一般概念:并行算法的复杂度,并行算法复杂性的度量运行时间t(n)：计算时间tc和选路(路由)时间tr处理器数目p(n)成本c(n)：c(n)=t(n)p(n)成本最优性：若c(n)等于在最坏情形下串行算法所需要的时间，则并行算法是成本最优的。加速比Sp(n)：Sp(n)=ts(n)/tp(n)，其中ts(n)为求解问题的最快的串行算法在最坏情形下所需的运行时间，tp(n)为求解同一问题的并行算法在最坏情形下的运行时间。注：(1)加速比Sp(n)反映算法的并行性对运行时间的改进程度。(2)若Sp(n)=p(n)，则达到线性加速；若Sp(n)p(n)，则为超线性加速(一般出现在某些特殊的应用中，如并行搜索等)。并行效率Ep(n)：Ep(n)=Sp(n)/p(n)，0Ep(n)=1 注：反映了并行系统中处理器的利用程度。工作量(或运算量)W(n)：并行算法所执行的总操作步数。(与处理器的数目无关),2023/3/14,1.3 并行算法的一般概念:并行算法的WT表示,Brent定理(1974 JACM)令W(n)是一并行算法A在运行时间T(n)内执行的运算量，则A使用p台处理器可在时间t(n)=O(W(n)/p+T(n)内执行完成。证明：设时刻 并行算法A做的工作量为Wi(即在(i-1,i时段内的工作量)=用p台处理器去完成并行算法A的第i时刻工作量，需时间=用p台处理器模拟并行算法A的总时间为,2023/3/14,1.3 并行算法的一般概念:并行算法的WT表示,Brent定理 注：(1)揭示了并行算法工作量和运行时间的关系；(2)提供了并行算法的WT(Work-Time)表示方法；(3)告诉我们：设计并行算法时应尽可能将每个时间步的工作量均匀地分摊给p台处理器，使各处理器处于活跃状态。,2023/3/14,1.3 并行算法的一般概念:并行算法的WT表示,例1 令n=2k(k=0)，求n个数和的并行算法。算法运行时间：t(n)=O(logn)总运算量:由Brent定理知:t(n)=O(n/p+logn),2023/3/14,1.3 并行算法的一般概念:并行算法的WT表示,2023/3/14,1.3 并行算法的一般概念:加速比性能定律,Amdahls Law:Base on Fixed Problem Size适用于实时应用问题。当问题的计算负载或规模固定时，我们必须通过增加处理器数目来降低计算时间；设 f 是算法中不能并行的串行部分比例，Ws和Wp分别是串行和并行部分的工作量，则总工作量W=fW+(1-f)W=Ws+Wp；Amdahls law表明：加速比受到算法中串行工作量的限制。公式推导,2023/3/14,1.3 并行算法的一般概念:加速比性能定律,Gustafsons Law:Base on Fixed Execution Time适用于要求精度高的应用，通过加大计算量来提高计算精度。Gustafsons Law表明：随着处理器数目的增加，串行执行部分f不再是并行算法的瓶颈。放大问题工作量或规模的加速公式推导：与p成线性关系。,2023/3/14,1.3 并行算法的一般概念:加速比性能定律,Sun&Nis Law:Base on Memory Bounding充分利用存储空间等计算资源，尽量增大问题规模以产生更好/更精确的解。是Amdahl定律和Gustafson定律的推广。公式推导：设单机上的存储器容量为M，其工作负载W=fW+(1-f)W 当并行系统有p个结点时，存储容量扩大了pM，用G(p)表示系统的存储容量增加p倍时工作负载的增加量。则存储容量扩大后的工作负载为W=fW+(1-f)G(p)W，所以，存储受限的加速为 特别地：当G(p)=1时，为Amdahl定律；当G(p)=p时，为Gustafson定律；,2023/3/14,1.3 并行算法的一般概念:并行算法的同步,同步概念同步是在时间上强使各执行进程在某一点必须互相等待，确保各进程的正常顺序和对共享可写数据的正确访问；可用软件、硬件和固件的办法来实现。同步语句示例算法1.3 APRAM上的求和算法 输入：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 for算法的时间复杂度：O(n/p+p),2023/3/14,1.3 并行算法的一般概念:并行算法的同步,2023/3/14,1.3 并行算法的一般概念:并行算法的通讯,通讯共享存储多处理器使用：global read(X,Y)/将SM中的X读入LM中的Y global write(U,V)/将LM中的U写入SM中的V分布存储多计算机使用：send(X,i)/处理器P发送X给处理器Pi receive(Y,j)/处理器P等待从Pj接收数据并存入LM中的Y通讯语句示例算法1.5 分布存储多计算机上矩阵向量乘法,通讯链为环 输入：处理器数p,A按列划分为p个B=Ai=A1.n,(i-1)r+1.ir,x划分为w=xi=x(i-1)r+1.ir,r=n/p,i=1p 输出：P1保存乘积AX Begin(1)Compute z=Bw(2)if i=1 then y=0 else receive(y,left)endif(3)y=y+z(4)send(y,right)(5)if i=1 then receive(y,left)End,2023/3/14,1.3 并行算法的一般概念:并行算法的通讯,计算过程图示,2023/3/14,1.3 并行算法的一般概念:并行算法的通讯,算法的复杂度,2023/3/14,1.3 并行算法的一般概念:并行算法的通讯,2023/3/14,End of Chapter 1,
