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

并行计算,结构算法编程,国家高性能计算中心（合肥）,2,2022/12/14,并行计算结构算法编程,第一篇 并行计算的基础第一章 并行计算机系统及其结构模型第二章 当代并行机系统：SMP、MPP和Cluster第三章 并行计算性能评测第二篇 并行算法的设计第四章 并行算法的设计基础第五章 并行算法的一般设计方法第六章 并行算法的基本设计技术第七章 并行算法的一般设计过程,国家高性能计算中心（合肥）,3,2022/12/14,并行计算结构算法编程,第三篇 并行数值算法第八章 基本通信操作第九章 稠密矩阵运算第十章 线性方程组的求解第十一章 快速傅里叶变换第四篇 并行程序设计第十二章 并行程序设计基础第十三章 并行程序设计模型和共享存储系统编程第十四章 分布存储系统并行编程第十五章 并行程序设计环境与工具,国家高性能计算中心（合肥）,4,2022/12/14,第一章并行计算机系统及结构模型,1.1 并行计算1.1.1 并行计算与计算科学1.1.2 当代科学与工程问题的计算需求1.2 并行计算机系统互连1.2.1 系统互连1.2.2 静态互联网络1.2.3 动态互连网络1.2.4 标准互联网络1.3 并行计算机系统结构1.3.1 并行计算机结构模型1.3.2 并行计算机访存模型,国家高性能计算中心（合肥）,5,2022/12/14,并行计算,并行计算：并行机上所作的计算，又称高性能计算或超级计算。计算科学：计算物理、计算化学、计算生物等科学与工程问题的需求：气象预报、油藏模拟、核武器数值模拟、航天器设计、基因测序等。需求类型：计算密集、数据密集、网络密集。美国HPCC计划：重大挑战性课题，3T性能美国Petaflops研究项目：Pflop/s。美国ASCI计划：核武器数值模拟。,国家高性能计算中心（合肥）,6,2022/12/14,高性能计算机,Intel（Option Red)：1Tflops,1997,Pentium ProSGI(Option Blue Mountain): 3Tflops,1998,MIPS10000IBM(Option White): 7Tflops,Top4,2001,Power3日本Earth Simulator: 35Tflops,Top1,2002,VPHewlett-Packard ASCI Q： 7Tflops ,Top2,3,2002, Alpha Server中国联想：1Tflops,Top43,2002,国家高性能计算中心（合肥）,7,2022/12/14,系统互连,不同带宽与距离的互连技术: 总线、SAN、LAN、MAN、WAN,国家高性能计算中心（合肥）,8,2022/12/14,局部总线、I/O总线、SAN和LAN,国家高性能计算中心（合肥）,9,2022/12/14,网络性能指标,节点度（Node Degree）：射入或射出一个节点的边数。在单向网络中，入射和出射边之和称为节点度。网络直径（Network Diameter）： 网络中任何两个节点之间的最长距离，即最大路径数。对剖宽度（Bisection Width） ：对分网络各半所必须移去的最少边数对剖带宽（ Bisection Bandwidth）:每秒钟内，在最小的对剖平面上通过所有连线的最大信息位（或字节）数如果从任一节点观看网络都一样，则称网络为对称的（Symmetry）,国家高性能计算中心（合肥）,10,2022/12/14,静态互连网络 与动态互连网络,静态互连网络：处理单元间有着固定连接的一类网络，在程序执行期间，这种点到点的链接保持不变；典型的静态网络有一维线性阵列、二维网孔、树连接、超立方网络、立方环、洗牌交换网、蝶形网络等动态网络：用交换开关构成的，可按应用程序的要求动态地改变连接组态；典型的动态网络包括总线、交叉开关和多级互连网络等。,国家高性能计算中心（合肥）,11,2022/12/14,静态互连网络（1）,一维线性阵列（1-D Linear Array）：并行机中最简单、最基本的互连方式，每个节点只与其左、右近邻相连，也叫二近邻连接，N个节点用N-1条边串接之，内节点度为2，直径为N-1，对剖宽度为1当首、尾节点相连时可构成循环移位器，在拓扑结构上等同于环，环可以是单向的或双向的，其节点度恒为2，直径或为 （双向环）或为N-1（单向环），对剖宽度为2,国家高性能计算中心（合肥）,12,2022/12/14,静态互连网络（2）,二维网孔（2-D Mesh）：每个节点只与其上、下、左、右的近邻相连（边界节点除外），节点度为4，网络直径为 ，对剖宽度为 在垂直方向上带环绕，水平方向呈蛇状，就变成Illiac网孔了，节点度恒为4，网络直径为 ，而对剖宽度为 垂直和水平方向均带环绕，则变成了2-D环绕（2-D Torus），节点度恒为4，网络直径为 ，对剖宽度为,国家高性能计算中心（合肥）,13,2022/12/14,静态互连网络（3）,二叉树：除了根、叶节点，每个内节点只与其父节点和两个子节点相连。节点度为3，对剖宽度为1，而树的直径为 如果尽量增大节点度为，则直径缩小为2，此时就变成了星形网络，其对剖宽度为传统二叉树的主要问题是根易成为通信瓶颈。胖树节点间的通路自叶向根逐渐变宽。,国家高性能计算中心（合肥）,14,2022/12/14,静态互连网络（4）,超立方 ：一个n-立方由 个顶点组成，3-立方如图(a)所示；4-立方如图(b)所示，由两个3-立方的对应顶点连接而成。n-立方的节点度为n，网络直径也是n ，而对剖宽度为 。如果将3-立方的每个顶点代之以一个环就构成了如图(d)所示的3-立方环，此时每个顶点的度为3，而不像超立方那样节点度为n。,国家高性能计算中心（合肥）,15,2022/12/14,嵌入,将网络中的各节点映射到另一个网络中去用膨胀（Dilation）系数来描述嵌入的质量，它是指被嵌入网络中的一条链路在所要嵌入的网络中对应所需的最大链路数 如果该系数为1，则称为完美嵌入。 环网可完美嵌入到2-D环绕网中 超立方网可完美嵌入到2D环绕网中,国家高性能计算中心（合肥）,16,2022/12/14,嵌入,国家高性能计算中心（合肥）,17,2022/12/14,静态互连网络特性比较,国家高性能计算中心（合肥）,18,2022/12/14,动态互连网络 (1),总线：PCI、VME、Multics、Sbus、MicroChannel 多处理机总线系统的主要问题包括总线仲裁、中断处理、协议转换、快速同步、高速缓存一致性协议、分事务、总线桥和层次总线扩展等,国家高性能计算中心（合肥）,19,2022/12/14,动态互连网络 （2）,交叉开关（Crossbar）：单级交换网络，可为每个端口提供更高的带宽。象电话交换机一样，交叉点开关可由程序控制动态设置其处于“开”或“关”状态，而能提供所有（源、目的）对之间的动态连接。交叉开关一般有两种使用方式：一种是用于对称的多处理机或多计算机机群中的处理器间的通信；另一种是用于SMP服务器或向量超级计算机中处理器和存储器之间的存取。,国家高性能计算中心（合肥）,20,2022/12/14,动态互联网络 （3）,单级交叉开关级联起来形成多级互连网络MIN（Multistage Interconnection Network）,国家高性能计算中心（合肥）,21,2022/12/14,动态互连网络（4）,交换开关模块： 一个交换开关模块有n个输入和n个输出，每个输入可连接到任意输出端口，但只允许一对一或一对多的映射，不允许多对一的映射，因为这将发生输出冲突 级间互连（Interstage Connection ）：均匀洗牌、蝶网、多路均匀洗牌、交叉开关、立方连接n输入的网络需要 级 开关，在Ilinois大学的Cedar2多处理机系统中采用了网络 Cray Y/MP多级网络，该网络用来支持8个向量处理器和256个存储器模块之间的数据传输。网络能够避免8个处理器同时进行存储器存取时的冲突。,国家高性能计算中心（合肥）,22,2022/12/14,动态互连网络比较,n,节点规模 w，数据宽度,国家高性能计算中心（合肥）,23,2022/12/14,标准互联网络（1）,Myrinet:Myrinet是由Myricom公司设计的千兆位包交换网络，其目的是为了构筑计算机机群，使系统互连成为一种商业产品。Myrinet是基于加州理工学院开发的多计算机和VLSI技术以及在南加州大学开发的ATOMIC/LAN技术。Myrinet能假设任意拓扑结构，不必限定为开关网孔或任何规则的结构。Myrinet在数据链路层具有可变长的包格式，对每条链路施行流控制和错误控制，并使用切通选路法以及定制的可编程的主机接口。在物理层上，Myrinet网使用全双工SAN链路，最长可达3米，峰值速率为（1.281.28）Gbps（目前有2.56+2.56)Myrinet交换开关 :8,12,16端口Myrinet主机接口 : 32位的称作LANai芯片的用户定制的VLSI处理器，它带有Myrinet接口、包接口、DMA引擎和快速静态随机存取存储器SRAM。140 of the November 2002 TOP500 use Myrinet, including 15 of the top 100,国家高性能计算中心（合肥）,24,2022/12/14,Myrinet连接的LAN/Cluster,国家高性能计算中心（合肥）,25,2022/12/14,标准互连网络（2),高性能并行接口（HiPPI）Los Alamos国家实验室于1987年提出的一个标准，其目的是试图统一来自不同产商生产的所有大型机和超级计算机的接口。在大型机和超级计算机工业界，HiPPI作为短距离的系统到系统以及系统到外设连接的高速I/O通道。1993年，ANSI X3T9.3委员会认可了HiPPI标准，它覆盖了物理和数据链路层，但在这两层之上的任何规定却取决于用户。HiPPI是个单工的点到点的数据传输接口，其速率可达800Mbps到1.6Gbps。开发成功了一种能提供潜在的6.4Gbps速率，比HiPPI快8倍且有很低时延的超级HiPPI技术，SGI公司和Los Alamos国家实验室都开发了用来构筑速率高达25.6Gbps的HiPPI交换开关的HiPPI技术。HiPPI通道和HiPPI交换开关被用在SGI Power Challenge服务器、IBM 390主机、Cray Y/MP、C90和T3D/T3E等系统,国家高性能计算中心（合肥）,26,2022/12/14,使用HiPPI通道和开关构筑的LAN主干网,国家高性能计算中心（合肥）,27,2022/12/14,标准互连网络（3）,光纤通道FC（Fiber Channel） :通道和网络标准的集成 光纤通道既可以是共享介质，也可以是一种交换技术 光纤通道操作速度范围可从100到133、200、400和800Mbps。FCSI厂商也正在推出未来具有更高速度（1、2或4Gbps）的光纤通道 光纤通道的价值已被现在的某些千兆位局域网所证实，这些局域网就是基于光纤通道技术的 连网拓扑结构的灵活性是光纤通道的主要财富，它支持点到点、仲裁环及交换光纤连接 FDDI :光纤分布式数据接口FDDI（Fiber Distributed Data Interface）FDDI采用双向光纤令牌环可提供100-200Mbps数据传输速率 FDDI具有互连大量设备的能力 传统的FDDI仅以异步方式操作,国家高性能计算中心（合肥）,28,2022/12/14,双向FDDI环作为主干网,国家高性能计算中心（合肥）,29,2022/12/14,标准互联网络（4）,ATM（Asynchronous Transfer Mode）:由成立于1991年的ATM论坛和ITU标准定义。ATM是一种独立于介质的消息传输协议，它将消息段变成更短的固定长度为53字节的报元进行传输。这种技术是基于报元交换机制。ATM的目的是将实时和突发数据的传输合并成单一的网络技术。ATM网络支持从25到51、155和622Mbps不同的速率，其速率越低ATM交换器和使用的链路价格越低。,国家高性能计算中心（合肥）,30,2022/12/14,香港大学开发的Pearl机群,国家高性能计算中心（合肥）,31,2022/12/14,标准互连网络（5）,国家高性能计算中心（合肥）,32,2022/12/14,并行计算机结构模型,国家高性能计算中心（合肥）,33,2022/12/14,并行计算机体系合一结构,SMP、MPP、DSM和COW并行结构渐趋一致。大量的节点通过高速网络互连起来节点遵循Shell结构：用专门定制的Shell电路将商用微处理器和节点的其它部分（包括板级Cache、局存、NIC和DISK）连接起来。优点是CPU升级只需要更换Shell。,国家高性能计算中心（合肥）,34,2022/12/14,五种结构特性一览表,国家高性能计算中心（合肥）,35,2022/12/14,并行计算机访存模型（1),UMA（Uniform Memory Access）模型是均匀存储访问模型的简称。其特点是：物理存储器被所有处理器均匀共享；所有处理器访问任何存储字取相同的时间；每台处理器可带私有高速缓存；外围设备也可以一定形式共享。,国家高性能计算中心（合肥）,36,2022/12/14,并行计算机访存模型（2),NUMA(Nonuniform Memory Access)模型是非均匀存储访问模型的简称。特点是：被共享的存储器在物理上是分布在所有的处理器中的，其所有本地存储器的集合就组成了全局地址空间；处理器访问存储器的时间是不一样的；访问本地存储器LM或群内共享存储器CSM较快，而访问外地的存储器或全局共享存储器GSM较慢(此即非均匀存储访问名称的由来)；每台处理器照例可带私有高速缓存，外设也可以某种形式共享。,国家高性能计算中心（合肥）,37,2022/12/14,并行计算机访存模型（3),COMA(Cache-Only Memory Access)模型是全高速缓存存储访问的简称。其特点是：各处理器节点中没有存储层次结构，全部高速缓存组成了全局地址空间；利用分布的高速缓存目录D进行远程高速缓存的访问;COMA中的高速缓存容量一般都大于2 级高速缓存容量；使用COMA时，数据开始时可任意分配，因为在运行时它最终会被迁移到要用到它们的地方。,国家高性能计算中心（合肥）,38,2022/12/14,并行计算机访存模型（4),CC-NUMA（Coherent-Cache Nonuniform Memory Access）模型是高速缓存一致性非均匀存储访问模型的简称。其特点是：大多数使用基于目录的高速缓存一致性协议；保留SMP结构易于编程的优点，也改善常规SMP的可扩放性；CC-NUMA实际上是一个分布共享存储的DSM多处理机系统；它最显著的优点是程序员无需明确地在节点上分配数据，系统的硬件和软件开始时自动在各节点分配数据，在运行期间，高速缓存一致性硬件会自动地将数据迁移至要用到它的地方。,国家高性能计算中心（合肥）,39,2022/12/14,并行计算机访存模型（5),NORMA（No-Remote Memory Access）模型是非远程存储访问模型的简称。NORMA的特点是：所有存储器是私有的；绝大数NUMA都不支持远程存储器的访问；在DSM中，NORMA就消失了。,国家高性能计算中心（合肥）,40,2022/12/14,构筑并行机系统的不同存储结构,国家高性能计算中心（合肥）,41,2022/12/14,第二章 当代并行机系统,2.1 共享存储多处理机系统2.1.1 对称多处理机SMP结构特性2.2 分布存储多计算机系统2.2.1 大规模并行机MPP结构特性2.3 机群系统2.3.1 大规模并行处理系统MPP机群SP22.3.2 工作站机群COW,国家高性能计算中心（合肥）,42,2022/12/14,对称多处理机SMP(1),SMP: 采用商用微处理器，通常有片上和片外Cache，基于总线连接，集中式共享存储，UMA结构例子：SGI Power Challenge, DEC Alpha Server,Dawning 1,国家高性能计算中心（合肥）,43,2022/12/14,对称多处理机SMP(2),优点对称性单地址空间，易编程性，动态负载平衡，无需显示数据分配高速缓存及其一致性，数据局部性，硬件维持一致性低通信延迟，Load/Store完成问题欠可靠，BUS,OS,SM通信延迟（相对于CPU），竞争加剧慢速增加的带宽（MB double/3年,IOB更慢）不可扩放性-CC-NUMA,国家高性能计算中心（合肥）,44,2022/12/14,大规模并行机MPP,成百上千个处理器组成的大规模计算机系统，规模是变化的。NORMA结构，高带宽低延迟定制互连。可扩放性：Mem, I/O,平衡设计系统成本：商用处理器，相对稳定的结构，SMP,分布通用性和可用性：不同的应用，PVM,MPI,交互，批处理，互连对用户透明，单一系统映象，故障通信要求存储器和I/O能力例子：Intel Option Red IBM SP2 Dawning 1000,国家高性能计算中心（合肥）,45,2022/12/14,典型MPP系统特性比较,国家高性能计算中心（合肥）,46,2022/12/14,MPP所用的高性能CPU特性比较,国家高性能计算中心（合肥）,47,2022/12/14,机群型大规模并行机SP2,设计策略：机群体系结构 标准环境 标准编程模型 系统可用性 精选的单一系统映像 系统结构：高性能开关 HPS 多级网络 宽节点、窄节点和窄节点2,国家高性能计算中心（合肥）,48,2022/12/14,工作站机群COW,分布式存储，MIMD，工作站+商用互连网络，每个节点是一个完整的计算机，有自己的磁盘和操作系统，而MPP中只有微内核优点：投资风险小系统结构灵活性能/价格比高能充分利用分散的计算资源可扩放性好问题通信性能并行编程环境例子：Berkeley NOW，Alpha Farm, FXCOW,国家高性能计算中心（合肥）,49,2022/12/14,典型的机群系统,国家高性能计算中心（合肥）,50,2022/12/14,SMPMPP机群比较,国家高性能计算中心（合肥）,51,2022/12/14,第三章 并行计算性能评测,3.1 并行机的一些基本性能指标3.2 加速比性能定律3.2.1 Amdahl定律3.2.2 Gustafson定律3.2.3 Sun和Ni定律3.3 可扩放性评测标准3.3.1 并行计算的可扩放性3.3.2 等效率度量标准3.3.3 等速度度量标准3.3.4 平均延迟度量标准,国家高性能计算中心（合肥）,52,2022/12/14,CPU的某些基本性能指标,工作负载执行时间 浮点运算数 指令数目 并行执行时间 T comput 为计算时间，T paro 为并行开销时间，T comm为相互通信时间 T n = T comput + T paro+ T comm 例：估计APRAM模型下执行时间,国家高性能计算中心（合肥）,53,2022/12/14,存储器性能,存储器的层次结构(C,L,B)估计存储器的带宽RISC add r1,r2,r3 r 8bytes 100MHzB = 3*8*100*106 B/s= 2.4GB/s,国家高性能计算中心（合肥）,54,2022/12/14,并行与通信开销,并行和通信开销：相对于计算很大。 PowerPC (每个周期 15ns 执行4flops; 创建一个进程1.4ms 可执行372000flops)开销的测量：乒-乓方法（Ping-Pong Scheme）节点0发送m个字节给节点1；节点1从节点0接收m个字节后，立即将消息发回节点0。总的时间除以2，即可得到点到点通信时间，也就是执行单一发送或接收操作的时间。可一般化为热土豆法（Hot-Potato），也称为救火队法（Fire-Brigade) 01 2 -n-1 0,国家高性能计算中心（合肥）,55,2022/12/14,Ping-Pong Scheme,if （my _node _id =0） then /*发送者*/start _time =second（ ） send an m-byte message to node 1 receive an m-byte message from node 1end_time = second（ ）total_time = end_time start_time communication_timei = total_time/2 else if （my_node_id = 1） then /*接收者*/ receive an m-byte message from node 0 send an m-byte message to node 0endif,国家高性能计算中心（合肥）,56,2022/12/14,并行开销的表达式：点到点通信,通信开销 t(m) = t0 + m/ r通信启动时间 t0渐近带宽r ：传送无限长的消息时的通信速率半峰值长度m1/2 ：达到一半渐近带宽所要的消息长度特定性能0：表示短消息带宽 t0 = m1/2 / r = 1 /0,国家高性能计算中心（合肥）,57,2022/12/14,并行开销的表达式：整体通信,典型的整体通信有： 播送（Broadcasting）：处理器0发送m个字节给所有的n个处理器收集（Gather）：处理0接收所有n个处理器发来在消息，所以处理器0最终接收了m n个字节；散射（Scatter）：处理器0发送了m个字节的不同消息给所有n个处理器，因此处理器0最终发送了m n个字节；全交换（Total Exchange）：每个处理器均彼此相互发送m个字节的不同消息给对方，所以总通信量为mn2个字节；循环移位（Circular-shift）：处理器i发送m个字节给处理器i+1，处理器n-1发送m个字节给处理器0，所以通信量为m n个字节。,国家高性能计算中心（合肥）,58,2022/12/14,机器的成本、价格与性/价比,机器的成本与价格机器的性能/价格比 Performance/Cost Ratio ：系指用单位代价（通常以百万美元表示）所获取的性能（通常以MIPS或MFLOPS表示） 利用率（Utilization）：可达到的速度与峰值速度之比,国家高性能计算中心（合肥）,59,2022/12/14,算法级性能评测,加速比性能定律并行系统的加速比是指对于一个给定的应用，并行算法（或并行程序）的执行速度相对于串行算法（或串行程序）的执行速度加快了多少倍。Amdahl 定律Gustafson定律Sun Ni定律可扩放性评测标准等效率度量标准等速度度量标准平均延迟度量标准,国家高性能计算中心（合肥）,60,2022/12/14,Amdahl 定律,P：处理器数；W：问题规模（计算负载、工作负载，给定问题的总计算量）；Ws：应用程序中的串行分量，f是串行分量比例（f = Ws/W， Ws=W1）；WP：应用程序中可并行化部分，1-f为并行分量比例；Ws +W p =W；Ts=T1 ：串行执行时间，T p ：并行执行时间；S：加速比，E：效率； 出发点：固定不变的计算负载； 固定的计算负载分布在多个处理器上的，增加处理器加快执行速度，从而达到了加速的目的。,国家高性能计算中心（合肥）,61,2022/12/14,Amdahl定律（contd),固定负载的加速公式： W s+ W p可相应地表示为f+（1-f）p时，上式极限为： S= 1 / f W o为额外开销,国家高性能计算中心（合肥）,62,2022/12/14,Amdahls law (contd),国家高性能计算中心（合肥）,63,2022/12/14,Gustafson定律,出发点：对于很多大型计算，精度要求很高，即在此类应用中精度是个关键因素，而计算时间是固定不变的。此时为了提高精度，必须加大计算量，相应地亦必须增多处理器数才能维持时间不变；除非学术研究，在实际应用中没有必要固定工作负载而计算程序运行在不同数目的处理器上，增多处理器必须相应地增大问题规模才有实际意义。 Gustafson加速定律 :并行开销W o ：,国家高性能计算中心（合肥）,64,2022/12/14,Gustafson定律（contd),国家高性能计算中心（合肥）,65,2022/12/14,Sun 和 Ni定律,基本思想：只要存储空间许可，应尽量增大问题规模以产生更好和更精确的解（此时可能使执行时间略有增加）。假定在单节点上使用了全部存储容量M并在相应于W的时间内求解之，此时工作负载W= fW + （1-f）W。 在p 个节点的并行系统上，能够求解较大规模的问题是因为存储容量可增加到pM。令因子G（p）反应存储容量增加到p倍时并行工作负载的增加量，所以扩大后的工作负载W = fW + （1-f）G（p）W。存储受限的加速公式 ： 并行开销W o:,国家高性能计算中心（合肥）,66,2022/12/14,Sun 和 Ni定律(contd),G（p）=1时就是Amdahl加速定律； G（p）=p 变为 f + p（1-f），就是Gustafson加速定律G（p）p时，相应于计算机负载比存储要求增加得快，此时 Sun和 N i 加速均比 Amdahl 加速和 Gustafson 加速为高。,国家高性能计算中心（合肥）,67,2022/12/14,加速比讨论,参考的加速经验公式： p/log pSP 线性加速比：很少通信开销的矩阵相加、内积运算等p/log p的加速 比：分治类的应用问题 通信密集类的应用问题 ：S = 1 / C （ p ） 超线性加速 绝对加速：最佳并行算法与串行算法相对加速：同一算法在单机和并行机的运行时间,国家高性能计算中心（合肥）,68,2022/12/14,可扩放性评测标准,并行计算的可扩放性（Scalability）也是主要性能指标可扩放性最简朴的含意是在确定的应用背景下，计算机系统（或算法或程序等）性能随处理器数的增加而按比例提高的能力 影响加速比的因素：处理器数与问题规模求解问题中的串行分量并行处理所引起的额外开销（通信、等待、竞争、冗余操作和同步等）加大的处理器数超过了算法中的并发程度增加问题的规模有利于提高加速的因素：较大的问题规模可提供较高的并发度；额外开销的增加可能慢于有效计算的增加；算法中的串行分量比例不是固定不变的（串行部分所占的比例随着问题规模的增大而缩小）。增加处理器数会增大额外开销和降低处理器利用率，所以对于一个特定的并行系统（算法或程序），它们能否有效利用不断增加的处理器的能力应是受限的，而度量这种能力就是可扩放性这一指标。,国家高性能计算中心（合肥）,69,2022/12/14,可扩放性评测标准（contd),可扩放性:调整什么和按什么比例调整并行计算要调整的是处理数p和问题规模W，两者可按不同比例进行调整，此比例关系（可能是线性的，多项式的或指数的等）就反映了可扩放的程度。 并行算法和体系结构可扩放性研究的主要目的：确定解决某类问题用何种并行算法与何种并行体系结构的组合，可以有效地利用大量的处理器；对于运行于某种体系结构的并行机上的某种算法当移植到大规模处理机上后运行的性能；对固定的问题规模，确定在某类并行机上最优的处理器数与可获得的最大的加速比；用于指导改进并行算法和并行机体系结构，以使并行算法尽可能地充分利用可扩充的大量处理器 目前无一个公认的、标准的和被普遍接受的严格定义和评判它的标准,国家高性能计算中心（合肥）,70,2022/12/14,等效率度量标准,令tie 和t io 分别是并行系统上第i个处理器的有用计算时间和额外开销时间（包括通信、同步和空闲等待时间等）T p 是p个处理器系统上并行算法的运行时间，对于任意i显然有T p = tie +t io ，且 T e+ T o= pT p 问题的规模W为最佳串行算法所完成的计算量W=Te 如果问题规模W 保持不变，处理器数p增加，开销To增大，效率E下降。为了维持一定的效率（介于0与1之间），当处理数p增大时，需要相应地增大问题规模W的值。由此定义函数f E（p）为问题规模W随处理器数p变化的函数，为等效率函数（ISO-efficiency Function）（Kumar1987）,国家高性能计算中心（合肥）,71,2022/12/14,等效率度量标准（contd),曲线1表示算法具有很好的扩放性；曲线2表示算法是可扩放的；曲线 3表示算法是不可扩放的。 优点：简单可定量计算的、少量的参数计算等效率函数 缺点：如果To无法计算出（在共享存储并行机中）,国家高性能计算中心（合肥）,72,2022/12/14,等速度度量标准, 表示处理器个数，W表示要求解问题的工作量或称问题规模（在此可指浮点操作个数），T为并行执行时间，定义并行计算的速度V为工作量W除以并行时间T p个处理器的并行系统的平均速度定义为并行速度V除以处理器个数 p：W是使用p个处理器时算法的工作量，令W表示当处理数从p增大到p时，为了保持整个系统的平均速度不变所需执行的工作量，则可得到处理器数从 p到p时平均速度可扩放度量标准公式,国家高性能计算中心（合肥）,73,2022/12/14,等速度度量标准（contd）,优点：直观地使用易测量的机器性能速度指标来度量缺点：某些非浮点运算可能造成性能的变化,国家高性能计算中心（合肥）,74,2022/12/14,平均延迟度量标准,Ti为Pi的执行时间，包括包括延迟Li，Pi的总延迟时间为“L i+启动时间+停止时间”。定义系统平均延迟时间为pTpara =To+ Ts 在p个处理器上求解工作量为W问题的平均延迟 在p个处理器上求解工作量为W问题的平均延迟当处理器数由p变到p，而推持并行执行效率不变，则定义平均延迟可扩放性度量标准为,国家高性能计算中心（合肥）,75,2022/12/14,平均延迟度量标准（Contd),优点：平均延迟能在更低层次上衡量机器的性能缺点：需要特定的软硬件才能获得平均延迟,并 行 计 算,中国科学技术大学计算机科学与技术系国家高性能计算中心(合肥)2003年9月,第二篇 并行算法的设计 第四章 并行算法的设计基础 第五章 并行算法的一般设计方法 第六章 并行算法的基本设计技术 第七章 并行算法的一般设计过程,第四章 并行算法的设计基础 4.1 并行算法的基础知识 4.2 并行计算模型,4.1 并行算法的基础知识 4.1.1 并行算法的定义和分类 4.1.2 并行算法的表达 4.1.3 并行算法的复杂性度量 4.1.4 并行算法中的同步和通讯,国家高性能计算中心（合肥）,80,2022/12/14,并行算法的定义和分类,并行算法的定义算法并行算法：一些可同时执行的诸进程的集合，这些进程互相作用和协调动作从而达到给定问题的求解。并行算法的分类数值计算和非数值计算同步算法和异步算法分布算法确定算法和随机算法,4.1 并行算法的基础知识 4.1.1 并行算法的定义和分类 4.1.2 并行算法的表达 4.1.3 并行算法的复杂性度量 4.1.4 并行算法中的同步和通讯,国家高性能计算中心（合肥）,82,2022/12/14,并行算法的表达,描述语言可以使用类Algol、类Pascal等；在描述语言中引入并行语句。并行语句示例Par-do语句 for i=1 to n par-do end forfor all语句 for all Pi, where 0ik end for,4.1 并行算法的基础知识 4.1.1 并行算法的定义和分类 4.1.2 并行算法的表达 4.1.3 并行算法的复杂性度量 4.1.4 并行算法中的同步和通讯,国家高性能计算中心（合肥）,84,2022/12/14,并行算法的复杂性度量,串行算法的复杂性度量最坏情况下的复杂度(Worst-CASE Complexity)期望复杂度(Expected Complexity)并行算法的几个复杂性度量指标运行时间t(n):包含计算时间和通讯时间，分别用计算时间步和选路时间步作单位。n为问题实例的输入规模。处理器数p(n)并行算法成本c(n): c(n)=t(n)p(n)总运算量W(n): 并行算法求解问题时所完成的总的操作步数。,国家高性能计算中心（合肥）,85,2022/12/14,并行算法的复杂性度量,Brent定理令W(n)是某并行算法A在运行时间T(n)内所执行的运算量，则A使用p台处理器可在t(n)=O(W(n)/p+T(n)时间内执行完毕。W(n)和c(n)密切相关P=O(W(n)/T(n)时，W(n)和c(n)两者是渐进一致的对于任意的p，c(n)W(n),4.1 并行算法的基础知识 4.1.1 并行算法的定义和分类 4.1.2 并行算法的表达 4.1.3 并行算法的复杂性度量 4.1.4 并行算法中的同步和通讯,国家高性能计算中心（合肥）,87,2022/12/14,并行算法的同步,同步概念同步是在时间上强使各执行进程在某一点必须互相等待；可用软件、硬件和固件的办法来实现。同步语句示例算法4.1 共享存储多处理器上求和算法 输入：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 end for,国家高性能计算中心（合肥）,88,2022/12/14,并行算法的通讯,通讯共享存储多处理器使用：global read(X,Y)和global write(X,Y)分布存储多计算机使用：send(X,i)和receive(Y,j)通讯语句示例算法4.2 分布存储多计算机上矩阵向量乘算法 输入：处理器数p, A划分为B=A1.n,(i-1)r+1.ir, x划分为w=w(i-1)r+1;ir 输出：P1保存乘积AX Begin (1) Compute z=Bw (2) if i=1 then yi=0 else receive(y,left) endif (3) y=y+z (4) send(y,right) (5) if i=1 then receive(y,left) End,第四章 并行算法的设计基础 4.1 并行算法的基础知识 4.2 并行计算模型,4.2 并行计算模型 4.2.1 PRAM模型 4.2.2 异步APRAM模型 4.2.3 BSP模型 4.2.4 logP模型,国家高性能计算中心（合肥）,91,2022/12/14,PRAM模型,基本概念由Fortune和Wyllie1978年提出，又称SIMD-SM模型。有一个集中的共享存储器和一个指令控制器，通过SM的R/W交换数据，隐式同步计算。结构图,国家高性能计算中心（合肥）,92,2022/12/14,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,国家高性能计算中心（合肥）,93,2022/12/14,PRAM模型,优点适合并行算法表示和复杂性分析，易于使用，隐藏了并行机的通讯、同步等细节。缺点不适合MIMD并行机，忽略了SM的竞争、通讯延迟等因素,4.2