并行算法实践

并行计算,第一级,第二级,第三级,第一级,第二级,第三级,*,*,并行算法实践,上篇 并行程序设计导论,2024/9/14,1,并行算法实践,上篇 并行程序设计导论,单元,I,并行程序设计基础,单元,II,并行程序编程指南,单元,III,并行程序开发方法,2024/9/14,2,单元,I,并行程序设计基础,第一章 并行计算机系统与结构模型,第二章,PC,机群的搭建,第三章 并行程序设计简介,2024/9/14,3,第一章 并行计算机系统与结构模型,1.1,典型并行计算机系统简介,1.1.1,阵列处理机,1.1.2,向量处理机,1.1.3,共享存储多处理机,1.1.4,分布存储多计算机,1.1.5,分布共享存储多处理机,1.2,当代并行计算机体系结构,1.2.1,并行计算机体系结构模型,1.2.2,并行计算机存储结构模型,1.2.3,分布式高速缓存与主存体系结构,1.3,小结,2024/9/14,4,阵列处理机,向量处理机,共享存储多处理机,分布存储多计算机,典型并行计算机系统,分布存储,共享存储,流水线,并行向量机,紧耦合多机系统,同构对称对机系统,DSM/SVM,2024/9/14,5,阵列处理机的两种基本结构,(a),分布存储阵列机,(b),共享存储阵列机,2024/9/14,6,阵列处理机的特点,SIMD单指令多数据流机,利用资源重复开拓计算空间的并行,同步计算所有PE执行相同操作,适于特定问题（如有限差分、矩阵运算等）求解,2024/9/14,7,Cray-1,的向量处理,2024/9/14,8,共享存储的多处理机,MIMD多指令多数据流机,单一的共享地址空间,易于编程、难于扩展,存储访问可成为性能瓶颈,紧耦合与同构对称方式,2024/9/14,9,典型的紧耦合多处理机系统,2024/9/14,10,Balance同构对称多处理机系统,2024/9/14,11,分布存储多计算机,松散耦合多机系统,节点独立（可有局存、,IO,设备等）,易于扩展,多地址空间,消息传递通信界面,难于编程,2024/9/14,12,Intel Paragon系统框图,2024/9/14,13,分布共享存储多处理机,分布共享存储,DSM,D,istributed,S,hared,M,emory,将物理上分布的存储系统，通过硬件和软件的办法，向用户提供一个单一的全局地址空间,易于编程,易于扩展,2024/9/14,14,并行计算机体系结构,单指令多数据流机,SIMD,（,Single-Instruction Multiple-Data,）；,并行向量处理机,PVP,（,Parallel Vector Processor,）；,对称多处理机,SMP,（,Symmetric Multiprocessor,）；,大规模并行处理机,MPP(Massively Parallel Processor),；,工作站机群,COW(Cluster of Workstation),分布式共享存储,DSM(Distributed Shared Memory),多处理机,。,2024/9/14,15,并行计算机体系结构模型,2024/9/14,16,对称多处理机SMP(1),SMP:,采用商用微处理器，通常有片上和片外,Cache，,基于总线连接，集中式共享存储，,UMA,结构,例子：,SGI Power Challenge, DEC Alpha Server,Dawning 1,2024/9/14,17,对称多处理机SMP(2),优点,对称性,单地址空间，易编程性，动态负载平衡，无需显示数据分配,高速缓存及其一致性，数据局部性，硬件维持一致性,低通信延迟，,Load/Store,完成,问题,欠可靠，,BUS,OS,SM,通信延迟（相对于,CPU），,竞争加剧,慢速增加的带宽（,MB double/3,年,IOB,更慢）,不可扩放性-,CC-NUMA,2024/9/14,18,大规模并行机MPP,成百上千个处理器组成的大规模计算机系统，规模是变化的。,NORMA,结构，高带宽低延迟定制互连。,可扩放性：,Mem, I/O,平衡设计,系统成本：商用处理器，相对稳定的结构，,SMP,分布,通用性和可用性：不同的应用，,PVM,MPI,交互，批处理，互连对用户透明，单一系统映象，故障,通信要求,存储器和,I/O,能力,例子：,Intel Option Red,IBM SP2 Dawning 1000,2024/9/14,19,典型MPP系统特性比较,MPP,模型,Intel/Sandia ASCI Option Red,IBM SP2,SGI/Cray Origin2000,一个大型样机的配置,9072个处理器，1.8,Tflop/s(NSL),400个处理器，100,Gflop/s(MHPCC),128个处理器，51,Gflop/s(NCSA),问世日期,1996年12月,1994年9月,1996年10月,处理器类型,200,MHz, 200Mflop/s Pentium Pro,67,MHz，267Mflop/s POWER2,200,MHz，400Mflop/s MIPS R10000,节点体系结构,和数据存储器,2个处理器，32到256,MB,主存，共享磁盘,1个处理器，64,MB,到2,GB,本地主存，1,GB,到14.5,GB,本地磁盘,2个处理器，64,MB,到256,MB,分布共享主存和共享磁盘,互连网络和主存模型,分离两维网孔，,NORMA,多级网络，,NORMA,胖超立方体网络，,CC-NUMA,节点操作系统,轻量级内核（,LWK）,完全,AIX（IBM UNIX）,微内核,Cellular IRIX,自然编程机制,基于,PUMA Portals,的,MPI,MPI,和,PVM,Power C， Power Fortran,其他编程模型,Nx，PVM，HPF,HPF，Linda,MPI，PVM,2024/9/14,20,机群型大规模并行机SP2,设计策略：,机群体系结构,标准环境,标准编程模型,系统可用性,精选的单一系统映像,系统结构：,高性能开关,HPS,多级,网络,宽节点、窄节点和窄节点2,2024/9/14,21,工作站机群COW,分布式存储，,MIMD，,工作站+商用互连网络，每个节点是一个完整的计算机，有自己的磁盘和操作系统，而,MPP,中只有微内核,优点：,投资风险小,系统结构灵活,性能/价格比高,能充分利用分散的计算资源,可扩放性好,问题,通信性能,并行编程环境,例子：,Berkeley NOW，Alpha Farm, FXCOW,P/C,M,MIO,MIO,M,P/C,NIC,NIC,D,D,LAN,2024/9/14,22,典型的机群系统,典型的机群系统特点一览表,名称,系统特点,Princeton:SHRIMP,PC,商用组件，通过专用网络接口达到共享虚拟存储，支持有效通信,Karsruhe:Parastation,用于分布并行处理的有效通信网络和软件开发,Rice:TreadMarks,软件实现分布共享存储的工作站机群,Wisconsin:Wind Tunnel,在经由商用网络互连的工作站机群上实现分布共享存储,Chica,、,Maryl,、,Penns:NSCP,国家可扩放机群计划：在通过因特网互连的,3,个本地机群系统上进行元计算,Argonne:Globus,在由,ATM,连接的北美,17,个站点的,WAN,上开发元计算平台和软件,Syracuse:WWVM,使用因特网和,HPCC,技术，在世界范围的虚拟机上进行高性能计算,HKU:Pearl Cluster,研究机群在分布式多媒体和金融数字库方面的应用,Virgina:Legion,在国家虚拟计算机设施上开发元计算软件,2024/9/14,23,SMPMPP机群比较,系统特征,SMP,MPP,机群,节点数量,(,N),O(10),O(100)-O(1000),O(100),节点复杂度,中粒度或细粒度,细粒度或中粒度,中粒度或粗粒度,节点间通信,共享存储器,消息传递,或共享变量（有,DSM,时）,消息传递,节点操作系统,1,N(,微内核,),和,1,个主机,OS(,单一,),N (,希望为同构,),支持单一系统映像,永远,部分,希望,地址空间,单一,多或单一（有,DSM,时）,多个,作业调度,单一运行队列,主机上单一运行队列,协作多队列,网络协议,非标准,非标准,标准或非标准,可用性,通常较低,低到中,高可用或容错,性能,/,价格比,一般,一般,高,互连网络,总线,/,交叉开关,定制,商用,2024/9/14,24,五种结构特性一览表,属性,PVP,SMP,MPP,DSM,COW,结构类型,MIMD,MIMD,MIMD,MIMD,MIMD,处理器类型,专用定制,商用,商用,商用,商用,互连网络,定制交叉,开关,总线、交叉开关,定制网络,定制网络,商用网络,以太,ATM,通信机制,共享变量,共享变量,消息传递,共享变量,消息传递,地址空间,单地址空间,单地址空间,多地址空间,单地址空间,多地址空间,系统存储器,集中共享,集中共享,分布非共享,分布共享,分布非共享,访存模型,UMA,UMA,NORMA,NUMA,NORMA,代表机器,Cray C-90,，,Cray T-90,，,银河,1,号,IBM R50,，,SGI Power Challenge,，,曙光,1,号,Intel Paragon,，,IBMSP2,，,曙光,1000/2000,Stanford DASH,，,Cray T 3D,Berkeley NOW,，,Alpha Farm,2024/9/14,25,并行计算机访存模型,均匀存储访问模型,UMA,非,均匀存储访问模型,NUMA,全高速缓存访问模型,COMA,高速缓存一致性非均匀存储访问模型,CC-NUMA,非远程存储访问模型,NORMA,2024/9/14,26,UMA访存模型,UMA,（,Uniform Memory Access,）,模型是均匀存储访问模型的简称。其特点是：,物理存储器被所有处理器均匀共享；,所有处理器访问任何存储字取相同的时间；,每台处理器可带私有高速缓存；,外围设备也可以一定形式共享。,2024/9/14,27,NUMA访存模型,NUMA(Nonuniform Memory Access),模型是,非均匀存储访问,模型的简称。特点是：,被共享的存储器在物理上是分布在所有的处理器中的，其所有本地存储器的集合就组成了全局地址空间；,处理器访问存储器的时间是不一样的；访问本地存储器,LM,或群内共享存储器,CSM,较快，而访问外地的存储器或全局共享存储器,GSM,较慢,(,此即非均匀存储访问名称的由来,),；,每台处理器照例可带私有高速缓存，外设也可以某种形式共享。,LM,1,P,1,LM,2,P,2,LM,n,P,n,互,连,网,络,(,a),共享本地存储模型,全局互连网络,(,b),层次式机群模型,GSM,GSM,GSM,P,C,I,N,CSM,P,P,CSM,CSM,群1,P,C,I,N,CSM,群,N,P,P,CSM,CSM,2024/9/14,28,COMA访存模型,COMA(Cache-Only Memory Access),模型是,全高速缓存存储访问,的简称。其特点是：,各处理器节点中没有存储层次结构，全部高速缓存组成了全局地址空间；,利用分布的高速缓存目录,D,进行远程高速缓存的访问;,COMA,中的高速缓存容量一般都大于,2,级高速缓存容量；,使用,COMA,时，数据开始时可任意分配，因为在运行时它最终会被迁移到要用到它们的地方。,2024/9/14,29,CC-NUMA访存模型,CC-NUMA,（,Coherent-Cache Nonuniform Memory Access,）,模型是,高速缓存一致性非均匀存储访问,模型的简称。其特点是：,大多数使用基于目录的高速缓存一致性协议；,保留,SMP,结构易于编程的优点，也改善常规,SMP,的可扩放性；,CC-NUMA,实际上是一个分布共享存储的,DSM,多处理机系统；,它最显著的优点是程序员无需明确地在节点上分配数据，系统的硬件和软件开始时自动在各节点分配数据，在运行期间，高速缓存一致性硬件会自动地将数据迁移至要用到它的地方。,2024/9/14,30,NORMA访存模型,NORMA（No-Remote Memory Access）,模型是,非远程存储访问,模型的简称。,NORMA,的特点是：,所有存储器是私有的；,绝大数,NUMA,都不支持远程存储器的访问；,在,DSM,中，,NORMA,就消失了。,2024/9/14,31,构筑并行机系统的不同存储结构,2024/9/14,32,分布式存储中的共享与非共享存储,在并行计算机中，一个物理上分布的存储器在逻辑上可以被共享与非共享。,如果系统内任何处理器上的进程都能直接地访问系统内任何本地存储器和远程存储器，则就称该系统具有共享存储结构。注意，所谓直接访问系指能用load和store之类的指令存取整个系统内的任何存储单元。,如果系统内任何处理器上的进程不能直接对远程存储器用load和store之类的指令进行访问，而必须借助于运行时软件层和用户可调用的例程库来实现，则就称该系统具有非共享存储结构。,2024/9/14,33,分布存储中四种不同的远程访问,2024/9/14,34,五种分布存储结构的特性比较,特性,NORMA,NCC-NUMA,SC-NUMA,CC-NUMA,COMA,共享单位（粒度）,变量,变量,页,页,/,高速缓存行,高速缓存行,一致性维护,由用户应用实现,由用户级软件实现,由,OS,或运行时系统实现,在高速缓存行级由硬件实现,在高速缓存行级由硬件实现,复制和迁移的实现,由用户在变量级实现,由用户在变量级实现,由,OS,或运行时系统在页面级实现,由,OS,在页面级实现,由硬件在高速缓存行级实现,假共享现象,无,无,有,有,有,2024/9/14,35,