并行计算模型

2023/12/22主要内容1.1并行计算机体系结构并行计算机的分类并行计算机的互连方式1.2并行计算模型

PRAM模型异步APRAM模型BSP模型LogP模型1.3并行算法的一般概念并行算法的定义和分类相关性与可并行化并行算法的表示并行算法的复杂度并行算法的WT表示加速比性能定律并行算法的同步和通讯2023/12/221.1并行计算机的体系结构:并行计算机分类Flynn分类（1966年）

(1)单指令流单数据流机SISD，即传统的单处理机(2)单指令流多数据流机SIMD(3)多指令流单数据流机MISD，实际中不存在的机器(4)多指令流多数据流机MIMD并行机的结构模型－实际的机器体系结构－SIMD(SingleInstructionMultipleData,单指令流多数据流机)

－PVP(ParallelVectorProcessor,并行向量机)

－SMP(SymmetricMultiprocessor,对称多处理机)

－MPP(MassivelyParallelProcessor,大规模并行处理机)

－COW(ClusterofWorkstation,工作站机群)

－DSM(DistributedSharedMemory,分布共享存储多处理机)

注：SIMD是专用并行机，后5种属于MIMD并行机。2023/12/22SISDcomputer-VonNeumann'smodel1.1并行计算机的体系结构:并行计算机分类SIMDcomputer2023/12/22Symmetricmultiprocessor–MIMD-SM1.1并行计算机的体系结构:并行计算机分类Massivelyparallelprocessor–MIMD-DM2023/12/22Clusterofworkstations–MIMD-DM1.1并行计算机的体系结构:并行计算机分类2023/12/22VPVPVP…交叉开关SM(a)PVPP/CP/CP/C…总线或交叉开关SM(b)SMP,物理上单一地址空间P/CP/CP/C…定制网络LMLMLM(c)MPP,物理/逻辑上多地址空间P/CP/CP/C…定制网络LMLMLM虚拟分布共享存储(DSM)(d)DSM(MPP/Cluster),逻辑上单一地址空间结构模型－物理机模型P/CP/CP/C…定制/标准网络LMLMLM(e)Cluster/COW,物理/逻辑上多地址空间1.1并行计算机的体系结构:并行计算机分类2023/12/22SMPMPPMPP…WANLMDSMSM(h)Grid(ClusterofClusters)SMPSMPSMP…SAN/LANSMSMSMMPPMPPMPP…SAN/LANDSMDSMDSM(f)SMP-Cluster(g)DSM-Cluster结构模型－物理机模型1.1并行计算机的体系结构:并行计算机分类2023/12/221.1并行计算机的体系结构:互连方式静态互连网络(固定连接)

connectedgraphvertices=processingnodesedges=communicationlinks(1)一维线性连接LA(1-DLinearArray)—一维阵列不带环绕的1-DLA，带环绕的1-DLA(2)网孔连接MC(MeshConnected)—二维阵列不带环绕的MC，带环绕的MC2023/12/221.1并行计算机的体系结构:互连方式静态互连网络

(3)树形连接TC(TreeConnected)二叉树，胖树2023/12/221.1并行计算机的体系结构:互连方式静态互连网络

(4)树网连接MT(Meshoftree)

2023/12/221.1并行计算机的体系结构:互连方式静态互连网络(5)金字塔连接(Pyramid)(6)超立方连接HC(HypercubeConnected)3－立方，4－立方(7)立方环连接CCC(CubeConnected-Cycles)(8)洗牌交换连接SE(ShuffleExchange)(9)蝶形连接(ButterflyConnected)2023/12/221.1并行计算机的体系结构:互连方式静态互连网络:嵌入将网络中的各节点映射到另一个网络中去用膨胀（Dilation）系数来描述嵌入的质量，它是指被嵌入网络中的一条链路在所要嵌入的网络中对应所需的最大链路数如果该系数为1，则称为完美嵌入。环网可完美嵌入到2-D环绕网中超立方网可完美嵌入到2－D环绕网中2023/12/221.1并行计算机的体系结构:互连方式静态互连网络:嵌入Ringonto2-Dtorus

Hypercubeonto2-Dtorus2023/12/221.1并行计算机的体系结构:互连方式动态互连网络(非固定连接)(1)总线Bus(2)交叉开关CrossbarSwitcher：一种高带宽网络(3)多级互连网络MultistageInterconnectionNetwork一种大型开关网络

2023/12/22主要内容1.1并行计算机体系结构并行计算机的分类并行计算机的互连方式1.2并行计算模型

PRAM模型异步APRAM模型BSP模型LogP模型1.3并行算法的一般概念并行算法的定义和分类相关性与可并行化并行算法的表示并行算法的复杂度并行算法的WT表示加速比性能定律并行算法的同步和通讯2023/12/221.2并行计算模型:PRAM模型描述由Fortune和Wyllie1978年提出，称为并行随机存取机器PRAM，又称SIMD-SM模型。有一个集中的共享存储器和一个指令控制器，通过SM的R/W交换数据，隐式同步计算。假设SM的容量无限有限/无限个功能相同的处理器本地指令和SM的R/W操作都取单位时间结构图ControlUnitInterconnectionNetworkPLMPLMPLMPLMSharedMemory2023/12/221.2并行计算模型:PRAM模型分类PRAM-CRCW并发读并发写CPRAM-CRCW(CommonPRAM-CRCW)：仅允许写入相同数据PPRAM-CRCW(PriorityPRAM-CRCW)：仅允许优先级最高的处理器写入APRAM-CRCW(ArbitraryPRAM-CRCW)：允许任意处理器自由写入PRAM-CREW并发读互斥写PRAM-EREW互斥读互斥写计算能力比较PRAM-CRCW是最强的计算模型，PRAM-EREW可logp倍模拟PRAM-CREW和PRAM-CRCW。令Tm是在模型M上的运行时间，则：1979年，Eckstain曾经使用二叉树方法来解决冲突问题解决读冲突：只允许一个PE从共享存储单元取内容。解决写冲突：用树作一种竞赛机构，确保仅有一个PE在写。2023/12/221.2并行计算模型:PRAM模型优点适合并行算法表示和复杂性分析，易于使用，隐藏了并行机的通讯、同步等细节。缺点不适合MIMD并行机，忽略了SM的竞争、通讯延迟等因素推广存储竞争模型：将Memory分成一些模块，每个模块一次可处理一个访问，可以在模块级处理存储器的竞争。延迟模型：考虑了信息的产生到能够使用之间的通信延迟

。局部PRAM模型：考虑了存储带宽，假定每个PE均有无限局存，而访问全局存储器是十分昂贵的。

分层存储模型：将存储器视为分层的存储模块，每个模块由其大小及传送时间表征。异步PRAM模型2023/12/221.2并行计算模型:SIMD-IN模型描述又称SIMD-DM模型，分布式存储，处理器通过互连网络相连，用传递数据方式实现通讯，算法时间复杂性考虑计算和选路(时间)，结构图如下：

常见模型SIMD-LC一维线性连接SIMD-MC网孔连接SIMD-TC树形连接SIMD-MT树网连接SIMD-HC超立方连接SIMD-CCC立方环连接SIMD-SE洗牌交换连接2023/12/221.2并行计算模型:异步APRAM模型描述又称分相（Phase）PRAM或MIMD-SM。每个处理器有其局部存储器、局部时钟、局部程序；无全局时钟，各处理器异步执行；处理器通过SM进行通讯；处理器间依赖关系，需在并行程序中显式地加入同步路障。指令类型(1)全局读(2)全局写(3)局部操作(4)同步

2023/12/221.2并行计算模型:异步APRAM模型计算过程由同步障分开的全局相组成

，*号表示局部操作。2023/12/221.2并行计算模型:异步APRAM模型计算时间

设局部操作为单位时间；全局读/写平均时间为d，d随着处理器数目的增加而增加；同步路障时间为B=B(p)非降函数。令为全局相内各处理器执行时间最长者，则APRAM上的计算时间为

优缺点

易编程和分析算法的复杂度，其上并行算法比较有限，不适合MIMD-DM模型。

2023/12/221.2并行计算模型:BSP模型描述由Valiant(1990)提出的，“块”同步模型，是一种异步MIMD-DM模型，支持消息传递系统，块内异步并行，块间显式同步。

模型参数p：处理器数(带有存储器)L：同步障时间(Barriersynchronizationtime)g：选路器吞吐率（带宽因子）发送一个消息所用的时间，带宽因子(timesteps/packet)=1/bandwidth2023/12/221.2并行计算模型:BSP模型计算过程由若干超级步组成，每个超级步计算模式为右图优缺点

强调了计算和通讯的分离，提供了一个编程环境，易于程序复杂性分析。但需要显式同步机制，限制至多h条消息的传递等。2023/12/221.2并行计算模型:LogP模型描述由Culler(1993)年提出的，是一种分布存储的、点到点通讯的多处理机模型，其中通讯由一组参数描述，实行隐式同步。模型参数L(Latency)：通迅延迟o(overhead)：通讯额外开销g(gap)：g=1/bandwidth,处理器可连续进行消息发送或接收的最小时间间隔P：#processors注：L和g反映了通讯网络的容量

2023/12/221.2并行计算模型:LogP模型优缺点捕捉了MPC的通讯瓶颈，隐藏了并行机的网络拓扑、路由、协议，可以应用到共享存储、消息传递、数据并行的编程模型中；但难以进行算法描述、设计和分析。BSPvs.LogPBSP

LogP：BSP块同步

BSP子集同步

BSP进程对同步＝LogPBSP可以常数因子模拟LogP，LogP可以对数因子模拟BSPBSP＝LogP+Barriers－OverheadBSP提供了更方便的程设环境，LogP更好地利用了机器资源BSP似乎更简单、方便和符合结构化编程

2023/12/221.2并行计算模型:各种计算模型比较模型属性PRAMAPRAMBSPLogPC3体系结构SIMD-SMMIMD-SMMIMD-DMMIMD-DMMIMD-DM计算模式同步异步异步异步异步同步方式自动同步路障同步路障同步隐式同步路障同步模型参数单位时间步d,读/写时间B,同步时间p,处理器数g,带宽因子l,同步间隔L,通信延迟o,额外开销g,带宽因子P,处理器数l,信包长度s,发送建立时间h,通信延迟计算粒度细粒度/中粒度中粒度/粗粒度中粒度/粗粒度中粒度/粗粒度粗粒度通信方式读/写共享变量读/写共享变量发送/接收消息发送/接收消息发送/接收消息地址空间全局地址空间单地址空间单/多地址空间单/多地址空间多地址空间2023/12/22主要内容1.1并行计算机体系结构并行计算机的分类并行计算机的互连方式1.2并行计算模型

PRAM模型异步APRAM模型BSP模型LogP模型1.3并行算法的一般概念并行算法的定义和分类相关性与可并行化并行算法的表示并行算法的复杂度并行算法的WT表示加速比性能定律并行算法的同步和通讯2023/12/221.3并行算法的一般概念:定义和分类并行算法

一组可同时执行且可互相协作的诸进程的集合。分类

VLSI并行算法：在VLSI计算模型上开发的并行算法

2023/12/221.3并行算法的一般概念:并行算法的表示par-do语句

fori=1tonpar-do

或fori=1tondoinparallel......endforendforforall语句

forallPi,where0≤i≤kdo...endfor2023/12/221.3并行算法的一般概念:并行算法的复杂度串行算法的度量一些记号平均情形复杂度、最坏情形复杂度2023/12/221.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)，0<Ep(n)<=1注：反映了并行系统中处理器的利用程度。工作量(或运算量)W(n)：并行算法所执行的总操作步数。(与处理器的数目无关)2023/12/221.3并行算法的一般概念:并行算法的WT表示Brent定理(1974JACM)

令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/12/221.3并行算法的一般概念:并行算法的WT表示Brent定理注：(1)揭示了并行算法工作量和运行时间的关系；

(2)提供了并行算法的WT(Work-Time)表示方法；(3)告诉我们：设计并行算法时应尽可能将每个时间步的工作量均匀地分摊给p台处理器，使各处理器处于活跃状态。2023/12/221.3并行算法的一般概念:并行算法的WT表示例1令n=2k(k>=0)，求n个数和的并行算法。算法运行时间：t(n)=O(logn)总运算量:由Brent定理知:t(n)=O(n/p+logn)

2023/12/221.3并行算法的一般概念:并行算法的WT表示2023/12/221.3并行算法的一般概念:加速比性能定律Amdahl’sLaw:BaseonFixedProblemSize适用于实时应用问题。当问题的计算负载或规模固定时，我们必须通过增加处理器数目来降低计算时间；设f是算法中不能并行的串行部分比例，Ws和Wp分别是串行和并行部分的工作量，则总工作量W=fW+(1-f)W=Ws+Wp；Amdahl’slaw表明：加速比受到算法中串行工作量的限制。公式推导2023/12/221.3并行算法的一般概念:加速比性能定律Gustafson’sLaw:BaseonFixedExecutionTime适用于要求精度高的应用，通过加大计算量来提高计算精度。Gustafson’sLaw表明：随着处理器数目的增加，串行执行部分f不再是并行算法的瓶颈。放大问题工作量或规模的加速公式推导：

与p成线性关系。2023/12/221.3并行算法的一般概念:加速比性能定律Sun&Ni’sLaw:BaseonMemoryBounding充分利用存储空间等计算资源，尽量增大问题规模以产生更好/更精确的解。是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/12/221.3并行算法的一般概念:并行算法的同步同步概念同步是在时间上强使各执行进程在某一点必须互相等待，确保各进程的正常顺序和对共享可写数据的正确访问；可用软件、硬件和固件的办法来实现。同步语句示例算法1.3APRAM上的求和算法输入：A=(a0,…,an-1),处理器数p

输出：S=ΣaiBegin(1)S=0(2.3)lock(S)(2)forallPiwhere0≤i≤p-1doS=S+L(2.1)L=0(2.4)unlock(S)(2.2)