Title,This is our 1st Level Bullet,This is our 2nd level bullet,This is our 3rd level bullet,This is our next 1st Level Bullet,This is our 2nd level bullet,This is our 3rd level bullet,*,并行算法,*,/Ch1,并行算法,1,/Ch1,Title,This is our 1st Level Bullet,This is our 2nd level bullet,This is our 3rd level bullet,This is our next 1st Level Bullet,This is our 2nd level bullet,This is our 3rd level bullet,*,2024/10/21,Parallel Algorithms,Chapter,1,Foundation of Parallel Algorithms,Spring,2018,2023/8/6Parallel Algorithms,2024/10/21,主要内容,1.1,并行计算机体系结构,并行计算机的分类,并行计算机的互连方式,1.2,并行计算模型,PRAM,模型,异步,APRAM,模型,BSP,模型,LogP,模型,1.3,并行算法的一般概念,并行算法的定义和分类,相关性与可并行化,并行算法的表示,并行算法的复杂度,并行算法的,WT,表示,加速比性能定律,并行算法的同步和通讯,2023/8/6主要内容1.1 并行计算机体系结构,2024/10/21,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/8/61.1 并行计算机的体系结构:并行计算机分,2024/10/21,SISD computer-Von Neumanns model,1.1,并行计算机的体系结构,:,并行计算机分类,SIMD computer,2023/8/6SISD computer-Von Neu,2024/10/21,Symmetric multiprocessor,MIMD-SM,1.1,并行计算机的体系结构,:,并行计算机分类,Massively parallel processor,MIMD-DM,2023/8/6Symmetric multiprocess,2024/10/21,Cluster of workstations,MIMD-DM,1.1,并行计算机的体系结构,:,并行计算机分类,2023/8/6Cluster of workstation,2024/10/21,VP,VP,VP,交叉开关,SM,(a)PVP,P/C,P/C,P/C,总线或交叉开关,SM,(b)SMP,物理上单一地址空间,P/C,P/C,P/C,定制网络,LM,LM,LM,(c)MPP,物理,/,逻辑上多地址空间,P/C,P/C,P/C,定制网络,LM,LM,LM,虚拟分布共享存储,(DSM),(d)DSM(MPP/Cluster),逻辑上单一地址空间,结构模型,物理机模型,P/C,P/C,P/C,定制,/,标准网络,LM,LM,LM,(e)Cluster/COW,物理,/,逻辑上多地址空间,1.1,并行计算机的体系结构,:,并行计算机分类,2023/8/6VPVPVP交叉开关SM(a)PVPP/,2024/10/21,SMP,MPP,MPP,WAN,LM,DSM,SM,(h)Grid(Cluster of Clusters),SMP,SMP,SMP,SAN/LAN,SM,SM,SM,MPP,MPP,MPP,SAN/LAN,DSM,DSM,DSM,(f)SMP-Cluster,(g)DSM-Cluster,结构模型,物理机模型,1.1,并行计算机的体系结构,:,并行计算机分类,2023/8/6SMPMPPMPPWANLMDSMSM(h,2024/10/21,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/8/61.1 并行计算机的体系结构:互连方式静态,2024/10/21,1.1,并行计算机的体系结构,:,互连方式,静态互连网络,(3),树形连接,TC(Tree Connected),二叉树，胖树,2023/8/61.1 并行计算机的体系结构:互连方式静态,2024/10/21,1.1,并行计算机的体系结构,:,互连方式,静态互连网络,(4),树网连接,MT(Mesh of tree),2023/8/61.1 并行计算机的体系结构:互连方式静态,2024/10/21,1.1,并行计算机的体系结构,:,互连方式,静态互连网络,(5),金字塔连接,(Pyramid),(6),超立方连接,HC(Hypercube Connected),3,立方，,4,立方,(7),立方环连接,CCC(Cube Connected-Cycles),(8),洗牌交换连接,SE(Shuffle Exchange),(9),蝶形连接,(Butterfly Connected),2023/8/61.1 并行计算机的体系结构:互连方式静态,2024/10/21,1.1,并行计算机的体系结构,:,互连方式,静态互连网络,:,嵌入,将网络中的各节点映射到另一个网络中去,用膨胀（,Dilation,）系数来描述嵌入的质量，它是指被嵌入网络中的一条链路在所要嵌入的网络中对应所需的最大链路数,如果该系数为,1,，则称为完美嵌入。
环网可完美嵌入到,2-D,环绕网中,超立方网可完美嵌入到,2,D,环绕网中,2023/8/61.1 并行计算机的体系结构:互连方式静态,2024/10/21,1.1,并行计算机的体系结构,:,互连方式,静态互连网络,:,嵌入,Ring onto 2-D torus,Hypercube onto 2-D torus,2023/8/61.1 并行计算机的体系结构:互连方式静态,2024/10/21,1.1,并行计算机的体系结构,:,互连方式,动态互连网络,(,非固定连接,),(1),总线,Bus,(2),交叉开关,Crossbar Switcher,：一种高带宽网络,(3),多级互连网络,Multistage Interconnection Network,一种大型开关网络,2023/8/61.1 并行计算机的体系结构:互连方式动态,2024/10/21,主要内容,1.1,并行计算机体系结构,并行计算机的分类,并行计算机的互连方式,1.2,并行计算模型,PRAM,模型,异步,APRAM,模型,BSP,模型,LogP,模型,1.3,并行算法的一般概念,并行算法的定义和分类,相关性与可并行化,并行算法的表示,并行算法的复杂度,并行算法的,WT,表示,加速比性能定律,并行算法的同步和通讯,2023/8/6主要内容1.1 并行计算机体系结构,2024/10/21,1.2,并行计算模型,:,PRAM,模型,描述,由,Fortune,和,Wyllie1978,年提出，称为并行随机存取机器,PRAM,，又称,SIMD-SM,模型。
有一个集中的共享存储器和一个指令控制器，通过,SM,的,R/W,交换数据，隐式同步计算假设,SM,的容量无限,有限,/,无限个功能相同的处理器,本地指令和,SM,的,R/W,操作都取单位时间,结构图,Control Unit,Interconnection Network,P,LM,P,LM,P,LM,P,LM,Shared Memory,2023/8/61.2 并行计算模型:PRAM模型描述Co,2024/10/21,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/8/61.2 并行计算模型:PRAM模型分类,2024/10/21,1.2,并行计算模型,:,PRAM,模型,优点,适合并行算法表示和复杂性分析，易于使用，隐藏了并行机的通讯、同步等细节,缺点,不适合,MIMD,并行机，忽略了,SM,的竞争、通讯延迟等因素,推广,存储竞争模型：,将,Memory,分成一些模块，每个模块一次可处理一个访问，可以在模块级处理存储器的竞争延迟模型：,考虑了信息的产生到能够使用之间的通信延迟,局部,PRAM,模型：,考虑了存储带宽，假定每个,PE,均有无限局存，而访问全局存储器是十分昂贵的分层存储模型：,将存储器视为分层的存储模块，每个模块由其大小及传送时间表征异步,PRAM,模型,2023/8/61.2 并行计算模型:PRAM模型优点,2024/10/21,1.2,并行计算模型,:,SIMD-IN,模型,描述,又称,SIMD-DM,模型，分布式存储，处理器通过互连网络相连，用传递数据方式实现通讯，算法时间复杂性考虑计算和选路,(,时间,),，结构图如下：,常见模型,SIMD-LC,一维线性连接,SIMD-MC,网孔连接,SIMD-TC,树形连接,SIMD-MT,树网连接,SIMD-HC,超立方连接,SIMD-CCC,立方环连接,SIMD-SE,洗牌交换连接,2023/8/61.2 并行计算模型:SIMD-IN模型描,2024/10/21,1.2,并行计算模型,:,异步,APRAM,模型,描述,又称分相（,Phase,）,PRAM,或,MIMD-SM,。
每个处理器有其局部存储器、局部时钟、局部程序；无全局时钟，各处理器异步执行；处理器通过,SM,进行通讯；处理器间依赖关系，需在并行程序中显式地加入同步路障指令类型,(,1),全局读,(2),全局写,(3),局部操作,(4),同步,2023/8/61.2 并行。
