并行计算(中科大讲义)
并行计算――结构?算法?编程并行计算――结构?算法?编程? 第一篇 并行计算的基础? 第一章 并行计算机系统及其结构模型 ? 第二章 当代并行机系统：SMP、MPP和Cluster ? 第三章 并行计算性能评测? 第二篇 并行算法的设计? ? ? ? 第四章 并行算法的设计基础 第五章 并行算法的一般设计方法 第六章 并行算法的基本设计技术 第七章 并行算法的一般设计过程国家高性能计算中心（合肥）2并行计算――结构?算法?编程? 第三篇 并行数值算法? ? ? ? 第八章 基本通信操作 第九章 稠密矩阵运算 第十章 线性方程组的求解 第十一章 快速傅里叶变换? 第四篇 并行程序设计? ? ? ? 第十二章 并行程序设计基础 第十三章 并行程序设计模型和共享存储系统编程 第十四章 分布存储系统并行编程 第十五章 并行程序设计环境与工具 3国家高性能计算中心（合肥）第一章并行计算机系统及结构模型? 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 并行计算机访存模型国家高性能计算中心（合肥）
4并行计算? 并行计算：并行机上所作的计算，又称高性能 计算或超级计算。 ? 计算科学：计算物理、计算化学、计算生物等 ? 科学与工程问题的需求：气象预报、油藏模拟、 核武器数值模拟、航天器设计、基因测序等。 ? 需求类型：计算密集、数据密集、网络密集。 ? 美国HPCC计划：重大挑战性课题，3T性能 ? 美国Petaflops研究项目：Pflop/s。 ? 美国ASCI计划：核武器数值模拟。国家高性能计算中心（合肥）5? Intel（Option Red)： 1Tflops,1997,Pentium Pro ? SGI(Option Blue Mountain): 3Tflops,1998,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高性能计算机国家高性能计算中心（合肥）6? 不同带宽与距离的互连技术: 总线、SAN、LAN、MAN、WAN100 Gb/s MIN 或 交叉开关 10 Gb/s 局部总线 SCI HiPPI Myrinet 千兆位 以太网 I/O 总线 光纤 通道 快速以太网 100 Base T 10 Mb/s 总线或开关 FDDI系统互连网络带宽1 Gb/s100 Mb/sATMIsoEnet SAN以太网 10 Base T LAN MAN WAN国家高性能计算中心（合肥）7局部总线、I/O总线、SAN和LANP 节点 1 处理器总线 局部总线,存储器总线 I/O 桥 SCSI 磁盘 SAN(e.g.Myrinet) 系统 I M 节点 2 节点 NI/O总线,系统总线 LAN(e.g.以太网,FDDI) 接口 系统 II国家高性能计算中心（合肥）8网络性能指标? 节点度（Node Degree）：射入或射出一个节点的边 数。在单向网络中，入射和出射边之和称为节点度。 ? 网络直径（Network Diameter）： 网络中任何两个 节点之间的最长距离，即最大路径数。 ? 对剖宽度（Bisection Width） ：对分网络各半所必须 移去的最少边数 ? 对剖带宽（ Bisection Bandwidth）:每秒钟内，在最小的对剖平面上通过所有连线的最大信息位（或字节）数? 如果从任一节点观看网络都一样，则称网络为对称的 （Symmetry）国家高性能计算中心（合肥）9静态互连网络 与动态互连网络? 静态互连网络：处理单元间有着固定连接的一类网络， 在程序执行期间，这种点到点的链接保持不变；典型的 静态网络有一维线性阵列、二维网孔、树连接、超立方 网络、立方环、洗牌交换网、蝶形网络等 ? 动态网络：用交换开关构成的，可按应用程序的要求动 态地改变连接组态；典型的动态网络包括总线、交叉开 关和多级互连网络等。国家高性能计算中心（合肥）10静态互连网络（1）? 一维线性阵列（1-D Linear Array）：? 并行机中最简单、最基本的互连方式， ? 每个节点只与其左、右近邻相连，也叫二近邻连接， ?N / 2? ? N个节点用N-1条边串接之，内节点度为2，直径为N-1，对剖 宽度为1 ? 当首、尾节点相连时可构成循环移位器，在拓扑结构上等同于 环，环可以是单向的或双向的，其节点度恒为2，直径或为 （双向环）或为N-1（单向环），对剖宽度为2国家高性能计算中心（合肥）11?N? N二维网孔（2-D Mesh）：静态互连网络（2）? 每个节点只与其上、下、左、右的近邻相连（边界节点除外）， 节点度为4，网络直径为 2( N ?1) ，对剖宽度为 N ? 在垂直方向上带环绕，水平方向呈蛇状，就变成Illiac网孔了， 节点度恒为4，网络直径为 N ?1 ，而对剖宽度为 2 N ? 垂直和水平方向均带环绕，则变成了2-D环绕（2-D Torus）， 节点度恒为4，网络直径为 2? N / 2? ，对剖宽度为 2 N(a)2-D网孔国家高性能计算中心（合肥）(b)Illiac网孔(c)2-D环绕12? 二叉树：静态互连网络（3）? 除了根、叶节点，每个内节点只与其父节点和两个子节点相连。 ? 节点度为3，对剖宽度为1，而树的直径为 2??log N ? ? 1? ? 如果尽量增大节点度为，则直径缩小为2，此时就变成了星形 网络，其对剖宽度为 ?N / 2? ? 传统二叉树的主要问题是根易成为通信瓶颈。胖树节点间的通 路自叶向根逐渐变宽。(a)二叉树(b)星形连接(c)二叉胖树国家高性能计算中心（合肥）13? 超立方 ：静态互连网络（4）n? 一个n-立方由 N ? 2 个顶点组成，3-立方如图(a)所示；4-立 方如图(b)所示，由两个3-立方的对应顶点连接而成。 ? n-立方的节点度为n，网络直径也是n ，而对剖宽度为N / 2 。 ? 如果将3-立方的每个顶点代之以一个环就构成了如图(d)所示 的3-立方环，此时每个顶点的度为3，而不像超立方那样节点 度为n。(a)3-立方(b)4-立方(c)顶点代之以环(d)3-立方环国家高性能计算中心（合肥）14嵌入? 将网络中的各节点映射到另一个网络中去 ? 用膨胀（Dilation）系数来描述嵌入的质量，它是指被 嵌入网络中的一条链路在所要嵌入的网络中对应所需的 最大链路数 ? 如果该系数为1，则称为完美嵌入。? 环网可完美嵌入到2-D环绕网中 ? 超立方网可完美嵌入到2－D环绕网中国家高性能计算中心（合肥）15嵌入11 1010110011011111111001000101011101100000000100110010011111011011国家高性能计算中心（合肥）16静态互连网络特性比较网络名称 线性阵列N网络规模节点度 2网络直径N ?1对剖宽度 1对称 非 是链路数N ?1环形N2（双 ?N / 2?向）2( N ?1)N ?12N2-D网孔 Illiac网孔 2-D环绕 二叉树? ? ?N? N N? N? ? ?4 4 4 3非N2 N2( N ? N )2N非 是 非 非 是 是N? NN2 N /2??2 N2N2??log N ? ? 1?1N ?1星形N N ?12?N / 2?N ?1 nN / 2超立方 立方环N ?2nn3n2k ? 1 ? ?k / 2?N /2国家高性能计算中心（合肥）N ? k ? 2kN /(2k )3N / 217? 总线：PCI、VME、Multics、Sbus、MicroChannel? 多处理机总线系统的主要问题包括总线仲裁、中断处理、协议转换、 快速同步、高速缓存一致性协议、分事务、总线桥和层次总线扩展等CPU板动态互连网络 (1)本地外围设备 (SCSI总线)存储器板 存储器单元 存储器总线 IF MCLMCPU 本地总线IOC高速缓存IF系统总线 I/O板 IOP 数据总线 缓冲 IF IF(底板上) 通信板 IF 数据总线 缓冲 IF CC国家高性能计算中心（合肥）磁盘和磁带 部件打印机 或绘图仪网络 (以太网等)18? 交叉开关（Crossbar）：动态互连网络 （2）? 单级交换网络，可为每个端口提供更高的带宽。象电话交换机 一样，交叉点开关可由程序控制动态设置其处于“开”或“关” 状态，而能提供所有（源、目的）对之间的动态连接。 ? 交叉开关一般有两种使用方式：一种是用于对称的多处理机或 多计算机机群中的处理器间的通信；另一种是用于SMP服务器 或向量超级计算机中处理器和存储器之间的存取。国家高性能计算中心（合肥）19? 单级交叉开关级联起来形成多级互连网络MIN （Multistage Interconnection Network）0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1动态互联网络 （3）(a)4种可能的开关连接输入 000 001 010 011 100 101 110 111 第0级 第1级 第2级 输出 000 001 010 011 100 101 110 111(b)一种8输入的Omega网络国家高性能计算中心（合肥）20动态互连网络（4）? 交换开关模块：? 一个交换开关模块有n个输入和n个输出，每个输入可连接到任 意输出端口，但只允许一对一或一对多的映射，不允许多对一 的映射，因为这将发生输出冲突 ? 均匀洗牌、蝶网、多路均匀洗牌、交叉开关、立方连接 2? 2 log n ? n输入的Ω网络需要 级 开关，在Ilinois大学的 Cedar[2]多处理机系统中采用了Ω网络 ? Cray Y/MP多级网络，该网络用来支持8个向量处理器和256 个存储器模块之间的数据传输。网络能够避免8个处理器同时 进行存储器存取时的冲突。2? 级间互连（Interstage Connection ）：国家高性能计算中心（合肥）21动态互连网络比较动态互连网络的复杂度和带宽性能一览表 网络特性 硬件复杂度 每个处理器带宽 总线系统 多级互连网络 交叉开关O(n ? w)O(wf / n)O((n logk n)w)O(n 2 w)O( wf )～O( wf ) O( wf )报道的聚集带宽SunFire服务器 IBM SP2中的 Digital的千兆开 中的Gigaplane 512节点的HPS： 关：3.4GB/s 总线：2.67GB/s 10.24GB/s? n,节点规模w，数据宽度 22国家高性能计算中心（合肥）? Myrinet:标准互联网络（1）? Myrinet是由Myricom公司设计的千兆位包交换网络，其目的 是为了构筑计算机机群，使系统互连成为一种商业产品。 ? Myrinet是基于加州理工学院开发的多计算机和VLSI技术以及 在南加州大学开发的ATOMIC/LAN技术。Myrinet能假设任 意拓扑结构，不必限定为开关网孔或任何规则的结构。 ? Myrinet在数据链路层具有可变长的包格式，对每条链路施行 流控制和错误控制，并使用切通选路法以及定制的可编程的主 机接口。在物理层上，Myrinet网使用全双工SAN链路，最长 可达3米，峰值速率为（1.28＋1.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 23国家高性能计算中心（合肥）Myrinet连接的LAN/Cluster机箱内多计算机机群 桌面主机交换开关 交换开关 交换开关 VME 单板交换开关网络RAM和磁盘多处理机机群国家高性能计算中心（合肥）24? 高性能并行接口（HiPPI）标准互连网络（2)? 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等系统国家高性能计算中心（合肥）25使用HiPPI通道和开关构筑的 LAN主干网超级计算机 300米 HiPPI 串行 直至10千米 帧缓冲器 25米 HiPPI 25米 文件 光纤扩展器 交换开关 服务器 HiPPI 300米 串行 工作站RGB显示器存储器 25米 HiPPI 光纤扩展器 服务器 交换开关 HiPPI 串行 300米 小型机 大规模并行 处理系统国家高性能计算中心（合肥）工作站26? 光纤通道FC（Fiber Channel） :标准互连网络（3）? 通道和网络标准的集成 ? 光纤通道既可以是共享介质，也可以是一种交换技术 ? 光纤通道操作速度范围可从100到133、200、400和 800Mbps。FCSI厂商也正在推出未来具有更高速度（1、2或 4Gbps）的光纤通道 ? 光纤通道的价值已被现在的某些千兆位局域网所证实，这些局 域网就是基于光纤通道技术的 ? 连网拓扑结构的灵活性是光纤通道的主要财富，它支持点到点、 仲裁环及交换光纤连接? FDDI :? 光纤分布式数据接口FDDI（Fiber Distributed Data Interface） ? FDDI采用双向光纤令牌环可提供100-200Mbps数据传输速率 ? FDDI具有互连大量设备的能力 ? 传统的FDDI仅以异步方式操作 27国家高性能计算中心（合肥）双向FDDI环作为主干网文件服务器?以太网集线器 路由器桌面计算机FDDI集中器 双向 FDDI环 FDDI 集中器FDDI 集中器计算机服务器 数据库服务器国家高性能计算中心（合肥）28标准互联网络（4）? ATM（Asynchronous Transfer Mode）:? 由成立于1991年的ATM论坛和ITU标准定义。 ? ATM是一种独立于介质的消息传输协议，它将消息段变成更 短的固定长度为53字节的报元进行传输。 ? 这种技术是基于报元交换机制。ATM的目的是将实时和突发 数据的传输合并成单一的网络技术。 ? ATM网络支持从25到51、155和622Mbps不同的速率，其速 率越低ATM交换器和使用的链路价格越低。国家高性能计算中心（合肥）29香港大学开发的Pearl机群IBM SP2 ( 32 节点 ） FDDI 城市大学的WS池 T1 HARNET 浸会大学 的WS池 T1 T3 去USA 主干因特网 USC的 IMSCPC 和 WSLAX-20 以太网 ASX-200BXT1SGI Power Challenge XL服务器 (8CPU) 155Mb/s Sun E-6000 服务器 (8 CPU) Power 集线器7000155Mb/s HP 服务器 Sun E-4000ASX-1000 ATM开关 155Mb/sPC工作站池 Sun UltraSPARC 2/1200 国家高性能计算中心（合肥） Sun SPARC 20/HS14以太网30标准互连网络（5）代别 类型 引入年代 速度（带宽） 以太网 10BaseT 1982 10Mb/s 快速以太网 100BaseT Mb/s 千兆位以太网 1GB 1997 1Gb/s最 UTR（非屏蔽双扭对） 大 距 STP（屏蔽双扭对） 同轴电缆 离 多模光纤单模光纤100m 500m 2Km25Km100m 100m 412m（半双工） 2Km（全双工）20Km25－100m 25－100m 500m3Km主要应用领域文件共享， 打印机共享COW计算， C/S结构， 大型数据库存取等大型图像文件， 多媒体， 因特网， 内部网， 数据仓库等31国家高性能计算中心（合肥）并行计算机结构模型MB VP VP MB P/C P/C LM NIC I/O 定制网络?SMVPP/CP/C?SM?P/C LM NIC交叉开关 SM SM SM总线或交叉开关(a)PVP(b)SMP(c)MPPMB MB MB P/C M Bridge LD IOB NIC 定制网络 MB P/C M Bridge LD IOB NICP/C LM DIR NICP/C LM DIR NIC??(d)DSM国家高性能计算中心（合肥） 商品网络(以太网，ATM，etc.)(e)COW32并行计算机体系合一结构? SMP、MPP、DSM和COW并行结构渐趋一致。? 大量的节点通过高速网络互连起来 ? 节点遵循Shell结构：用专门定制的Shell电路将商用微处理器 和节点的其它部分（包括板级Cache、局存、NIC和DISK） 连接起来。优点是CPU升级只需要更换Shell。C M D 节点 1 Shell P NIC 互连网络 C C Shell P NIC 互连网络 共享磁盘 C Shell P 互连网络 共享存储器 共享磁盘?节点 NM 节点 1?节点 N NICShell PNIC(a)无共享(c)共享存储(b)共享磁盘国家高性能计算中心（合肥）
33五种结构特性一览表属性 结构类型 PVP MIMD SMP MIMD MPP MIMD DSM MIMD COW MIMD 处理器类型 专用定制 商用 商用 商用 商用互连网络定制交叉开关总线、交叉开关定制网络定制网络商用网络（以太 ATM）通信机制共享变量共享变量消息传递共享变量消息传递地址空间单地址空间单地址空间多地址空间单地址空间多地址空间系统存储器集中共享集中共享分布非共享分布共享分布非共享访存模型UMAUMANORMANUMANORMA代表机器Cray C-90， Cray T-90， 银河1号IBM R50， SGI Power Challenge， 曙光1号Intel Paragon， IBMSP2，曙光 Stanford DASH， Cray T 3DBerkeley NOW， Alpha Farm国家高性能计算中心（合肥）34并行计算机访存模型（1)? UMA（Uniform Memory Access）模型是均匀存储访问 模型的简称。其特点是：? ? ? ? 物理存储器被所有处理器均匀共享； 所有处理器访问任何存储字取相同的时间； 每台处理器可带私有高速缓存； 外围设备也可以一定形式共享。处理器 P1 P2?Pn系统互连 （ 总线 , 交叉开关 , 多级 网络 ）I/OSM1 共享存储器?SMm国家高性能计算中心（合肥）35? NUMA(Nonuniform Memory Access)模型是非均匀存储 访问模型的简称。特点是：? 被共享的存储器在物理上是分布在所有的处理器中的，其所有 本地存储器的集合就组成了全局地址空间； ? 处理器访问存储器的时间是不一样的；访问本地存储器 LM或 群内共享存储器CSM较快，而访问外地的存储器或全局共享存 储器GSM较慢(此即非均匀存储访问名称的由来)； ? 每台处理器照例可带私有高速缓存，外设也可以某种形式共享。GSM GSM并行计算机访存模型（2)…GSM全局互连网络P LM1 P1 互 LM2 P2 连 网 络 Pn P C I NCSM CSMP P C I NCSM CSM………………LMn…PCSMPCSM群1群N(b)层次式机群模型国家高性能计算中心（合肥） (a)共享本地存储模型36? COMA(Cache-Only Memory Access)模型是全高速缓存 存储访问的简称。其特点是：? 各处理器节点中没有存储层次结构，全部高速缓存组成了全局 地址空间； ? 利用分布的高速缓存目录D进行远程高速缓存的访问; ? COMA中的高速缓存容量一般都大于2 级高速缓存容量； ? 使用COMA时，数据开始时可任意分配，因为在运行时它最终 会被迁移到要用到它们的地方。互连网络并行计算机访存模型（3)D C PD C PD?C P国家高性能计算中心（合肥）37并行计算机访存模型（4)? CC-NUMA（Coherent-Cache Nonuniform Memory Access）模型是高速缓存一致性非均匀存储访问模型的 简称。其特点是：? ? ? ? 大多数使用基于目录的高速缓存一致性协议； 保留SMP结构易于编程的优点，也改善常规SMP的可扩放性； CC-NUMA实际上是一个分布共享存储的DSM多处理机系统； 它最显著的优点是程序员无需明确地在节点上分配数据，系统 的硬件和软件开始时自动在各节点分配数据，在运行期间，高 速缓存一致性硬件会自动地将数据迁移至要用到它的地方。节点 1 P/C 节点 N Mem P/C?P/C交叉 开关 总线或 I/O NIC,DIR,RC?I/O?P/CMem开关 总线或 交叉 NIC,DIR,RC系统互连网路国家高性能计算中心（合肥）38? NORMA（No-Remote Memory Access）模型是非远程 存储访问模型的简称。NORMA的特点是：? 所有存储器是私有的； ? 绝大数NUMA都不支持远程存储器的访问； ? 在DSM中，NORMA就消失了。M P M P并行计算机访存模型（5)...M PMP 消息传递互连网络 (网络，环网，超立方， 立方环等)PMM国家高性能计算中心（合肥）...P...P MP MP M...P M39构筑并行机系统的不同存储结构PVP (Cray中央存储器 T90)UMA SMP SGI多处理机 （ 单地址 空间 共享 存储器 ） (Intel SHV,SunFire,DEC 8400, PowerChallenge,IBMR60,etc.) (KSR-1,DDM) (Stanford Dash, SGI Origin 2000,Sequent NUMA-Q, HP/Convex Exemplar) (Cray T3E)COMACC-NUMA NUMA分布存储器NCC-NUMAMIMD Cluster(IBM SP2,DEC TruCluster Tandem Hymalaya,HP, Microsoft Wolfpack,etc) （ 松散耦合）DSM(TreadMarks, Wind Tunnel, IVY,Shrimp, etc.)NORMA多计算机 (多地址空间非共享存储器)MPP (Intel国家高性能计算中心（合肥）TFLOPS) （ 紧耦合）40第二章 当代并行机系统? 2.1 共享存储多处理机系统? 2.1.1 对称多处理机SMP结构特性? 2.2 分布存储多计算机系统? 2.2.1 大规模并行机MPP结构特性? 2.3 机群系统? 2.3.1 大规模并行处理系统MPP机群SP2 ? 2.3.2 工作站机群COW国家高性能计算中心（合肥）41对称多处理机SMP(1)? SMP: 采用商用微处理器，通常有片上和片外Cache，基于总线连 接，集中式共享存储，UMA结构? 例子：SGI Power Challenge, DEC Alpha Server,Dawning 1P/C P/C?SMP/C总线或交叉开关 SM国家高性能计算中心（合肥）I/O42对称多处理机SMP(2)? 优点? ? ? ? ? ? ? ? 对称性 单地址空间，易编程性，动态负载平衡，无需显示数据分配 高速缓存及其一致性，数据局部性，硬件维持一致性 低通信延迟，Load/Store完成 欠可靠，BUS,OS,SM 通信延迟（相对于CPU），竞争加剧 慢速增加的带宽（MB double/3年,IOB更慢） 不可扩放性---〉CC-NUMA? 问题国家高性能计算中心（合肥）43大规模并行机MPP? ? ? ? ? 成百上千个处理器组成的大规模计算机系统，规模是变化的。 NORMA结构，高带宽低延迟定制互连。 可扩放性：Mem, I/O,平衡设计 系统成本：商用处理器，相对稳定的结构，SMP,分布 通用性和可用性：不同的应用，PVM,MPI,交互，批处理，互连对 用户透明，单一系统映象，故障 ? 通信要求 MB MB ? 存储器和I/O能力 P/C P/C ? 例子：Intel Option Red LM ? LMIBM SP2 Dawning 1000NIC NIC定制网络国家高性能计算中心（合肥）44典型MPP系统特性比较MPP模型 Intel/Sandia ASCI Option Red 9072个处理器， 1.8Tflop/s(NSL) 1996年12月 200MHz, 200Mflop/s Pentium Pro 2个处理器，32到 256MB主存，共 享磁盘 分离两维网孔， NORMA 轻量级内核 （LWK） 基于PUMA Portals的MPI Nx，PVM，HPF IBM SP2 SGI/Cray Origin个处理器， 51Gflop/s(NCSA) 1996年10月 200MHz， 400Mflop/s MIPS R10000 2个处理器，64MB 到256MB分布共享 主存和共享磁盘 胖超立方体网络， CC-NUMA 微内核Cellular IRIX Power C， Power Fortran MPI，PVM 一个大型样机的配置 400个处理器， 100Gflop/s(MHPC C) 1994年9月 67MHz， 267Mflop/s POWER2 1个处理器，64MB 到2GB本地主存， 1GB到14.5GB本地 磁盘 多级网络， NORMA 完全AIX（IBM UNIX） MPI和PVM HPF，Linda问世日期 处理器类型节点体系结构 和数据存储器 互连网络和主存模型 节点操作系统 自然编程机制 其他编程模型国家高性能计算中心（合肥）45MPP所用的高性能CPU特性比较属性 工艺 晶体管数 时钟频率 电压 功率 字长 I/O 高速缓存 2级 高速缓存 执行单元 超标量 流水线深 度 SPECint 92 SPECfp 92 SPECint 95 SPECfp 95 其它特性 Pentium Pro BiCMOS 5.5M/15.5M 150MHz 2.9V 20W 32位 8KB/8KB 256KB (多芯片模块 5个单元 ) 3路(Way) 14级 366 283 8.09 6.70 CISC/RISC 混合 PowerPC 602 CMOS 7M 133MHz 3.3V 30W 64位 32KB/32KB 1~128MB (片外) 6个单元 4路 4~8级 225 300 225 300 短流水线长 L1高速缓存 Alpha 21164A CMOS 9.6M 417MHz 2.2V 20W 64位 8KB/8KB 96KB (片上) 4个单元 4路 7~9级 &500 &750 &11 &17 最高时钟频 率最大片上 2级高速缓 存 Ultra SPARC II CMOS 5.4M 200MHz 2.5V 28W 64位 16KB/16KB 16MB (片外) 9个单元 4路 9级 350 550 N/A N/A 多媒体和图 形指令 MIPS R10000 CMOS 6.8M 200MHz 3.3V 30W 64位 32KB/32K B 16MB (片外) 5个单元 4路 5~7级 300 600 7.4 15 MP机群总 线可支持4 个CPU国家高性能计算中心（合肥）46机群型大规模并行机SP2? 设计策略：? ? ? ? ? 机群体系结构 标准环境 标准编程模型 系统可用性 精选的单一系统映像P D MCC P I/O 总线 NIC 节点1 E 以太网 P D MCC P I/O 总线 NIC S 节点N E?? 系统结构：? 高性能开关 HPS 多级Ω网络 ? 宽节点、窄节点和窄节点2高性能开关 ，Omega 网络国家高性能计算中心（合肥）47工作站机群COW? ? 分布式存储，MIMD，工作站+商用互连网络，每个节点是一个完整的计 算机，有自己的磁盘和操作系统，而MPP中只有微内核 优点：? ? ? ? ? 投资风险小 系统结构灵活 性能/价格比高 能充分利用分散的计算资源 可扩放性好D NIC P/C P/CMMMIO LAN DMIO?问题? 通信性能 ? 并行编程环境NIC?例子：Berkeley NOW，Alpha Farm, FXCOW国家高性能计算中心（合肥）48典型的机群系统典型的机群系统特点一览表名称 Princeton:SHRIMP Karsruhe:Parastation Rice:TreadMarks 系统特点 PC商用组件，通过专用网络接口达到共享虚拟存储，支持 有效通信 用于分布并行处理的有效通信网络和软件开发 软件实现分布共享存储的工作站机群Wisconsin:Wind TunnelChica、Maryl、 Penns:NSCP Argonne:Globus Syracuse:WWVM HKU:Pearl Cluster Virgina:Legion国家高性能计算中心（合肥）在经由商用网络互连的工作站机群上实现分布共享存储国家可扩放机群计划：在通过因特网互连的3个本地机群系 统上进行元计算 在由ATM连接的北美17个站点的WAN上开发元计算平台和 软件 使用因特网和HPCC技术，在世界范围的虚拟机上进行高性 能计算 研究机群在分布式多媒体和金融数字库方面的应用 在国家虚拟计算机设施上开发元计算软件 49SMP\MPP\机群比较系统特征 节点数量(N) 节点复杂度 节点间通信 节点操作系统 支持单一系统映像 地址空间 作业调度 网络协议 可用性 性能/价格比 互连网络 SMP ?O(10) 中粒度或细粒度 共享存储器 1 永远 单一 单一运行队列 非标准 通常较低 一般 总线/交叉开关
MPP O(100)-O(1000) 细粒度或中粒度 消息传递 或共享变量（有DSM时） N(微内核) 和1个主机OS(单一) 部分 多或单一（有DSM时） 主机上单一运行队列 非标准 低到中 一般 定制 机群 ?O(100) 中粒度或粗粒度 消息传递 N (希望为同构) 希望 多个 协作多队列 标准或非标准 高可用或容错 高 商用 50国家高性能计算中心（合肥）第三章 并行计算性能评测? 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 平均延迟度量标准国家高性能计算中心（合肥）51CPU的某些基本性能指标? 工作负载? 执行时间 ? 浮点运算数 ? 指令数目? 并行执行时间 T comput 为计算时间，T paro 为并行开销 时间，T comm为相互通信时间 T n = T comput + T paro+ T comm? 例：估计APRAM模型下执行时间T ?T ? max? 1 , T? ? ? Tn ? 1 ? T? n ? n ?国家高性能计算中心（合肥）52存储器性能远程 存储器 1-100GB 100-100K周期 1-300MB/S? 存储器的层次结构(C,L,B)寄存器 C&2KB L=0周期 B=1-32GB/S 1级 高速缓存 4-256KB 0-2周期 1-16GB/S 2级 高速缓存 64KB-4MB 2-10周期 1-4GB/S 主存 16MB-16GB 10-100周期 0.4-2GB/S 磁盘 1-100GB 100K-1M周期 1-16MB/S? 估计存储器的带宽 ? RISC add r1,r2,r3 r 8bytes 100MHz ? B = 3*8*100*106 B/s= 2.4GB/s国家高性能计算中心（合肥）53并行与通信开销? 并行和通信开销：相对于计算很大。? ? PowerPC (每个周期 15ns 执行4 创建一个进程1.4ms 可执行372000flops)? 开销的测量：乒--乓方法（Ping-Pong Scheme） 节点0发送m个字节给节点1；节点1从节点0接收 m个字节后，立即将消息发回节点0。总的时间除 以2，即可得到点到点通信时间，也就是执行单 一发送或接收操作的时间。 ? 可一般化为热土豆法（Hot-Potato），也称为救 火队法（Fire-Brigade) 0――1 ―― 2 ―― … ―― -n-1 ―― 0国家高性能计算中心（合肥）
54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 1 ? end_time = second（ ） ? total_time = end_time C start_time ? communication_time[i] = 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 0 ? endif国家高性能计算中心（合肥）55并行开销的表达式：点到点通信? 通信开销 t(m) = t0 + m/ r∞? 通信启动时间 t0? 渐近带宽r∞ ：传送无限长的消息时的通信速率 ? 半峰值长度m1/2 ：达到一半渐近带宽所要的消息长度 ? 特定性能π0：表示短消息带宽t0 = m1/2 / r∞ = 1 /π0国家高性能计算中心（合肥）
56并行开销的表达式：整体通信? 典型的整体通信有：? 播送（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个 字节。国家高性能计算中心（合肥）57机器的成本、价格与性/价比? 机器的成本与价格 ? 机器的性能/价格比 Performance/Cost Ratio ：系指 用单位代价（通常以百万美元表示）所获取的性能（通 常以MIPS或MFLOPS表示） ? 利用率（Utilization）：可达到的速度与峰值速度之比国家高性能计算中心（合肥）58算法级性能评测? 加速比性能定律? 并行系统的加速比是指对于一个给定的应用，并行算法（或并行程序） 的执行速度相对于串行算法（或串行程序）的执行速度加快了多少倍。 ? Amdahl 定律 ? Gustafson定律 ? Sun Ni定律? 可扩放性评测标准? 等效率度量标准 ? 等速度度量标准 ? 平均延迟度量标准国家高性能计算中心（合肥）59Amdahl 定律? P：处理器数； ? W：问题规模（计算负载、工作负载，给定问题的总计算量）；? Ws：应用程序中的串行分量，f是串行分量比例（f = Ws/W， Ws=W1）； ? WP：应用程序中可并行化部分，1-f为并行分量比例； ? Ws +W p =W；? Ts=T1 ：串行执行时间，T p ：并行执行时间； ? S：加速比，E：效率； ? 出发点：? 固定不变的计算负载； ? 固定的计算负载分布在多个处理器上的， ? 增加处理器加快执行速度，从而达到了加速的目的。国家高性能计算中心（合肥）60Ws ? Wp ? 固定负载的加速公式： S ? Ws ? WP / pAmdahl定律（cont‘d)? ? W s+ W p可相应地表示为f+（1-f） f ? (1 ? f ) p ? S? ? 1? f ? 1 ? f ( p ? 1)f ?? p→∞时，上式极限为： ? W o为额外开销pS= 1 / fWS ? WP W p S? ? ? WP W (1 ? f ) WS ? ? WO fW ? ? WO 1 ? f ( p ? 1) ? WO p /W p p国家高性能计算中心（合肥）
61Amdahl’s law (cont’d)T1 W1 W1 W1 W1 W1 W1工作负载W 执行时间T1024xT1 Tp T1 Tp T1 Tp Tp T1 Tp5加速比SS/(1+1023f)91x 48x 31xWp Wp WpWp Wp WpT1 Tp624x 4%1x 100%12345612340%1%2%3%处理器数P (a)处理器数P (b)程序中顺序部分的百分比f (c)国家高性能计算中心（合肥）62? 出发点：Gustafson定律? 对于很多大型计算，精度要求很高，即在此类应用中精度是个 关键因素，而计算时间是固定不变的。此时为了提高精度，必 须加大计算量，相应地亦必须增多处理器数才能维持时间不变； ? 除非学术研究，在实际应用中没有必要固定工作负载而计算程 序运行在不同数目的处理器上，增多处理器必须相应地增大问 题规模才有实际意义。WS ? pWp WS ? pWp ? ? Gustafson加速定律 : S ' ? WS ? p ? Wp / p WS ? WPS' ? f ? p (1-f) ? p ? f (1-p) ? p-f (p1)? 并行开销W o ：'WS ? pWP f ? p?1 ? f ? S ? ? WS ? WP ? WO 1 ? WO / W 63国家高性能计算中心（合肥）Gustafson定律（cont‘d)W1 W1工作负载WW1执行时间T1024x加速比S 'Wp W1 W1 W1 Wp1T1T1 T1 T1T1T1x993x 983xWp WpTpTp Tp TpTpTpS '23fWpWp2 3 4 5 6 1 2 3 4 5 60%1%2%3%4%处理器数P (a)处理器数P (b)程序中顺序部分的百分比f (c)国家高性能计算中心（合肥）64Sun 和 Ni定律? 基本思想：? 只要存储空间许可，应尽量增大问题规模以产生更好和更精确的解 （此时可能使执行时间略有增加）。 ? 假定在单节点上使用了全部存储容量M并在相应于W的时间内求解之， 此时工作负载W= fW + （1-f）W。 ? 在p 个节点的并行系统上，能够求解较大规模的问题是因为存储容量 可增加到pM。令因子G（p）反应存储容量增加到p倍时并行工作负载 的增加量，所以扩大后的工作负载W = fW + （1-f）G（p）W。? 存储受限的加速公式 ：f ? ?1 ? f ?G ? p ? fW ? ?1 ? f ?G ? p ?W ? S ? f ? ?1 ? f ?G ? p ? / p fW ? ?1 ? f ?G ? p ?W / p''? 并行开销W o:fW ? ?1 ? f ?WG? p ? f ? ?1 ? f ?G? p ? S ? ? fW ? ?1 ? f ?G? p ?W / p ? WO f ? ?1 ? f ?G? p ?/ p ? WO /W'国家高性能计算中心（合肥）
65Sun 和 Ni定律(cont’d)W1 W1工作负载WW1 W1 W1 W1 Wp1执行时间TWp Wp WpT1 TpT1 Tp2T1 TpT1 TpT1T1TpTpWpWp2 3 4 5 613456处理器数P (a)处理器数P (b)? G（p）=1时就是Amdahl加速定律； ? G（p）=p 变为 f + p（1-f），就是Gustafson加速定律 ? G（p）&p时，相应于计算机负载比存储要求增加得快， 此时 Sun和 N i 加速均比 Amdahl 加速和 Gustafson 加 速为高。国家高性能计算中心（合肥）
66加速比讨论? ? ? ? ? ? ? 参考的加速经验公式： p/log p≤S≤P 线性加速比：很少通信开销的矩阵相加、内积运算等 p/log p的加速 比：分治类的应用问题 通信密集类的应用问题 ：S = 1 / C （ p ） 超线性加速 绝对加速：最佳并行算法与串行算法 相对加速：同一算法在单机和并行机的运行时间国家高性能计算中心（合肥）67可扩放性评测标准? 并行计算的可扩放性（Scalability）也是主要性能指标? 可扩放性最简朴的含意是在确定的应用背景下，计算机系统（或算法或 程序等）性能随处理器数的增加而按比例提高的能力? 影响加速比的因素：处理器数与问题规模? 求解问题中的串行分量 ? 并行处理所引起的额外开销（通信、等待、竞争、冗余操作和同步等） ? 加大的处理器数超过了算法中的并发程度? 增加问题的规模有利于提高加速的因素：? 较大的问题规模可提供较高的并发度； ? 额外开销的增加可能慢于有效计算的增加； ? 算法中的串行分量比例不是固定不变的（串行部分所占的比例随着问题 规模的增大而缩小）。? 增加处理器数会增大额外开销和降低处理器利用率，所以对于一个 特定的并行系统（算法或程序），它们能否有效利用不断增加的处 理器的能力应是受限的，而度量这种能力就是可扩放性这一指标。国家高性能计算中心（合肥）
68可扩放性评测标准（cont‘d)? 可扩放性:调整什么和按什么比例调整? 并行计算要调整的是处理数p和问题规模W， ? 两者可按不同比例进行调整，此比例关系（可能是线性的，多 项式的或指数的等）就反映了可扩放的程度。? 并行算法和体系结构 ? 可扩放性研究的主要目的：? 确定解决某类问题用何种并行算法与何种并行体系结构的组合， 可以有效地利用大量的处理器； ? 对于运行于某种体系结构的并行机上的某种算法当移植到大规 模处理机上后运行的性能； ? 对固定的问题规模，确定在某类并行机上最优的处理器数与可 获得的最大的加速比； ? 用于指导改进并行算法和并行机体系结构，以使并行算法尽可 能地充分利用可扩充的大量处理器? 目前无一个公认的、标准的和被普遍接受的严格定义和 评判它的标准国家高性能计算中心（合肥）
69等效率度量标准? 令tie 和t io 分别是并行系统上第i个处理器的有用计算时间 和额外开销时间（包括通信、同步和空闲等待时间等）Te ?i ? Ts ? te i ?0 p ?1To ?i t ?o i ?0p ?1? T p 是p个处理器系统上并行算法的运行时间，对于任意i显 然有T p = tie +t io ，且 T e+ T o= pT p ? 问题的规模W为最佳串行算法所完成的计算量W=TeS?? 如果问题规模W 保持不变，处理器数p增加，开销To增大， 效率E下降。为了维持一定的效率（介于0与1之间），当 处理数p增大时，需要相应地增大问题规模W的值。由此定 义函数f E（p）为问题规模W随处理器数p变化的函数，为 等效率函数（ISO-efficiency Function）（Kumar1987）国家高性能计算中心（合肥）
70Te Te p p ? ? ? Te ? To T T Tp 1? o 1? o p Te WE ?S ? P1 1 ? T T 1? o 1? o Te W等效率度量标准（cont‘d)? 曲线1表示算法具有很好的扩放性；曲线2表示算法是 可扩放的；曲线 3表示算法是不可扩放的。 ? 优点：简单可定量计算的、少量的参数计算等效率函数 ? 缺点：如果To无法计算出（在共享存储并行机中）曲线 3 曲线 2工作负载W曲线 1处理器数 P国家高性能计算中心（合肥）
71等速度度量标准? p 表示处理器个数，W表示要求解问题的工作量或称问题规模 （在此可指浮点操作个数），T为并行执行时间，定义并行计算的 速度V为工作量W除以并行时间T ? p个处理器的并行系统的平均速度定义为并行速度V除以处理器个 数 p： V W V ? ? p pT ? W是使用p个处理器时算法的工作量，令W’表示当处理数从p增大 到p’时，为了保持整个系统的平均速度不变所需执行的工作量，则 可得到处理器数从 p到p’时平均速度可扩放度量标准公式W/p p'W ? ( p, p ' ) ? ? W ' / p' pW '国家高性能计算中心（合肥）72等速度度量标准（cont’d）? 优点：直观地使用易测量的机器性能速度指标来度量 ? 缺点：某些非浮点运算可能造成性能的变化问题规模处理器数执行时间处理器数平均速度处理器数执行时间国家高性能计算中心（合肥）处理器数73平均延迟度量标准? Ti为Pi的执行时间，包括包括延迟Li，Pi的总延迟时间为“L i+启动 时间+停止时间”。定义系统平均延迟时间为L ?W , p ? ? ? ?T para ? Ti ? Li ? pp i ?1? pTpara =To+ Ts? ? L ?W , p ? 在p个处理器上求解工作量为W问题的平均延迟 ? L ?W ' , p'?在p’个处理器上求解工作量为W’问题的平均延迟当处理器 数由p变到p’，而推持并行执行效率不变，则定义平均延迟可扩放 性度量标准为L ?W , p? ? Tpara ? Tseq pTo ? pL ?W , p ?L ?W , p ? ? ?E , p , p ' ? ? L ?W ' , p' ?国家高性能计算中心（合肥）74平均延迟度量标准（Cont’d)? 优点：平均延迟能在更低层次上衡量机器的性能 ? 缺点：需要特定的软硬件才能获得平均延迟5T5 = Tpara执行时间Tpara4 3 2 1T4 T1 T2 T3 T5 T6 T7P6 P7T8P8P1P2P3P4P5处理器数P 启动前与结束后空闲时间国家高性能计算中心（合肥）开销延迟 Li运行时间 Ti75并行计算中国科学技术大学计算机科学与技术系 国家高性能计算中心(合肥)2003年9月第二篇 并行算法的设计第四章 第五章 第六章 第七章 并行算法的设计基础 并行算法的一般设计方法 并行算法的基本设计技术 并行算法的一般设计过程第四章 并行算法的设计基础4.1 并行算法的基础知识 4.2 并行计算模型4.1 并行算法的基础知识4.1.1 并行算法的定义和分类 4.1.2 并行算法的表达 4.1.3 并行算法的复杂性度量 4.1.4 并行算法中的同步和通讯并行算法的定义和分类? 并行算法的定义? 算法 ? 并行算法：一些可同时执行的诸进程的集合，这些进程 互相作用和协调动作从而达到给定问题的求解。? 并行算法的分类? ? ? ? 数值计算和非数值计算 同步算法和异步算法 分布算法 确定算法和随机算法国家高性能计算中心（合肥）804.1 并行算法的基础知识4.1.1 并行算法的定义和分类 4.1.2 并行算法的表达 4.1.3 并行算法的复杂性度量 4.1.4 并行算法中的同步和通讯并行算法的表达? 描述语言? 可以使用类Algol、类Pascal等； ? 在描述语言中引入并行语句。? 并行语句示例? Par-do语句for i=1 to n par-do …… end for? for all语句for all Pi, where 0≤i≤k …… end for国家高性能计算中心（合肥）
824.1 并行算法的基础知识4.1.1 并行算法的定义和分类 4.1.2 并行算法的表达 4.1.3 并行算法的复杂性度量 4.1.4 并行算法中的同步和通讯并行算法的复杂性度量? 串行算法的复杂性度量? 最坏情况下的复杂度(Worst-CASE Complexity) ? 期望复杂度(Expected Complexity)? 并行算法的几个复杂性度量指标? 运行时间t(n):包含计算时间和通讯时间，分别用计算时 间步和选路时间步作单位。n为问题实例的输入规模。 ? 处理器数p(n) ? 并行算法成本c(n): c(n)=t(n)p(n) ? 总运算量W(n): 并行算法求解问题时所完成的总的操作 步数。国家高性能计算中心（合肥）84并行算法的复杂性度量? 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)国家高性能计算中心（合肥）854.1 并行算法的基础知识4.1.1 并行算法的定义和分类 4.1.2 并行算法的表达 4.1.3 并行算法的复杂性度量 4.1.4 并行算法中的同步和通讯并行算法的同步? 同步概念? 同步是在时间上强使各执行进程在某一点必须互相等待； ? 可用软件、硬件和固件的办法来实现。? 同步语句示例? 算法4.1 共享存储多处理器上求和算法 输入：A=(a0,…,an-1),处理器数p 输出：S=ΣaiBegin (1)S=0 (2)for all Pi where 0≤i≤p-1 do (2.1) L=0 (2.2) for j=i to n step p do L=L+aj end for end for (2.3) lock(S) S=S+L (2.4) unlock(S) end for End国家高性能计算中心（合肥）87? 通讯并行算法的通讯? 共享存储多处理器使用：global read(X,Y)和global write(X,Y) ? 分布存储多计算机使用：send(X,i)和receive(Y,j)? 通讯语句示例? 算法4.2 分布存储多计算机上矩阵向量乘算法 输入：处理器数p, A划分为B=A[1..n,(i-1)r+1..ir], x划分为w=w[(i-1)r+1;ir] 输出：P1保存乘积AXBegin (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国家高性能计算中心（合肥）88第四章 并行算法的设计基础4.1 并行算法的基础知识 4.2 并行计算模型4.2 并行计算模型4.2.1 PRAM模型 4.2.2 异步APRAM模型 4.2.3 BSP模型 4.2.4 logP模型PRAM模型? 基本概念? 由Fortune和Wyllie1978年提出，又称SIMD-SM模型。 有一个集中的共享存储器和一个指令控制器，通过SM 的R/W交换数据，隐式同步计算。? 结构图P LMControl UnitP LMP LMP LMInterconnection NetworkShared Memory 国家高性能计算中心（合肥）
91TEREW ? TCREW ? TCRCW? 分类? ? ?PRAM模型(1) PRAM-CRCW并发读并发写CPRAM-CRCW(Common PRAM-CRCW)：仅允许写入相同数据 PPRAM-CRCW(Priority PRAM-CRCW)：仅允许优先级最高的处理器写入 APRAM-CRCW(Arbitrary PRAM-CRCW)：允许任意处理器自由写入(2) PRAM-CREW并发读互斥写 (3) PRAM-EREW互斥读互斥写? 计算能力比较? PRAM-CRCW是最强的计算模型，PRAM-EREW可logp倍模拟 PRAM-CREW和PRAM-CRCW TEREW ? TCREW ? TCRCWTEREW ? O(TCREW ? log p) ? O(TCRCW ? log p)国家高性能计算中心（合肥）
92PRAM模型? 优点? 适合并行算法表示和复杂性分析，易于使用，隐藏了 并行机的通讯、同步等细节。? 缺点? 不适合MIMD并行机，忽略了SM的竞争、通讯延迟 等因素国家高性能计算中心（合肥）934.2 并行计算模型4.2.1 PRAM模型 4.2.2 异步APRAM模型 4.2.3 BSP模型 4.2.4 logP模型异步APRAM模型? 基本概念? 又称分相（Phase）PRAM或MIMD-SM。每个处理 器有其局部存储器、局部时钟、局部程序；无全局时 钟，各处理器异步执行；处理器通过SM进行通讯； 处理器间依赖关系，需在并行程序中显式地加入同步 路障。? 指令类型(1)全局读(3)局部操作(2)全局写 (4)同步国家高性能计算中心（合肥）95异步APRAM模型? 计算过程由同步障分开的全局相组成国家高性能计算中心（合肥）96异步APRAM模型? 计算时间设局部操作为单位时间；全局读/写平均时间为d，d随着处理器数 目的增加而增加；同步路障时间为B=B(p)非降函数。 满足关系 2 ? d ? B ? p ； B ? B( p) ? O(d log p) 或 O(d log p / log d ) 令 t ph 为全局相内各处理器执行时间最长者，则APRAM上的计算时 间为T ? ?t ph ? B ?同步障次数? 优缺点易编程和分析算法的复杂度，但与现实相差较远，其上并行算法非 常有限，也不适合MIMD-DM模型。国家高性能计算中心（合肥）974.2 并行计算模型4.2.1 PRAM模型 4.2.2 异步APRAM模型 4.2.3 BSP模型 4.2.4 logP模型BSP模型? 基本概念? 由Valiant(1990)提出的，“块”同步模型，是一种 异步MIMD-DM模型，支持消息传递系统，块内异步 并行，块间显式同步。? 模型参数? p：处理器数(带有存储器) ? l：同步障时间(Barrier synchronization time) ? g：带宽因子(time steps/packet)=1/bandwidth国家高性能计算中心（合肥）99BSP模型? 计算过程由若干超级步组成， 每个超级步计算模式为左图各处理器? 优缺点强调了计算和通讯的分离， 提供了一个编程环境，易于 程序复杂性分析。但需要显 式同步机制，限制至多h条 消息的传递等。图4.3局部计算全局通信 路障同步国家高性能计算中心（合肥）1004.2 并行计算模型4.2.1 PRAM模型 4.2.2 异步APRAM模型 4.2.3 BSP模型 4.2.4 logP模型logP模型? 基本概念? 由Culler(1993)年提出的，是一种分布存储的、点到 点通讯的多处理机模型，其中通讯由一组参数描述， 实行隐式同步。? 模型参数? L：network latency ? o：communication overhead ? g：gap=1/bandwidth ? P：#processors 注：L和g反映了通讯网络的容量国家高性能计算中心（合肥）
102logP模型? 优缺点捕捉了MPC的通讯瓶颈，隐藏了并行机的网络拓扑、路由、协议， 可以应用到共享存储、消息传递、数据并行的编程模型中；但难以 进行算法描述、设计和分析。?BSP vs. LogP? ? ? ? ? BSP?LogP：BSP块同步?BSP子集同步?BSP进程对同步＝ LogP BSP可以常数因子模拟LogP，LogP可以对数因子模拟BSP BSP＝LogP+Barriers－Overhead BSP提供了更方便的程设环境，LogP更好地利用了机器资源 BSP似乎更简单、方便和符合结构化编程国家高性能计算中心（合肥）103并行计算中国科学技术大学计算机科学与技术系 国家高性能计算中心(合肥)2003年9月第二篇 并行算法的设计第四章 第五章 第六章 第七章 并行算法的设计基础 并行算法的一般设计方法 并行算法的基本设计技术 并行算法的一般设计过程第五章 并行算法的一般设计方法5.1 串行算法的直接并行化 5.2 从问题描述开始设计并行算法 5.3 借用已有算法求解新问题5.1串行算法的直接并行化5.1.1 设计方法描述 5.1.2 快排序算法的并行化设计方法的描述? 方法描述? 发掘和利用现有串行算法中的并行性，直接将串行算法 改造为并行算法。? 评注? 由串行算法直接并行化的方法是并行算法设计的最常用 方法之一； ? 不是所有的串行算法都可以直接并行化的； ? 一个好的串行算法并不能并行化为一个好的并行算法； ? 许多数值串行算法可以并行化为有效的数值并行算法。国家高性能计算中心（合肥）1085.1串行算法的直接并行化5.1.1 设计方法描述 5.1.2 快排序算法的并行化快排序算法的并行化? 算法5.2 PRAM-CRCW上的快排序二叉树构造算法输入：序列(A1,…,An)和n个处理器 输出：供排序用的一棵二叉排序树 Begin (1)for each processor i do (2)repeat for each processor i&&root do (1.1)root=i if (Ai&Afi)∨(Ai=Afi∧i&fi) 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 endifend for(2.3)RCfi=i (2.4)if i=RCfi then exit else fi=RCfi endif endif end repeat Endelse国家高性能计算中心（合肥）110第五章 并行算法的一般设计方法5.1 串行算法的直接并行化 5.2 从问题描述开始设计并行算法 5.3 借用已有算法求解新问题从问题描述开始设计并行算法? 方法描述? 从问题本身描述出发，不考虑相应的串行算法，设计 一个全新的并行算法。? 评注? 挖掘问题的固有特性与并行的关系； ? 设计全新的并行算法是一个挑战性和创造性的工作； ? 利用串的周期性的PRAM-CRCW算法是一个很好的 范例；国家高性能计算中心（合肥）112第五章 并行算法的一般设计方法5.1 串行算法的直接并行化 5.2 从问题描述开始设计并行算法 5.3 借用已有算法求解新问题5.3 借用已有算法求解新问题5.3.1 设计方法描述 5.3.2 利用矩阵乘法求所有点对间 最短路径设计方法的描述? 方法描述? 找出求解问题和某个已解决问题之间的联系； ? 改造或利用已知算法应用到求解问题上。? 评注? 这是一项创造性的工作；? 使用矩阵乘法算法求解所有点对间最短路径是一个很好 的范例。国家高性能计算中心（合肥）1155.3 借用已有算法求解新问题5.3.1 设计方法描述 5.3.2 利用矩阵乘法求所有点对间 最短路径利用矩阵乘法求所有点对间最短路径? 计算原理有向图G=(V,E)，边权矩阵W=(wij)n×n，求最短路径长度矩阵 D=(dij)n×n，dij为vi到vj的最短路径长度。假定图中无负权有向回路， 记d(k)ij为vi到vj至多有k-1个中间结点的最短路径长，Dk=(d(k)ij)n×n， 则 (1) d(1)ij=wij 当 i&&j (如果vi到vj之间无边存在记为∞) d(1)ij=0 当 i=j (2) 无负权回路 ? dij＝d(n-1)ij (3) 利用最优性原理：d(k)ij=min1≤l≤n{d(k/2)il+d(k/2)lj} 视：”+” ? “×”， “min” ? “∑”，则上式变为 d(k)ij=∑1≤l≤n{d(k/2)il×d(k/2)lj} logn 1 2 4 2 (4) 应用矩阵乘法：D ? D ? D ? …? D (= Dn)? SIMD-CC上的并行算法：p139算法5.5国家高性能计算中心（合肥） 117并行计算中国科学技术大学计算机科学与技术系 国家高性能计算中心(合肥)2003年9月第二篇 并行算法的设计第四章 第五章 第六章 第七章 并行算法的设计基础 并行算法的一般设计方法 并行算法的基本设计技术 并行算法的一般设计过程第六章 并行算法的基本设计技术6.1 划分设计技术 6.2 分治设计技术 6.3 平衡树设计技术 6.4 倍增设计技术 6.5 流水线设计技术6.1 划分设计技术6.1.1 均匀划分技术 6.1.2 方根划分技术 6.1.3 对数划分技术 6.1.4 功能划分技术? 划分方法均匀划分技术n个元素A[1..n]分成p组，每组A[(i-1)n/p+1..in/p]，i=1~p? 示例：MIMD-SM模型上的PSRS排序begin (1)均匀划分：将n个元素A[1..n]均匀划分成p段，每个pi处理 A[(i-1)n/p+1..in/p] (2)局部排序：pi调用串行排序算法对A[(i-1)n/p+1..in/p]排序 (3)选取样本：pi从其有序子序列A[(i-1)n/p+1..in/p]中选取p个样本元素 (4)样本排序：用一台处理器对p2个样本元素进行串行排序 (5)选择主元：用一台处理器从排好序的样本序列中选取p-1个主元，并 播送给其他pi (6)主元划分：pi按主元将有序段A[(i-1)n/p+1..in/p]划分成p段 (7)全局交换：各处理器将其有序段按段号交换到对应的处理器中 (8)归并排序：各处理器对接收到的元素进行归并排序 end.国家高性能计算中心（合肥）122均匀划分技术? 例6.1 PSRS排序过程。N=27，p=3，PSRS排序如下：(a) 均匀划分 ：15 46 48 93 39 6 72 91 14 36 69 40 89 61 97 12 21 54 53 97 84 58 32 27 33 72 20 (b) 局部排序 ： 6 14 15 39 46 48 72 91 93 12 21 36 40 54 61 69 89 97 20 27 32 33 53 58 72 84 97 (c) 正则采样 ： (d) 采样排序 ： (e) 选择主元 ： 6 6 33 39 12 69 72 20 12 33 40 39 69 40 20 69 33 72 72 72(f) 主元划分 ： 6 14 15 39 46 48 72 91 93 12 21 36 40 54 61 69 89 97 20 27 32 33 53 58 72 84 97(g) 全局交换 ： 6 14 15 12 21 20 27 32 33 39 46 48 36 40 54 61 69 53 58 72 91 93 89 97 72 84 97(h) 归并排序 ： 6 12 14 15 20 21 27 32 33 36 39 40 46 48 53 54 58 61 69 72 72 84 89 91 93 97 97国家高性能计算中心（合肥） 图6.11236.1 划分设计技术6.1.1 均匀划分技术 6.1.2 方根划分技术 6.1.3 对数划分技术 6.1.4 功能划分技术? 划分方法方根划分技术pqn个元素A[1..n]分成A[(i-1)n^(1/2)+1..in^(1/2)]，i=1~n^(1/2)? 示例：SIMD-CREW模型上的 k ? ?? Valiant归并(1975年发表) //有序组A[1..p]、B[1..q], (假设p&=q), 处理器数 k ? ? pq?begin (1)方根划分: A,B分别按 i ? p ? 和 j ? q ?分成若干段（ i ?1~ ? p ? 、 j ?1 ~ ? q? ）； (2)段间比较: A划分元与B划分元比较(至多? p ?? ? q ? 对)， 确定A划分元应插入B中的区段； (3)段内比较: A划分元与B相应段内元素进行比较，并插入适当的位Z； (4)递归归并: B按插入的A划分元重新分段，与A相应段(A除去原划分元) 构成了成对的段组，对每对段组递归执行(1)~(3)，直至A 组为0时，递归结束; 各组仍按 k ? ? pq?分配处理器； end.国家高性能计算中心（合肥）
125方根划分技术?示例: A={1,3,8,9,11,13,15,16},p=8; B={2,4,5,6,7,10,12,14,17},q=9(1)(2)? B:A:1 2 1 23 4 3 48* 5* 8* 5*9 6 9 611 7 11 713* 10* 13* 10*1115 12 15 1216 14 16 14(p2=2)（ p ? 8,? p? ? 3, ? p? ? 2)q ? 3,17* （q ? 9, ??? q ? ? 3)(3)? B:A:317*A2: 15 B3: 14 ...... ...... ...... ...... 16 17A1: 1(p1=2) A2: 9 7B 1: 2 4 5 6 A1: 1 3*8(q1=6) B2: 10 12 13(q2=3) (p1=2) ...... ...... ...... ......B1: 2 4 5* 6 7 8*(q1=6) A11: 1* A11:B11: 2 3* B12: 4 5 6 7 8 A: B: 1 2 3 4 5 6 7 8 9 10 1112 1314 15 1617国家高性能计算中心（合肥）126?算法分析方根划分技术? ? q? － 1 ） ?? ? p ?（ pq ＝k(1)算法在并行递归过程中所需的处理器数≤ k ? ? pq ?＝k ； 段间比较: ? p ?? ? q ? 比较对数≤ ? pq?段内比较:?递归调用: 设 A,B 分成若干子段对为(p1,q1), (p2,q2),…… 则∑pi≤p, ∑qi≤q, 由 Cauchy 不等式＝&pi qi ?i i? ? ? p ? q ? ? ? pq ? ? k 综上，整个过程可用处理器数 k ? ? pq ?完成。??pi qi ?? ??(2)时间分析2 记λ i 是第 i 次递归后的 A 组最大长度，＝& ?0 ? p , ?i ? ? ?i ?1 ? ? ? ? ?p?i?算法在 ?i ? 常数C 时终止递归，即 ?ptk ( p, q) ? O(loglog p)国家高性能计算中心（合肥）2? i? ? 常数C＝& i ? loglog p ? 常数C1由(1)知算法中其他各步的时间为 O(1), 所以 Valiant 归并算法时间p?q 1276.1 划分设计技术6.1.1 均匀划分技术 6.1.2 方根划分技术 6.1.3 对数划分技术 6.1.4 功能划分技术? 划分方法对数划分技术n个元素A[1..n]分成A[(i-1)logn+1..ilogn]，i=1~n/logn? 示例：PRAM-CREW上的对数划分并行归并排序(1)归并过程: 设有序组A[1..n]和B[1..m]B = A = b1 a1... blogm ... aj(1)A0B0blogm +1 aj(1)+1...B1b2logm... ...Bi bilogm +1 aj(i )+1... b(i+1)logm ... ...aj(i+1)... aj(2)A1...Aij[i]=rank(bilogm:A)为bilogm在A中的位序，即A中小于等于bilogm的元素个数 (2)例：A=(4,6,7,10,12,15,18,20), B=(3,9,16,21) n=8, m=4 =&logm=log4=2 =& j[1]=rank(blogm:A)=rank(b2:A)=rank(9:A)=3, j[2]=…=8 B0: 3, 9 B1: 16, 21 A0: 4, 6, 7 A1: 10, 12, 15, 18, 20 A和B归并化为(A0, B0)和(A1, B1)的归并国家高性能计算中心（合肥）
1296.1 划分设计技术6.1.1 均匀划分技术 6.1.2 方根划分技术 6.1.3 对数划分技术 6.1.4 功能划分技术? 划分方法功能划分技术n个元素A[1..n]分成等长的p组，每组满足某种特性。 ? 示例：(m, n)选择问题(求出n个元素中前m个最小者) ? 功能划分：要求每组元素个数必须大于m； ? 算法：p148算法6.4 输入：A=(a1,…,an); 输出：前m个最小者；Begin (1) 功能划分：将A划分成g=n/m组，每组含m个元素； (2) 局部排序：使用Batcher排序网络将各组并行进行排序； (3) 两两比较：将所排序的各组两两进行比较，从而形成MIN序列； (4) 排序-比较：对各个MIN序列，重复执行第(2)和第(3)步，直至 选出m个最小者。 End国家高性能计算中心（合肥）
131功能划分技术mS MAX MIN...mm S(M) MAX MINSmSm...SSmm (M)m图6.3 (m-n)-选择过程国家高性能计算中心（合肥）
132第六章 并行算法的基本设计技术6.1 划分设计技术 6.2 分治设计技术 6.3 平衡树设计技术 6.4 倍增设计技术 6.5 流水线设计技术6.2 分治设计技术6.2.1 并行分治设计步骤 6.2.2 双调归并网络并行分治设计步骤? 将输入划分成若干个规模相等的子问 题； ? 同时(并行地)递归求解这些子问题； ? 并行地归并子问题的解，直至得到原 问题的解。国家高性能计算中心（合肥）1356.2 分治设计技术6.2.1 并行分治设计步骤 6.2.2 双调归并网络双调归并网络? 双调序列(p149定义6.2)(1,3,5,7,8,6,4,2,0) (8,7,6,4,2,0,1,3,5) (1,2,3,4,5,6,7,8) 以上都是双调序列? Batcher定理给定双调序列(x0,x1,…,xn-1), 对于si=min{xi,xi+n/2}和 li=max{xi,xi+n/2}， 则小序列(s0,s1,…,sn-1)和大序列(l0,l1,…,ln-1) 仍是双调序列国家高性能计算中心（合肥）
137双调归并网络? (4,4)双调归并网络国家高性能计算中心（合肥）138? Batcher双调归并算法双调归并网络Procedure BITONIC_MERG(x) Begin (1)for i=0 to n/2-1 par-do (1.1) si=min{xi,xi+n/2} (1.2) li=max{xi,xi+n/2} end for (2)Recursive Call: (2.1)BITONIC_MERG(MIN=(s0,…,sn/2-1)) (2.2)BITONIC_MERG(MIN=(l0,…, ln/2-1)) (3)output sequence MIN followed by sequence MAX End输入：双调序列X=(x0,x1,…,xn-1) 输出：非降有序序列Y=(y0,y1,…,yn-1)国家高性能计算中心（合肥）139第六章 并行算法的基本设计技术6.1 划分设计技术 6.2 分治设计技术 6.3 平衡树设计技术 6.4 倍增设计技术 6.5 流水线设计技术6.3 平衡树设计技术6.3.1 设计思想 6.3.2 求最大值 6.3.3 计算前缀和平衡树设计技术? 设计思想以树的叶结点为输入，中间结点为处理结点， 由叶向根或由根向叶逐层进行并行处理。? 示例? 求最大值 ? 计算前缀和国家高性能计算中心（合肥）1426.3 平衡树设计技术6.3.1 设计思想 6.3.2 求最大值 6.3.3 计算前缀和求最大值? 算法6.8: SIMD-TC(SM)上求最大值算法Beginfor k=m-1 to 0 do for j=2k to 2k+1-1 par-do A[j]=max{A[2j], A[2j+1]} end for P1 An/4 end for P1 An/2 An P2 An/2+1 An+3 P1 A1K=0Pn/2-1 An-2 Pn/2-1 A2n-4An/2-1 Pn/2 An-1K=m-2endK=m-1? 图示 ? 时间分析An+1An+2A2n-3A2n-2A2n-1t(n)=m×O(1)=O(logn) p(n)=n/2国家高性能计算中心（合肥）1446.3 平衡树设计技术6.3.1 设计思想 6.3.2 求最大值 6.3.3 计算前缀和计算前缀和? 问题定义n个元素{x1,x2,…,xn}，前缀和是n个部分和： Si=x1*x2*…*xi, 1≤i≤n 这里*可以是＋或×? 串行算法： Si=Si－1*xi 计算时间为 O(n) ? 并行算法：p154算法6.9 SIMD-TC上非递归算法令A[i]=xi, i=1~n, B[h,j]和C[h,j]为辅助数组(h=0~logn, j=1~n/2h) 数组B记录由叶到根正向遍历树中各结点的信息(求和) 数组C记录由根到叶反向遍历树中各结点的信息(播送前 缀和)国家高性能计算中心（合肥）
146计算前缀和? 例：n=8, p=8, C01~C08为前缀和国家高性能计算中心（合肥）147第六章 并行算法的基本设计技术6.1 划分设计技术 6.2 分治设计技术 6.3 平衡树设计技术 6.4 倍增设计技术 6.5 流水线设计技术6.4 倍增设计技术6.4.1 设计思想 6.4.2 表序问题 6.4.3 求森林的根倍增设计技术? 设计思想? 又称指针跳跃(pointer jumping)技术，特别适合于 处理链表或有向树之类的数据结构； ? 当递归调用时，所要处理数据之间的距离逐步加倍， 经过k步后即可完成距离为2k的所有数据的计算。? 示例? 表序问题 ? 求森林的根国家高性能计算中心（合肥）1506.4 倍增设计技术6.4.1 设计思想 6.4.2 表序问题 6.4.3 求森林的根? 问题描述表序问题a (1) (2)2 4 4 2 3 4 2 1 3 1 0 0 2 1b21c1d21e1f21 1g0 0n个元素的列表L，求出每个元素在L中的次第号(秩或位序或rank(k))，rank(k)可视为元素k至表尾的距离；? 示例：n=7(3)4 (1)p[a]=b, p[b]=c, p[c]=d, p[d]=e,(4) 5 6 p[e]=f, p[f]=g, p[g]=g r[a]=r[b]=r[c]=r[d]=r[e]=r[f]=1, r[g]=0 (2)p[a]=c, p[b]=d, p[c]=e, p[d]=f, p[e]=p[f]=p[g]=g r[a]=r[b]=r[c]=r[d]=r[e]=2, r[f]=1, r[g]=0 (3)p[a]=e, p[b]=f, p[c]=p[d]=p[e]=p[f]=p[g]=g r[a]=4, r[b]=4, r[c]=4, r[d]=3, r[e]=2, r[f]=1, r[g]=0 (4)p[a]=p[b]=p[c]=p[d]=p[e]=p[f]=p[g]=g r[a]=6, r[b]=5, r[c]=4, r[d]=3, r[e]=2, r[f]=1, r[g]=0国家高性能计算中心（合肥）152? 算法：P155算法6.10(2)执行 ?log n? 次 (2.1)对k并行地做表序问题//O(1)//O(logn) //O(1)(1)并行做：初始化p[k]和distance[k]如果k的后继不等于k的后继之后继，则(i) distance[k]= distance[k]+ distance[p[k]] (ii) p[k]=p[p[k]](2.2)对k并行地做rank[k]=distance[k] 运行时间：t(n)=O(logn)国家高性能计算中心（合肥）//O(1) p(n)=n 1536.4 倍增设计技术6.4.1 设计思想 6.4.2 表序问题 6.4.3 求森林的根求森林的根? 问题描述一组有向树F中, 如果&i, j&是F中的一条弧，则p[i]=j(即 j是i的双亲)；若i为根，则p[i]=i。求每个结点j(j=1~n) 的树根s[j].? 示例初始时P[1]=p[2]=5 p[3]=p[4]=p[5]=6 P[6]=p[7]=8 p[8]=8 P[9]=10 p[10]=11 p[11]=12 p[12]=13 p[13]=13 3 s[i]=p[i]68137 5 4 1 2 9 1012 11国家高性能计算中心（合肥）(a)155求森林的根? 示例第一次迭代后8 6 5 4 1 2 9 11 3 10 4 5 10 11 13 1 7 12 2 6第二次迭代后8 7 9 12 133? 算法：P157算法6.11 ? 运行时间：t(n)=O(logn)国家高性能计算中心（合肥） (b)(c)W(n)=O(nlogn)156第六章 并行算法的基本设计技术6.1 划分设计技术 6.2 分治设计技术 6.3 平衡树设计技术 6.4 倍增设计技术 6.5 流水线设计技术6.5 流水线设计技术6.5.1 设计思想 6.5.2 5-point DFT的计算流水线设计技术? 设计思想? 将算法流程划分成p个前后衔接的任务片断，每个 任务片断的输出作为下一个任务片断的输入； ? 所有任务片断按同样的速率产生出结果。? 评注? 流水线技术是一种广泛应用在并行处理中的技术； ? 脉动算法(Systolic algorithm)是其中一种流水线技术；国家高性能计算中心（合肥）1596.5 流水线设计技术6.5.1 设计思想 6.5.2 5-point DFT的计算5-point DFT的计算? 问题描述5-point DFT的计算。应用秦九韶(Horner)法则，? y0 ? b0 ? a4? 0 ? a3? 0 ? a2? 0 ? a1? 0 ? a0 ? y0 ? (((a4? 0 ? a3 )? 0 ? a2 )? 0 ? a1 )? 0 ? a0 ? ? 4 3 2 1 1 1 1 1 y ? b ? a ? ? a ? ? a ? ? a ? ? a y ? ((( a ? ? a ) ? ? a ) ? ? a ) ? ? a0 1 1 4 3 2 1 0 1 4 3 2 1 ? ? ? ? 8 6 4 2 ? ? y2 ? b2 ? a4? ? a3? ? a2? ? a1? ? a0 ? y2 ? (((a4? 2 ? a3 )? 2 ? a2 )? 2 ? a1 )? 2 ? a0 ? y ? b ? a ?12 ? a ? 6 ? a ? 4 ? a ? 2 ? a ? y ? (((a ? 3 ? a )? 3 ? a )? 3 ? a )? 3 ? a 4 3 2 1 0 ? 3 3 4 16 3 6 2 4 1 2 0 ? 3 4 4 4 4 ? y ? b ? a ? ? a ? ? a ? ? a ? ? a y ? ((( a ? ? a ) ? ? a ) ? ? a ) ? ? a0 ? 3 2 1 0 4 3 2 1 ? 4 ? 4 4 4国家高性能计算中心（合肥）1615-point DFT的计算? 示例：p(n)=n-1, t(n)=2n-2=O(n)ω4 a41a4 ω a4 ω2 a4a31a2a1a0a3y0 ω y1 ω2 y2 ω3 y3a21a1a0a3a2y0 ω y1 ω2 y2(b)a11a0X Yin ina X out Y out(a)X out Y out X in Y in X in +aω3 a4 ω4 a4a3 a3a2 a2a1 a1y0 ω y1a0 a0 y0国家高性能计算中心（合肥）162并行计算中国科学技术大学计算机科学与技术系 国家高性能计算中心(合肥)2003年9月第二篇 并行算法的设计第四章 第五章 第六章 第七章 并行算法的设计基础 并行算法的一般设计方法 并行算法的基本设计技术 并行算法的一般设计过程第七章 并行算法的一般设计过程7.1 PCAM设计方法学 7.2 划分 7.3 通讯 7.4 组合 7.5 映射 7.6 小结PCAM设计方法学? 设计并行算法的四个阶段? ? ? ? 划分(Partitioning) 通讯(Communication) 组合(Agglomeration) 映射(Mapping)? ? ? ?划分：分解成小的任务，开拓并发性； 通讯：确定诸任务间的数据交换，监测划分的合理性； 组合：依据任务的局部性，组合成更大的任务； 映射：将每个任务分配到处理器上，提高算法的性能。 166国家高性能计算中心（合肥）PCAM设计过程问题 划分通信组合映射国家高性能计算中心（合肥）167第七章 并行算法的一般设计过程7.1 PCAM设计方法学 7.2 划分 7.3 通讯 7.4 组合 7.5 映射 7.6 小结7.2 划分7.2.1 方法描述 7.2.2 域分解 7.2.3 功能分解 7.2.4 划分判据划分方法描述? 充分开拓算法的并发性和可扩放性； ? 先进行数据分解(称域分解)，再进行计算功 能的分解(称功能分解)； ? 使数据集和计算集互不相交； ? 划分阶段忽略处理器数目和目标机器的体 系结构； ? 能分为两类划分：? 域分解(domain decomposition) ? 功能分解(functional decomposition)国家高性能计算中心（合肥）
1707.2 划分7.2.1 方法描述 7.2.2 域分解 7.2.3 功能分解 7.2.4 划分判据域分解? 划分的对象是数据，可以是算法的输入 数据、中间处理数据和输出数据； ? 将数据分解成大致相等的小数据片； ? 划分时考虑数据上的相应操作； ? 如果一个任务需要别的任务中的数据， 则会产生任务间的通讯；国家高性能计算中心（合肥）172域分解? 示例：三维网格的域分解，各格点上计算 都是重复的。下图是三种分解方法：1\D2\D3\D图7.2国家高性能计算中心（合肥）
173域分解? 不规则区域的分解示例：国家高性能计算中心（合肥）1747.2 划分7.2.1 方法描述 7.2.2 域分解 7.2.3 功能分解 7.2.4 划分判据功能分解? 划分的对象是计算，将计算划分为不同 的任务，其出发点不同于域分解； ? 划分后，研究不同任务所需的数据。如 果这些数据不相交的，则划分是成功的； 如果数据有相当的重叠， 意味着要重新 进行域分解和功能分解； ? 功能分解是一种更深层次的分解。国家高性能计算中心（合肥）176功能分解? 示例1：搜索树? 示例2：气候模型国家高性能计算中心（合肥）1777.2 划分7.2.1 方法描述 7.2.2 域分解 7.2.3 功能分解 7.2.4 划分判据划分判据? ? ? ? ? 划分是否具有灵活性？ 划分是否避免了冗余计算和存储？ 划分任务尺寸是否大致相当？ 任务数与问题尺寸是否成比例？ 功能分解是一种更深层次的分解，是否 合理？国家高性能计算中心（合肥）179第七章 并行算法的一般设计过程7.1 PCAM设计方法学 7.2 划分 7.3 通讯 7.4 组合 7.5 映射 7.6 小结7.3 通讯7.3.1 方法描述 7.3.2 四种通讯模式 7.3.3 通讯判据通讯方法描述? 通讯是PCAM设计过程的重要阶段； ? 划分产生的诸任务，一般不能完全独立执 行，需要在任务间进行数据交流；从而产 生了通讯； ? 功能分解确定了诸任务之间的数据流； ? 诸任务是并发执行的，通讯则限制了这种 并发性；国家高性能计算中心（合肥）1827.3 通讯7.3.1 方法描述 7.3.2 四种通讯模式 7.3.3 通讯判据四种通讯模式? ? ? ? 局部/全局通讯 结构化/非结构化通讯 静态/动态通讯 同步/异步通讯国家高性能计算中心（合肥）184局部通讯? 通讯限制在一个邻域内国家高性能计算中心（合肥）185全局通讯? 通讯非局部的 ? 例如：? All to All ? Master-Worker1 3 7 25国家高性能计算中心（合肥）186结构化通讯? 每个任务的通讯模式是相同的； ? 下面是否存在一个相同通讯模式？国家高性能计算中心（合肥）187非结构化通讯? 没有一个统一的通讯模式 ? 例如：无结构化网格国家高性能计算中心（合肥）1887.3 通讯7.3.1 方法描述 7.3.2 四种通讯模式 7.3.3 通讯判据通讯判据? ? ? ? 所有任务是否执行大致相当的通讯? 是否尽可能的局部通讯？ 通讯操作是否能并行执行? 同步任务的计算能否并行执行？国家高性能计算中心（合肥）190第七章 并行算法的一般设计过程7.1 PCAM设计方法学 7.2 划分 7.3 通讯 7.4 组合 7.5 映射 7.6 小结7.4 组合7.4.1 方法描述 7.4.2 表面-容积效应 7.4.3 重复计算 7.4.4 组合判据方法描述? 组合是由抽象到具体的过程，是将组合的 任务能在一类并行机上有效的执行； ? 合并小尺寸任务，减少任务数。如果任务 数恰好等于处理器数，则也完成了映射过 程； ? 通过增加任务的粒度和重复计算，可以减 少通讯成本； ? 保持映射和扩展的灵活性，降低软件工程 成本；国家高性能计算中心（合肥）
1937.4 组合7.4.1 方法描述 7.4.2 表面-容积效应 7.4.3 重复计算 7.4.4 组合判据表面-容积效应? 通讯量与任务子集的表面成正比，计算 量与任务子集的体积成正比； ? 增加重复计算有可能减少通讯量；国家高性能计算中心（合肥）1957.4 组合7.4.1 方法描述 7.4.2 表面-容积效应 7.4.3 重复计算 7.4.4 组合判据重复计算? 重复计算减少通讯量，但增加了计算量， 应保持恰当的平衡； ? 重复计算的目标应减少算法的总运算时间；国家高性能计算中心（合肥）197重复计算? 示例：二叉树上N个处理器求N个数的全和， 要求每个处理器均保持全和。s s b b0b b1s0s1s2s3b2b3二叉树上求和，共需2logN步国家高性能计算中心（合肥）198? 示例：二叉树上N个处理器求N个数的全和， 要求每个处理器均保持全和。0 Σ 7 0 Σ 7 0 Σ 7 0 Σ 7 0 Σ 7 0 Σ 7 0 Σ 7 0 Σ 7重复计算0 Σ30 Σ30 Σ30 Σ34 Σ74 Σ74 Σ74 Σ70 Σ10 Σ12 Σ32 Σ34 Σ54 Σ56 Σ76 Σ701234567蝶式结构求和，使用了重复计算，共需logN步国家高性能计算中心（合肥）
1997.4 组合7.4.1 方法描述 7.4.2 表面-容积效应 7.4.3 重复计算 7.4.4 组合判据组合判据? ? ? ? ? ? 增加粒度是否减少了通讯成本？ 重复计算是否已权衡了其得益？ 是否保持了灵活性和可扩放性？ 组合的任务数是否与问题尺寸成比例? 是否保持了类似的计算和通讯？ 有没有减少并行执行的机会？国家高性能计算中心（合肥）201第七章 并行算法的一般设计过程7.1 PCAM设计方法学 7.2 划分 7.3 通讯 7.4 组合 7.5 映射 7.6 小结7.5 映射7.5.1 方法描述 7.5.2 负载平衡算法 7.5.3 任务调度算法 7.5.4 映射判据方法描述? 每个任务要映射到具体的处理器，定位到 运行机器上； ? 任务数大于处理器数时，存在负载平衡和 任务调度问题； ? 映射的目标：减少算法的执行时间? 并发的任务 ? 不同的处理器 ? 任务之间存在高通讯的 ? 同一处理器? 映射实际是一种权衡，属于NP完全问题；国家高性能计算中心（合肥）
2047.5 映射7.5.1 方法描述 7.5.2 负载平衡算法 7.5.3 任务调度算法 7.5.4 映射判据负载平衡算法? ? ? ? 静态的：事先确定； 概率的：随机确定； 动态的：执行期间动态负载； 基于域分解的：? ? ? ? 递归对剖 局部算法 概率方法 循环映射 206国家高性能计算中心（合肥）7.5 映射7.5.1 方法描述 7.5.2 负载平衡算法 7.5.3 任务调度算法 7.5.4 映射判据任务调度算法? 任务放在集中的或分散的任务池中，使用 任务调度算法将池中的任务分配给特定的 处理器。下面是两种常用调度模式： ? 经理/雇员模式 ww w 员工 w p p p ppp 经理 w w w? 非集中模式国家高性能计算中心（合肥）2087.5 映射7.5.1 方法描述 7.5.2 负载平衡算法 7.5.3 任务调度算法 7.5.4 映射判据映射判据? 采用集中式负载平衡方案，是否存在通 讯瓶颈？ ? 采用动态负载平衡方案，调度策略的成 本如何？国家高性能计算中心（合肥）210第七章 并行算法的一般设计过程7.1 PCAM设计方法学 7.2 划分 7.3 通讯 7.4 组合 7.5 映射 7.6 小结小结? 划分? 域分解和功能分解? 通讯? 任务间的数据交换? 组合? 任务的合并使得算法更有效? 映射? 将任务分配到处理器，并保持负载平衡国家高性能计算中心（合肥）
212并行计算中国科学技术大学计算机科学与技术系 国家高性能计算中心(合肥)2003年9月第三篇 并行数值算法第八章 基本通讯操作 第九章 稠密矩阵运算 第十章 线性方程组的求解 第十一章 快速傅里叶变换第八章 并行数值算法8.0 8.1 8.2 8.3 8.4 预备知识 选路方法与开关技术 单一信包一到一传输 一到多播送 多到多播送预备知识? 选路(Routing)? 又称为选径或路由。产生消息从发源地到目的地所取 的路径, 要求具有较低通讯延迟、无死锁和容错能力。 应用于网络或并行机上的信息交换。? 消息、信包、片? 消息(Message)：是在多计算机系统的处理接点之间 传递包含数据和同步消息的信息包。它是一种逻辑单 位，可由任意数量的包构成。 ? 包(Packet)：包的长度随协议不同而不同，它是信息 传送的最小单位，64-512位。 ? 片(Flit)：片的长度固定，一般为8位。国家高性能计算中心（合肥）
216预备知识? 消息、信包、片的相互关系消息 包包头片 数据片 …… 顺序号尾片片F F F F F F F F国家高性能计算中心（合肥）217? 一些术语预备知识? 信道带宽b：每个信道有w位宽和信号传输率f = 1/t (t 是时钟周期), b = wf bits/sec ? 节点和开关的度：与节点和开关相连的信道数目 ? 路径：信包在网络中走过的开关和链路(link)序列 ? 路由长度或距离：路由路径中包括的链路(link)数目? 信包传输性能参数? ? ? ? 启动时间ts(startup time)：准备包头信息等 节点延迟时间th(per-hop time)：包头穿越相邻节点的时间 字传输时间tw(transfer time)：传输每个字的时间 链路数l 、信包大小m 218国家高性能计算中心（合肥）预备知识? 选路算法的三种机制? 基于算术的: 开关中具有简单的算术运算功能，如维 序选路； ? 基于源地址的: 在源点时就将沿路径的各个开关的输 出端口地址p0,p1,?,pn包在信包的头部，每个开关只 是对信包头的输出端口地址进行剥离； ? 基于查表的: 开关中含有一个选路表，对信包头中的 选路域查出输出端口地址。国家高性能计算中心（合肥）219预备知识? 选路方式? ?存储－转发（Store and Forward） ?信包? ? ） ?虫孔（Worm hole ?线路 : 用交换机 ? 息都已到达网络 ?静态 : 在选路开始时所有的信 ? 网络 ?动态 : 信包可在任意时刻到达 ?联机(online) : 没有事先计算好的路径 ? ?脱机(offline) : 事先算好传输路径 ?一到一（单播） ? : 每个处理器开始时最多 发送一条信包， ?一到一（置换） ? 每条信包有且仅有一个 目的地； ? ?多到一（集中） ?一到多（多播） ? ） ?一到所有（广播、组播 ?多到多（会议） ?国家高性能计算中心（合肥）
220第八章 并行数值算法8.0 8.1 8.2 8.3 8.4 预备知识 选路方法与开关技术 单一信包一到一传输 一到多播送 多到多播送8.1 选路方法与开关技术8.1.1 选路方法 8.1.2 开关技术选路方法? 分类? 最短路径/非最短路径(贪心选路/随机选路)， 如维序选路是贪心的，二阶段维序选路是随机的 ? 确定选路/自适应选路(寻径确定/寻径视网络状况)? 维序选路(Dimension-Ordered Routing)：一种确定的最短路径选路 ? 二维网孔中的维序选路: X-Y选路 ? 超立方中的维序选路: E-立方选路国家高性能计算中心（合肥）223选路方法? X-Y选路算法? 算法8.1：二维网孔上的X-Y选路算法 begin step1: 沿X方向将信包送至目的地处理器所在的列 step2: 沿Y方向将信包送至目的地处理器所在的行 end国家高性能计算中心（合肥）224选路方法? 例8.1 (P186)N W 0,7 0,6 0,5 E 0,4 0,3 0,2 0,1 1,7 1,6 1,5 1,4 1,3 1,2 1,1 1,0 2,7 2,6 2,5 2,4 2,3 2,2 2,1 2,0 3,7 3,6 3,5 3,4 3,3 3,2 3,1 3,0 4,7 4,6 4,5 4,4 4,3 4,2 4,1 4,0 5,7 5,6 5,5 5,4 5,3 5,2 5,1 5,0 6,7 6,6 6,5 6,4 6,3 6,2 6,1 6,0 7,7 7,6 7,5 7,4 7,3 7,2 7,1 7,0i,jSy0,0x4( 源;目的 )对:国家高性能计算中心（合肥）(2,1;7,6) (0,7;4,2)(5,4;2,0) (6,3;1,5) 图8.1 225选路方法? E-立方选路算法? 路由计算： sn-1sn-2?s1s0(源地址) 异或 ? dn-1dn-2?d1d0(目的地址) rn-1 rn-2 ?r1 r0 (路由值) ? 路由过程： sn-1sn-2?s1s0 ? sn-1sn-2?s1s0 ?r0 ? sn-1sn-2?s1s0 ?r1 ? ? ? 算法8.2 ：超立方网络上的E-立方选路算法(P186)国家高性能计算中心（合肥）226选路方法? 例8.2 (P187)0110(S) 1101(D) 1011(R)11
dim2 dim3 源： S=0110 目的： D=1101 路径： dim1 01 dim4 11 110111101111011101国家高性能计算中心（合肥）图8.22278.1 选路方法与开关技术8.1.1 选路方法 8.1.2 开关技术开关技术? 存储转发(Store-and-Forward)选路? 消息被分成基本的传输单位----信包(Packet), 每个信包 都含有寻径信息； ? 当一个信包到达中间节点A时，A把整个信包放入其 通信缓冲器中，然后在选路算法的控制下选择下一个 相邻节点B，当从A到B的通道空闲并且B的通信缓冲 器可用时，把信包从A发向B； ? 信包的传输时间: tcomm (SF) = ts + (mtw + th)l=O(ml)缺点：? 每个结点必须对整个消息和信包进行缓冲，缓冲器较 大； ? 网络时延与发送消息所经历的节点数成正比国家高性能计算中心（合肥）
229开关技术? 切通(Cut Through)选路? 在传递一个消息之前，就为它建立一条从源结点到 目的结点的物理通道。在传递的全部过程中，线路 的每一段都被占用，当消息的尾部经过网络后，整 条物理链路才被废弃。 ? 传输时间: tcomm (CT) = ts + mtw + lth = O(m+l)缺点：? 物理通道非共享 ? 传输过程中物理通道一直被占用国家高性能计算中心（合肥）230? 虫孔(Wormhole)选路开关技术? Dally于1986年提出，利用了前二种方法的优点，减少 了缓冲区，提高了物理通道的利用。 ? 首先把一个消息分成许多很小的片，消息的头片包含 了这个消息的所有寻径信息。尾片是一个其最后包含 了消息结束符的片。中间的片均为数据片； ? 片是最小信息单位。每个结点上只需要缓冲一个片就 能满足要求； ? 用一个头片直接牵引一条从输入链路到输出链路的路 径的方法来进行操作。每个消息中的片以流水的方式 在网络中向前“蠕动”。每个片相当于Worm的一个节， “蠕动”以节为单位顺序地向前爬行。当消息的尾片 向前“蠕动”一步后，它刚才所占用的结点就被放弃 了。国家高性能计算中心（合肥）
231开关技术? 虫孔(Wormhole)选路优点：(1)每个结点的缓冲器的需求量小，易于用VLSI实现； (2)较低的网络传输延迟。存储转发传输延迟基本上正比 于消息在网络中传输的距离; Wormhole与线路开关的网 络传输延迟正比于消息包的长度，传输距离对它的影响 很小（消息包较长时的情况）； (3)通道共享性好、利用率高； (4)易于实现Multicast和Broadcast。国家高性能计算中心（合肥）232开关技术? 几种开关技术的时空图tcomm(SF) mtwP1 P2 P3 P4 头 (a) 信包 数据 lTtcomm(CT) mtwP1 P2 P3 P4 (b) lT国家高性能计算中心（合肥）图8.4 233第八章 并行数值算法8.0 8.1 8.2 8.3 8.4 预备知识 选路方法与开关技术 单一信包一到一传输 一到多播送 多到多播送? 距离l的计算： 对于p个处理器? 一维环形： l ? ? p / 2? ? 带环绕Mesh( p ? p )：l ? 2? ? 超立方： l ? log pp /2单一信包一到一传输?? tcomm(SF)的计算(可由(8.1b)式得到)? 一维环形： tcomm (SF) ? ts ? tw ? m ? ? p / 2? ? 带环绕Mesh： tcomm (SF) ? ts ? 2tw ? m ? ? p / 2? ? 超立方：tcomm (SF) ? ts ? tw ? m ? log p? tcomm(CT)的计算(可由(8.2b)式得到)tcomm (CT ) ? ts ? mtw? 如果m&&p： tcomm(SF)≈ tcomm(CT) = ts+mtw国家高性能计算中心（合肥）
235第八章 并行数值算法8.0 8.1 8.2 8.3 8.4 预备知识 选路方法与开关技术 单一信包一到一传输 一到多播送 多到多播送8.3 一到多播送8.3.1 SF模式 8.3.2 CT模式一到多播送―SF模式?环? 步骤： ①先左右邻近传送;②再左右二个方向同时播送 3 4 ? 示例：7 6 5 42 0 1 1 2 2 3 34图8.5? 通讯时间： tone?to?all (SF) ? (ts ? mtw )? p / 2?国家高性能计算中心（合肥）
238一到多播送―SF模式? 环绕网孔? 步骤：①先完成一行中的播送;②再同时进行各列的 播送 12 13 14 15 ? 示例： 4 4 4 4 共4步(2步行、2步列)8 4 4 3 0 1 9 4 5 3 1 2 10 4 6 3 2 2 11 4 7 3 3t ? 通讯时间：国家高性能计算中心（合肥）? p? ( SF ) ? 2 ( t ? m t ) ? one ?to? all s w ? ? 2 ?图 8.6239一到多播送―SF模式? 超立方? 步骤：从低维到高维，依次进行播送; ? 示例： (110) 3 (111)6 (010) 2 3 2 (000) 0 3 1 1 (011) 3 2 4 (100) (001) 3 5 (101) 7? 通讯时间： tone ?to?all (SF) ? (ts ? mtw ) log p国家高性能计算中心（合肥）
2408.3 一到多播送8.3.1 SF模式 8.3.2 CT模式一到多播送―CT模式?环? 步骤： (1)先发送至p/2远的处理器; 7 (2)再同时发送至p/22远的处理器; ?? 0 i (i)再同时发送至p/2 远的处理器; ? 示例：图8.8( 8.2 ) log p i ?13 2 6 5341 1 2 3 2 33图 8.8? 通讯时间：tone ?to?all (CT ) ? ? (t s ? m tw ? th p / 2i )? t s log p ? m tw log p ? t h ( p ? 1) ? (t s ? m tw ) log p国家高性能计算中心（合肥） (t h可忽略时)242一到多播送―CT模式? 网孔? 步骤： (1)先进行行播送;// ts log p ? mtw log p ? th ( p ?1)3 4 2 6 7 4 10 11 4 14 15 4(2)再同时进行列播送;// ts log p ? mtw log p ? th ( p ?1)33 1 4 2 0 4 1 5 43 9 43 13 4 2 8 12? 示例：图8.9? 通讯时间：tone ?to?all (CT ) ? 2(t s log p ? m tw log p ? th ( p ? 1)) ? (t s ? m tw ) log p ? 2th ( p ? 1)国家高性能计算中心（合肥） 图 8.9243一到多播送―CT模式? 超立方? 步骤： 依次从低维到高维播送, d-立方, d=0,1,2,3,4…;? 通讯时间： tone?to?all (CT ) ? (ts ? mtw ) log p国家高性能计算中心（合肥）244第八章 并行数值算法8.0 8.1 8.2 8.3 8.4 预备知识 选路方法与开关技术 单一信包一到一传输 一到多播送 多到多播送8.3 一到多播送8.3.1 SF模式 8.3.2 CT模式多到多播送―SF模式?环? 步骤： 同时向右(或左)播送 刚接收到的信包 ? 示例：图8.10? 通讯时间：tall ?to?all (SF) ? (ts ? mtw )( p ?1)7(0) 7 7(1) 0 7(2)(7,6,5,4,3,2,1) (0,7,6,5,4,3,2)1(6) 7 (7) 1(7) (0) 0 1(0) 2(5) 7 (7,6) (0,7) 0 2(7) 1 6 1 (1) 6 (6)1(5) 5 (5) (2) 2 1(1) 2(4) 5 (6,5) (1,0) 2 2(0)1(4) 4 (4) 1(3) (3) 3 1(2) 2(3) 4 (5,4) (2,1) (4,3) (3,2) 3 2(1) 第2通信步 2(2) 第1通信步第2步传送数据22(6)...7(7) 6(6,5,4,3,2,1,0)7(6) 5(5,4,3,2,1,0,7) (2,1,0,7,6,5,4)4(4,3,2,1,0,7,6)7(5) 3(3,2,1,0,7,6,5)(1,0,7,6,5,4,3)1 7(3)2 7(4)第7通信步国家高性能计算中心（合肥） 图8.10...已有数据247多到多播送―SF模式? 环绕网孔? 步骤： (1)先进行行的播送； (2)再进行列的播送； ? 示例：图8.11(6) 6 (3) 3 4 (7) 7 (4) 5 (8) 8 (5) (3,4,5) 3 (3,4,5) 4 (3,4,5) 5 (6,7,8) 6 (6,7,8) 7 (6,7,8) 80 (0)1 (1) (a)2 (2)0 (0,1,2)1 (0,1,2) (b)2 (0,1,2)? 通讯时间：? 2t s ( p ? 1) ? m tw ( p ? 1)国家高性能计算中心（合肥） 图8.11tall ?to?all ( SF) ? (t s ? m tw )( p ? 1) ? (t s ? m p ? t w )( p ? 1)248多到多播送―SF模式(6) 6 3 (3) 7 (7) (2,3) (2) 2 2 (4,5) (4) (0) 0 (a) 4 1 (1) 5 (5) (0,1) 0 (b)(4,5,6,7) (0,...,7) (0,...,7)(6,7)6 3 (2,3) (5,6) 4 1 (0,1)7(6,7)? 超立方? 步骤： 依次按维进行 多到多的播送； ? 示例：图8.125(4,5)(4,5,6,7)6(0,1,2,3)7(0,...,7)6(0,...,7)7 32(0,1,2,3)3(4,5,6,7)2(0,...,7)? 通讯时间：tall ?to?all ( SF) ? ? (t s ? 2 m tw )i ?1 i ?1 log p(0,1,2,3)(4,5,6,7)(0,...,7)4 0 (c) 15(0,...,7) (0,1,2,3)4 0 (d) 15(0,...,7)? t s log p ? m tw ( p ? 1)国家高性能计算中心（合肥）图8.122498.3 一到多播送8.3.1 SF模式 8.3.2 CT模式多到多