并行计算(中科大讲义)课件.ppt

1、并行计算国家高性能计算中心（合肥）25/31/2022并行计算结构算法编程 第一篇 并行计算的基础 第一章 并行计算机系统及其结构模型 第二章 当代并行机系统：SMP、MPP和Cluster 第三章 并行计算性能评测国家高性能计算中心（合肥）35/31/2022并行计算结构算法编程 第三篇 并行数值算法 第八章 基本通信操作 第九章 稠密矩阵运算 第十章 线性方程组的求解 第十一章 快速傅里叶变换国家高性能计算中心（合肥）45/31/2022第一章并行计算机系统及结构模型 1.1 并行计算 1.1.1 并行计算与计算科学 1.1.2 当代科学与工程问题的计算需求国家高性能计算中心（合肥）55/

2、31/2022并行计算 并行计算：并行机上所作的计算，又称高性能计算或超级计算。 计算科学：计算物理、计算化学、计算生物等 科学与工程问题的需求：气象预报、油藏模拟、核武器数值模拟、航天器设计、基因测序等。 需求类型：计算密集、数据密集、网络密集。 美国HPCC计划：重大挑战性课题，3T性能 美国Petaflops研究项目：Pflop/s。 美国ASCI计划：核武器数值模拟。国家高性能计算中心（合肥）65/31/2022高性能计算机 Intel（Option Red)：1Tflops,1997,Pentium Pro SGI(Option Blue Mountain): 3Tflops,199

3、8,MIPS10000 IBM(Option White): 7Tflops,Top4,2001,Power3 日本Earth Simulator: 35Tflops,Top1,2002,VP Hewlett-Packard ASCI Q： 7Tflops ,Top2,3,2002, Alpha Server 中国联想：1Tflops,Top43,2002国家高性能计算中心（合肥）75/31/2022系统互连 不同带宽与距离的互连技术: 总线、SAN、LAN、MAN、WAN局 部 总 线I/O总 线SCIHiPPIMyrinet千 兆 位以 太 网光 纤通 道快 速 以 太 网以 太 网10

4、Base TFDDIATM总 线 或 开 关SANLANMANWAN100Gb/s10Gb/s1Gb/s100Mb/s10Mb/sIsoEnet网络带宽交 叉 开 关MIN 或100 Base T国家高性能计算中心（合肥）85/31/2022局部总线、I/O总线、SAN和LANPMI/O桥磁盘SAN(e.g.Myrinet)LAN(e.g.以太网,FDDI)系统 III/O总线,接口系统 I处理器总线局部总线,存储器总线SCSI节点 2节点N系统总线节点 1国家高性能计算中心（合肥）95/31/2022网络性能指标 节点度（Node Degree）：射入或射出一个节点的边数。在单向网络中，入射

5、和出射边之和称为节点度。 网络直径（Network Diameter）： 网络中任何两个节点之间的最长距离，即最大路径数。 对剖宽度（Bisection Width） ：对分网络各半所必须移去的最少边数对剖带宽（ Bisection Bandwidth）:每秒钟内，在最小的对剖平面上通过所有连线的最大信息位（或字节）数 如果从任一节点观看网络都一样，则称网络为对称的（Symmetry） 国家高性能计算中心（合肥）105/31/2022静态互连网络 与动态互连网络 静态互连网络：处理单元间有着固定连接的一类网络，在程序执行期间，这种点到点的链接保持不变；典型的静态网络有一维线性阵列、二维网孔、树

6、连接、超立方网络、立方环、洗牌交换网、蝶形网络等 动态网络：用交换开关构成的，可按应用程序的要求动态地改变连接组态；典型的动态网络包括总线、交叉开关和多级互连网络等。国家高性能计算中心（合肥）115/31/2022静态互连网络（1） 一维线性阵列（1-D Linear Array）：2/N国家高性能计算中心（合肥）125/31/2022静态互连网络（2） 二维网孔（2-D Mesh）：) 1(2NN1NN22/2NN2NN (a)2-D网孔(b)Illiac网孔(c)2-D环绕国家高性能计算中心（合肥）135/31/2022静态互连网络（3） 二叉树：1log2N2/N(a)二叉树(b)星形连

7、接(c)二叉胖树国家高性能计算中心（合肥）145/31/2022静态互连网络（4） 超立方 ：nN22/N(b)4-立 方(a)3-立 方(c)顶 点 代 之 以 环(d)3-立 方 环国家高性能计算中心（合肥）155/31/2022嵌入 将网络中的各节点映射到另一个网络中去 用（Dilation）系数来描述嵌入的质量，它是指被嵌入网络中的一条链路在所要嵌入的网络中对应所需的最大链路数 如果该系数为1，则称为完美嵌入。 环网可完美嵌入到2-D环绕网中 超立方网可完美嵌入到2D环绕网中 国家高性能计算中心（合肥）165/31/2022嵌入10001001101110101100110111111

8、110010001010111011000000001001100100 01 10 01 10 01 10 00 00 00 00 00 00 00 00 01 10 01 11 11 10 01 11 10 00 00 01 10 00 00 01 11 11 11 10 01 11 11 10 00 01 10 00 00 01 10 00 01 11 11 11 11 11 11 11 10 01 10 01 10 01 10 01 11 1国家高性能计算中心（合肥）175/31/2022 NNNNNN NN NN nN2kkN21N1N2/N) 1(2N1N2/2N1log2N2/1

9、2kkNN2N22/N2/N)2/(kN1NN)(2NN N2N21N1N2/nN2/3N静态互连网络特性比较国家高性能计算中心（合肥）185/31/2022动态互连网络 (1)总线：PCI、VME、Multics、Sbus、MicroChannel L MI O C本 地 总 线高 速 缓 存C P UI FI FI F存 储 器 总 线存 储 器 单 元I FI FC P U 板存 储 器 板I / O 板通 信 板系 统 总 线( 底 板 上 )数 据 总 线缓 冲C CI O P数 据 总 线网 络( 以 太 网 等 )磁 盘 和 磁 带部 件打 印 机或 绘 图 仪本 地 外 围 设

10、 备( S C S I 总 线 )M CI F缓 冲国家高性能计算中心（合肥）195/31/2022动态互连网络 （2） 交叉开关（Crossbar）：国家高性能计算中心（合肥）205/31/2022动态互联网络 （3） 单级交叉开关级联起来形成多级互连网络MIN（Multistage Interconnection Network） 0101010101010101(a)4种可能的开关连接000001010011100101110111输入000001010011100101110111输出第0级第1级第2级(b)一种8输入的Omega网络国家高性能计算中心（合肥）215/31/2022动态

11、互连网络（4） 交换开关模块： 一个交换开关模块有n个输入和n个输出，每个输入可连接到任意输出端口，但只允许一对一或一对多的映射，不允许多对一的映射，因为这将发生输出冲突 n2log22国家高性能计算中心（合肥）225/31/2022动态互连网络比较 n,节点规模 w，数据宽度 )(wnO)log(wnnOk)(2wnO)/(nwfO)(wfO)(wfO)(wfO国家高性能计算中心（合肥）235/31/2022标准互联网络（1） Myrinet:国家高性能计算中心（合肥）245/31/2022Myrinet连接的LAN/Cluster交换开关交换开关交换开关交换开关桌面主机机箱内多计算机机群多

12、处理机机群网络RAM和VME 单板磁盘国家高性能计算中心（合肥）255/31/2022标准互连网络（2) 高性能并行接口（HiPPI）国家高性能计算中心（合肥）265/31/2022使用HiPPI通道和开关构筑的LAN主干网 HiPPI交 换 开 关超 级 计 算 机帧 缓 冲 器RGB显 示 器HiPPI串 行文 件服 务 器工 作 站小 型 机大 规 模 并 行处 理 系 统25米300米25米25米HiPPI串 行300米直 至 10千 米300米HiPPI串 行存 储 器服 务 器工 作 站光 纤 扩 展 器光 纤 扩 展 器HiPPI交 换 开 关国家高性能计算中心（合肥）275/3

13、1/2022标准互连网络（3） 光纤通道FC（Fiber Channel） : 通道和网络标准的集成 光纤通道既可以是共享介质，也可以是一种交换技术 光纤通道操作速度范围可从100到133、200、400和800Mbps。FCSI厂商也正在推出未来具有更高速度（1、2或4Gbps）的光纤通道 光纤通道的价值已被现在的某些千兆位局域网所证实，这些局域网就是基于光纤通道技术的 连网拓扑结构的灵活性是光纤通道的主要财富，它支持点到点、仲裁环及交换光纤连接 国家高性能计算中心（合肥）285/31/2022双向FDDI环作为主干网 文件服务器数据库服务器计算机服务器双向 FDDI环FDDI集中器FDDI

14、 集中器FDDI 集中器桌面计算机以太网集线器路由器国家高性能计算中心（合肥）295/31/2022标准互联网络（4） ATM（Asynchronous Transfer Mode）:国家高性能计算中心（合肥）305/31/2022香港大学开发的Pearl机群 ASX-200BXLAX-20HARNETPower集 线 器 7000IBMSP2城 市 大 学 的 WS池浸 会 大 学的 WS池USC的IMSCXL服 务 器PCFDDIPC和WS去 USA主 干 因 特 网SunE-6000服 务 器(8 CPU)以 太 网工 作 站 池HP服 务 器SunE-4000SunUltraSPARC

15、2/1200Sun SPARC20/HS14以 太 网T3T1155Mb/sASX-1000ATM开 关T1T1155Mb/s155Mb/sSGI PowerChallenge(8CPU)32节 点 ）(国家高性能计算中心（合肥）315/31/2022标准互连网络（5）国家高性能计算中心（合肥）325/31/2022并行计算机结构模型 P/CLMNIC定制网络(c)MPPP/CLMNICMBMBVPSM交叉开关(a)PVPVPVPSMSMP/CSMSMI/O总线或交叉开关(b)SMPP/CP/CP/CLMNICDIRMB定制网络(d)DSMP/CLMNICDIRMBLDP/CMMBIOB(e)

16、COWLDP/CMMBIOB商品网络(以太网，ATM，etc.)BridgeNICNICBridge国家高性能计算中心（合肥）335/31/2022并行计算机体系合一结构 SMP、MPP、DSM和COW并行结构渐趋一致。CPNIC(a)无 共 享NIC互 连 网 络MD节 点N节 点1Shell共 享 磁 盘CPNIC(b)共 享 磁 盘NICM互 连 网 络节 点N节 点1ShellCP互 连 网 络共 享 存 储 器共 享 磁 盘(c)共 享 存 储CPShellShell国家高性能计算中心（合肥）345/31/2022五种结构特性一览表属性PVPSMPMPPDSMCOW结构类型MIMDM

17、IMDMIMDMIMDMIMD处理器类型专用定制商用商用商用商用互连网络定制交叉开关总线、交叉开关定制网络定制网络商用网络（以太ATM）通信机制共享变量共享变量消息传递共享变量消息传递地址空间单地址空间单地址空间多地址空间单地址空间多地址空间系统存储器集中共享集中共享分布非共享分布共享分布非共享访存模型UMAUMANORMANUMANORMA代表机器Cray C-90，Cray T-90，银河1号IBM R50，S G I P o w e r Challenge，曙光1号Intel Paragon， IBMSP2，曙光1000/2000Stanford DASH，Cray T 3DBerkel

18、ey NOW，Alpha Farm国家高性能计算中心（合肥）355/31/2022并行计算机访存模型（1)P1P2PnI/OSM1SMm共享存储器处理器（）系统互连总线 交叉开关多级,网络 UMA国家高性能计算中心（合肥）365/31/2022并行计算机访存模型（2) NUMA(Nonuniform Memory Access)LM1P1LM2P2LMnPn互连网络(a)共享本地存储模型全局互连网络(b)层次式机群模型GSMGSMGSMPCINCSMPPCSMCSM群1PCINCSM群NPPCSMCSM国家高性能计算中心（合肥）375/31/2022并行计算机访存模型（3) COMA(Cach

19、e-Only Memory Access)互 连 网 络DCPDCPDCP国家高性能计算中心（合肥）385/31/2022并行计算机访存模型（4) CC-NUMAI/ONIC,DIR,RC系统互连网路MemP/CP/CI/ONIC,DIR,RCMemP/CP/C节点N节点1总线或交叉 开关总线或交叉 开关国家高性能计算中心（合肥）395/31/2022并行计算机访存模型（5)消息传递互连网络(网络，环网，超立方，立方环等)PMPMMPMPMPMPMPPMPMPM.国家高性能计算中心（合肥）405/31/2022构筑并行机系统的不同存储结构MIMDMIMD多计算机(多地址空间非共享存储器)(IB

20、M SP2,DEC TruClusterTandem Hymalaya,HP,Microsoft Wolfpack,etc)NORMANORMAUMAUMANUMANUMAClusterClusterMPPMPP(Intel TFLOPS)紧耦合PVPPVP(Cray T90)SMPSMP(Intel SHV,SunFire,DEC 8400,SGI PowerChallenge,IBMR60,etc.)COMACOMA(KSR-1,DDM)CC-NUMACC-NUMA(Stanford Dash,SGI Origin 2000,Sequent NUMA-Q,HP/Convex Exempla

21、r)NCC-NUMANCC-NUMA(Cray T3E)DSMDSM(TreadMarks,Wind Tunnel,IVY,Shrimp,etc.)（）松散耦合（）中央存储器分布存储器多处理机单地址共享（）空间存储器国家高性能计算中心（合肥）415/31/2022第二章 当代并行机系统 2.1 共享存储多处理机系统 2.1.1 对称多处理机SMP结构特性国家高性能计算中心（合肥）425/31/2022对称多处理机SMP(1)SMP: 采用商用微处理器，通常有片上和片外Cache，基于总线连接，集中式共享存储，UMA结构 例子：SGI Power Challenge, DEC Alpha Ser

22、ver,Dawning 1P / CS MS MI / O总线或交叉开关P / CP / C国家高性能计算中心（合肥）435/31/2022对称多处理机SMP(2)优点 对称性 单地址空间，易编程性，动态负载平衡，无需显示数据分配 高速缓存及其一致性，数据局部性，硬件维持一致性 低通信延迟，Load/Store完成国家高性能计算中心（合肥）445/31/2022大规模并行机MPP成百上千个处理器组成的大规模计算机系统，规模是变化的。NORMA结构，高带宽低延迟定制互连。可扩放性：Mem, I/O,平衡设计系统成本：商用处理器，相对稳定的结构，SMP,分布通用性和可用性：不同的应用，PVM,MP

23、I,交互，批处理，互连对用户透明，单一系统映象，故障通信要求存储器和I/O能力例子：Intel Option Red IBM SP2 Dawning 1000P/CLMNIC定 制 网 络P/CLMNICMBMB国家高性能计算中心（合肥）455/31/2022典型MPP系统特性比较MPP模型Intel/Sandia ASCI Option RedIBM SP2SGI/Cray Origin2000一个大型样机的配置9072个处理器，1.8Tflop/s(NSL)400个处理器，100Gflop/s(MHPCC)128个处理器，51Gflop/s(NCSA)问世日期1996年12月1994年9月

24、1996年10月处理器类型200MHz, 200Mflop/s Pentium Pro67MHz，267Mflop/s POWER2200MHz，400Mflop/s MIPS R10000节点体系结构和数据存储器2个处理器，32到256MB主存，共享磁盘1个处理器，64MB到2GB本地主存，1GB到14.5GB本地磁盘2个处理器，64MB到256MB分布共享主存和共享磁盘互连网络和主存模型分离两维网孔，NORMA多级网络，NORMA胖超立方体网络，CC-NUMA节点操作系统轻量级内核（LWK）完全AIX（IBM UNIX）微内核Cellular IRIX自然编程机制基于PUMA Portal

25、s的MPIMPI和PVMPower C， Power Fortran其他编程模型Nx，PVM，HPFHPF，LindaMPI，PVM国家高性能计算中心（合肥）465/31/2022MPP所用的高性能CPU特性比较属性Pentium ProPowerPC 602Alpha 21164AUltra SPARC IIMIPS R10000工艺BiCMOSCMOSCMOSCMOSCMOS晶体管数5.5M/15.5M7M9.6M5.4M6.8M时钟频率150MHz133MHz417MHz200MHz200MHz电压2.9V3.3V2.2V2.5V3.3V功率20W30W20W28W30W字长32位64位

26、64位64位64位I/O高速缓存8KB/8KB32KB/32KB8KB/8KB16KB/16KB32KB/32KB2级高速缓存256KB(多芯片模块)1128MB(片外)96KB(片上)16MB(片外)16MB(片外)执行单元5个单元6个单元4个单元9个单元5个单元超标量3路(Way)4路4路4路4路流水线深度14级48级79级9级57级SPECint 92366225500350300SPECfp 92283300750550600SPECint 958.0922511N/A7.4SPECfp 956.7030017N/A15其它特性CISC/RISC混合短流水线长L1高速缓存最高时钟频率最

27、大片上2级高速缓存多媒体和图形指令MP机群总线可支持4个CPU国家高性能计算中心（合肥）475/31/2022机群型大规模并行机SP2 设计策略： 机群体系结构 标准环境 标准编程模型 系统可用性 精选的单一系统映像 NICDE 节 点 1NICDE 节 点S以 太 网PMCCMCCPPPN高 性 能Omega，网 络开 关I/O总 线I/O总 线国家高性能计算中心（合肥）485/31/2022工作站机群COW分布式存储，MIMD，工作站+商用互连网络，每个节点是一个完整的计算机，有自己的磁盘和操作系统，而MPP中只有微内核优点：投资风险小系统结构灵活性能/价格比高能充分利用分散的计算资源可扩

28、放性好P/CMMIOMIOMP/CNICNICDDLAN国家高性能计算中心（合肥）495/31/2022典型的机群系统典型的机群系统特点一览表名称系统特点Princeton:SHRIMPPC商用组件，通过专用网络接口达到共享虚拟存储，支持有效通信Karsruhe:Parastation用于分布并行处理的有效通信网络和软件开发Rice:TreadMarks软件实现分布共享存储的工作站机群Wisconsin:Wind Tunnel在经由商用网络互连的工作站机群上实现分布共享存储C h i c a 、 M a r y l 、Penns:NSCP国家可扩放机群计划：在通过因特网互连的3个本地机群系统上

29、进行元计算Argonne:Globus在由ATM连接的北美17个站点的WAN上开发元计算平台和软件Syracuse:WWVM使用因特网和HPCC技术，在世界范围的虚拟机上进行高性能计算HKU:Pearl Cluster研究机群在分布式多媒体和金融数字库方面的应用Virgina:Legion在国家虚拟计算机设施上开发元计算软件国家高性能计算中心（合肥）505/31/2022SMPMPP机群比较系统特征SMPMPP机群节点数量(N)O(10)O(100)-O(1000)O(100)节点复杂度中粒度或细粒度细粒度或中粒度中粒度或粗粒度节点间通信 共享存储器消息传递或共享变量（有DSM时）消息传递节点

30、操作系统1N(微内核)和1个主机OS(单一)N (希望为同构)支持单一系统映像永远部分希望地址空间单一多或单一（有DSM时）多个作业调度单一运行队列主机上单一运行队列协作多队列网络协议非标准非标准标准或非标准可用性通常较低低到中高可用或容错性能/价格比一般一般高互连网络总线/交叉开关定制商用国家高性能计算中心（合肥）515/31/2022第三章 并行计算性能评测 3.1 并行机的一些基本性能指标 3.2 加速比性能定律 3.2.1 Amdahl定律 3.2.2 Gustafson定律 3.2.3 Sun和Ni定律国家高性能计算中心（合肥）525/31/2022CPU的某些基本性能指标 工作负载

31、TnTTTnTn11,max国家高性能计算中心（合肥）535/31/2022存储器性能 存储器的层次结构(C,L,B) 估计存储器的带宽 RISC add r1,r2,r3 r 8bytes 100MHz B = 3*8*100*106 B/s= 2.4GB/s寄 存 器1级高 速 缓 存2级高 速 缓 存主 存磁 盘远 程存 储 器Cp时，相应于计算机负载比存储要求增加得快，此时 Sun和 N i 加速均比 Amdahl 加速和 Gustafson 加速为高。 T1Tp执行时间T处 理 器 数P (b)T1T1T1T1T1TpTpTpTpTp处 理 器 数P工作负载W (a)W1WpWpWp

32、WpWpWpW1W1W1W1W1123456123456国家高性能计算中心（合肥）675/31/2022加速比讨论 参考的加速经验公式： p/log pSP 线性加速比：很少通信开销的矩阵相加、内积运算等 p/log p的加速 比：分治类的应用问题 通信密集类的应用问题 ：S = 1 / C （ p ） 超线性加速 绝对加速：最佳并行算法与串行算法 相对加速：同一算法在单机和并行机的运行时间国家高性能计算中心（合肥）685/31/2022可扩放性评测标准并行计算的可扩放性（Scalability）也是主要性能指标 可扩放性最简朴的含意是在确定的应用背景下，计算机系统（或算法或程序等）性能随处理

33、器数的增加而按比例提高的能力 国家高性能计算中心（合肥）695/31/2022可扩放性评测标准（contd) 可扩放性:调整什么和按什么比例调整 并行计算要调整的是处理数p和问题规模W， 两者可按不同比例进行调整，此比例关系（可能是线性的，多项式的或指数的等）就反映了可扩放的程度。 国家高性能计算中心（合肥）705/31/2022等效率度量标准 令tie 和t io 分别是并行系统上第i个处理器的有用计算时间和额外开销时间（包括通信、同步和空闲等待时间等） T p 是p个处理器系统上并行算法的运行时间，对于任意i显然有T p = tie +t io ，且 T e+ T o= pT p 问题的规

34、模W为最佳串行算法所完成的计算量W=Te 如果问题规模W 保持不变，处理器数p增加，开销To增大，效率E下降。为了维持一定的效率（介于0与1之间），当处理数p增大时，需要相应地增大问题规模W的值。由此定义函数f E（p）为问题规模W随处理器数p变化的函数，为等效率函数（ISO-efficiency Function）（Kumar1987） 10piieeTstT10piiootTWTpTTppTTTTTSoeooeepe11WTTTPSEoeo1111国家高性能计算中心（合肥）715/31/2022等效率度量标准（contd) 曲线1表示算法具有很好的扩放性；曲线2表示算法是可扩放的；曲线 3

35、表示算法是不可扩放的。 优点：简单可定量计算的、少量的参数计算等效率函数 缺点：如果To无法计算出（在共享存储并行机中）处理器数 P工作负载W曲线3曲线2曲线1国家高性能计算中心（合肥）725/31/2022等速度度量标准 p 表示处理器个数，W表示要求解问题的工作量或称问题规模（在此可指浮点操作个数），T为并行执行时间，定义并行计算的速度V为工作量W除以并行时间T p个处理器的并行系统的平均速度定义为并行速度V除以处理器个数 p：W是使用p个处理器时算法的工作量，令W表示当处理数从p增大到p时，为了保持整个系统的平均速度不变所需执行的工作量，则可得到处理器数从 p到p时平均速度可扩放度量标准

36、公式 pTWpVV/ /) ,(pWWppWpWpp国家高性能计算中心（合肥）735/31/2022等速度度量标准（contd）问题规模处理器数执行时间处理器数处理器数平均速度处理器数执行时间 优点：直观地使用易测量的机器性能速度指标来度量 缺点：某些非浮点运算可能造成性能的变化国家高性能计算中心（合肥）745/31/2022平均延迟度量标准 Ti为Pi的执行时间，包括包括延迟Li，Pi的总延迟时间为“L i+启动时间+停止时间”。定义系统平均延迟时间为pTpara =To+ Ts 在p个处理器上求解工作量为W问题的平均延迟 在p个处理器上求解工作量为W问题的平均延迟当处理器数由p变到p，而推

37、持并行执行效率不变，则定义平均延迟可扩放性度量标准为 pLTTpWLpiiipara1,pWLpTo,pTTpWLseqpara, ,pWLpWLppEpWL, pWL国家高性能计算中心（合肥）755/31/2022平均延迟度量标准（Contd)处理器数PT1T2T3T4T5T6T7T8T5 = Tpara执行时间Tpara54321P1P2P3P4P5P6P7P8开销延迟 Li启动前与结束后空闲时间运行时间 Ti 优点：平均延迟能在更低层次上衡量机器的性能 缺点：需要特定的软硬件才能获得平均延迟并 行 计 算第二篇 并行算法的设计 第四章 并行算法的设计基础 第五章 并行算法的一般设计方法

38、第六章 并行算法的基本设计技术 第七章 并行算法的一般设计过程第四章 并行算法的设计基础 4.1 并行算法的基础知识 4.2 并行计算模型4.1 并行算法的基础知识 4.1.1 并行算法的定义和分类 4.1.2 并行算法的表达 4.1.3 并行算法的复杂性度量 4.1.4 并行算法中的同步和通讯国家高性能计算中心（合肥）805/31/2022 并行算法的定义和分类 并行算法的定义 算法 并行算法：一些可同时执行的诸进程的集合，这些进程互相作用和协调动作从而达到给定问题的求解。4.1 并行算法的基础知识 4.1.1 并行算法的定义和分类 4.1.2 并行算法的表达 4.1.3 并行算法的复杂性度

39、量 4.1.4 并行算法中的同步和通讯国家高性能计算中心（合肥）825/31/2022 并行算法的表达 描述语言 可以使用类Algol、类Pascal等； 在描述语言中引入并行语句。4.1 并行算法的基础知识 4.1.1 并行算法的定义和分类 4.1.2 并行算法的表达 4.1.3 并行算法的复杂性度量 4.1.4 并行算法中的同步和通讯国家高性能计算中心（合肥）845/31/2022 并行算法的复杂性度量 串行算法的复杂性度量 最坏情况下的复杂度(Worst-CASE Complexity) 期望复杂度(Expected Complexity)国家高性能计算中心（合肥）855/31/2022

40、 并行算法的复杂性度量 Brent定理4.1 并行算法的基础知识 4.1.1 并行算法的定义和分类 4.1.2 并行算法的表达 4.1.3 并行算法的复杂性度量 4.1.4 并行算法中的同步和通讯国家高性能计算中心（合肥）875/31/2022 并行算法的同步 同步概念 同步是在时间上强使各执行进程在某一点必须互相等待； 可用软件、硬件和固件的办法来实现。国家高性能计算中心（合肥）885/31/2022 并行算法的通讯 通讯 共享存储多处理器使用：global read(X,Y)和global write(X,Y) 分布存储多计算机使用：send(X,i)和receive(Y,j)第四章 并行

41、算法的设计基础 4.1 并行算法的基础知识 4.2 并行计算模型4.2 并行计算模型 4.2.1 PRAM模型 4.2.2 异步APRAM模型 4.2.3 BSP模型 4.2.4 logP模型国家高性能计算中心（合肥）915/31/2022 PRAM模型 基本概念 由Fortune和Wyllie1978年提出，又称SIMD-SM模型。有一个集中的共享存储器和一个指令控制器，通过SM的R/W交换数据，隐式同步计算。Control UnitInterconnection NetworkPLMPLMPLMPLMShared Memory国家高性能计算中心（合肥）925/31/2022 PRAM模型

42、分类CRCWCREWEREWTTTCRCWCREWEREWTTT)log()log(pTOpTOTCRCWCREWEREW国家高性能计算中心（合肥）935/31/2022 PRAM模型 优点 适合并行算法表示和复杂性分析，易于使用，隐藏了并行机的通讯、同步等细节。4.2 并行计算模型 4.2.1 PRAM模型 4.2.2 异步APRAM模型 4.2.3 BSP模型 4.2.4 logP模型国家高性能计算中心（合肥）955/31/2022 异步APRAM模型 基本概念 又称分相（Phase）PRAM或MIMD-SM。每个处理器有其局部存储器、局部时钟、局部程序；无全局时钟，各处理器异步执行；处理

43、器通过SM进行通讯；处理器间依赖关系，需在并行程序中显式地加入同步路障。国家高性能计算中心（合肥）965/31/2022 异步APRAM模型计算过程国家高性能计算中心（合肥）975/31/2022 异步APRAM模型 计算时间 设局部操作为单位时间；全局读/写平均时间为d，d随着处理器数目的增加而增加；同步路障时间为B=B(p)非降函数。 满足关系 ； 或 令 为全局相内各处理器执行时间最长者，则APRAM上的计算时间为 优缺点 易编程和分析算法的复杂度，但与现实相差较远，其上并行算法非常有限，也不适合MIMD-DM模型。pBd2 )log()(pdOpBB)log/log(dpdOpht同步

44、障次数BtTph4.2 并行计算模型 4.2.1 PRAM模型 4.2.2 异步APRAM模型 4.2.3 BSP模型 4.2.4 logP模型国家高性能计算中心（合肥）995/31/2022 BSP模型 基本概念 由Valiant(1990)提出的，“块”同步模型，是一种异步MIMD-DM模型，支持消息传递系统，块内异步并行，块间显式同步。 国家高性能计算中心（合肥）1005/31/2022 BSP模型计算过程由若干超级步组成，每个超级步计算模式为左图优缺点 强调了计算和通讯的分离， 提供了一个编程环境，易于 程序复杂性分析。但需要显 式同步机制，限制至多h条 消息的传递等。4.2 并行计算

45、模型 4.2.1 PRAM模型 4.2.2 异步APRAM模型 4.2.3 BSP模型 4.2.4 logP模型国家高性能计算中心（合肥）1025/31/2022 logP模型 基本概念 由Culler(1993)年提出的，是一种分布存储的、点到点通讯的多处理机模型，其中通讯由一组参数描述，实行隐式同步。国家高性能计算中心（合肥）1035/31/2022 logP模型优缺点 捕捉了MPC的通讯瓶颈，隐藏了并行机的网络拓扑、路由、协议，可以应用到共享存储、消息传递、数据并行的编程模型中；但难以进行算法描述、设计和分析。 并 行 计 算第二篇 并行算法的设计 第四章 并行算法的设计基础 第五章 并

46、行算法的一般设计方法 第六章 并行算法的基本设计技术 第七章 并行算法的一般设计过程第五章 并行算法的一般设计方法 5.1 串行算法的直接并行化 5.2 从问题描述开始设计并行算法 5.3 借用已有算法求解新问题 5.1串行算法的直接并行化 5.1.1 设计方法描述 5.1.2 快排序算法的并行化国家高性能计算中心（合肥）1085/31/2022 设计方法的描述 方法描述 发掘和利用现有串行算法中的并行性，直接将串行算法改造为并行算法。5.1串行算法的直接并行化 5.1.1 设计方法描述 5.1.2 快排序算法的并行化国家高性能计算中心（合肥）1105/31/2022 快排序算法的并行化 算法

47、5.2 PRAM-CRCW上的快排序二叉树构造算法 输入：序列(A1,An)和n个处理器 输出：供排序用的一棵二叉排序树 Begin (1)for each processor i do (2)repeat for each processor iroot do (1.1)root=i if (AiAfi)(Ai=Afiifi) then (1.2)fi=root (2.1)LCfi=i (1.3)LCi=RCi=n+1 (2.2)if i=LCfi then exit else fi=LCfi endif end for else (2.3)RCfi=i (2.4)if i=RCfi the

48、n exit else fi=RCfi endif endif end repeat End第五章 并行算法的一般设计方法 5.1 串行算法的直接并行化 5.2 从问题描述开始设计并行算法 5.3 借用已有算法求解新问题 国家高性能计算中心（合肥）1125/31/2022 从问题描述开始设计并行算法 方法描述 从问题本身描述出发，不考虑相应的串行算法，设计一个全新的并行算法。第五章 并行算法的一般设计方法 5.1 串行算法的直接并行化 5.2 从问题描述开始设计并行算法 5.3 借用已有算法求解新问题 5.3 借用已有算法求解新问题 5.3.1 设计方法描述 5.3.2 利用矩阵乘法求所有点对

49、间最短路径国家高性能计算中心（合肥）1155/31/2022 设计方法的描述 方法描述 找出求解问题和某个已解决问题之间的联系； 改造或利用已知算法应用到求解问题上。5.3 借用已有算法求解新问题 5.3.1 设计方法描述 5.3.2 利用矩阵乘法求所有点对间最短路径国家高性能计算中心（合肥）1175/31/2022 利用矩阵乘法求所有点对间最短路径 计算原理 有向图G=(V,E)，边权矩阵W=(wij)nn，求最短路径长度矩阵D=(dij)nn，dij为vi到vj的最短路径长度。假定图中无负权有向回路，记d(k)ij为vi到vj至多有k-1个中间结点的最短路径长，Dk=(d(k)ij)nn，

50、则 (1) d(1)ij=wij 当 ij (如果vi到vj之间无边存在记为) d(1)ij=0 当 i=j (2) 无负权回路 dijd(n-1)ij (3) 利用最优性原理：d(k)ij=min1并 行 计 算第二篇 并行算法的设计 第四章 并行算法的设计基础 第五章 并行算法的一般设计方法 第六章 并行算法的基本设计技术 第七章 并行算法的一般设计过程第六章 并行算法的基本设计技术 6.1 划分设计技术 6.2 分治设计技术 6.3 平衡树设计技术 6.4 倍增设计技术 6.5 流水线设计技术 6.1 划分设计技术 6.1.1 均匀划分技术 6.1.2 方根划分技术 6.1.3 对数划分