体系结构与并行基础

1、体系结构与并行基础赵永华中科院计算机网络信息中心超级计算中心11:052 并行机体系结构并行机体系结构并行计算机系统结构分类11:053n Flynn分类：（instruction/data stream ）SISD（单指令单数据）,SIMD（单指令多数据）, MIMD, MISDn 结构模型分类：PVP（并行向量机）, SMP（共享内存）,MPP（大规模并行计算机）,DSM（分布共享内存）,COW（集群）n 访存模型分类：UMA(Uniform Memory-access，均匀存储访问模型) NUMA(non-UMA）COMA（Cache-Only Memory Architecture，全

2、高速缓存内存体系结构） CC-NUMA(Cache-Coherent0一致性高速缓存非均匀存储访问模型), NORMA（No-Romate Memory Access 非远程存储访问模型）结构模型共享内存/对称多处理机系统(SMP)n PVPPVP：并行向量机：并行向量机 单地址空间单地址空间 共享存储共享存储 UMA(UMA( Uniform Memory AccessUniform Memory Access) )n SMPSMP：共享内存并行机（：共享内存并行机（ Shared Memory Shared Memory Processors Processors ）。多个处理器通过交叉开

3、关）。多个处理器通过交叉开关（CrossbarCrossbar）或总线与共享内存互连。）或总线与共享内存互连。任意处理器可直接访问任意内存地址任意处理器可直接访问任意内存地址, ,且访问且访问延迟、带宽、几率都是等价的延迟、带宽、几率都是等价的; ; 系统是对称的；系统是对称的；单地址空间单地址空间 、共享存储、共享存储、UMAUMA；并行编程方式并行编程方式: : 通常采用通常采用OpenMP, OpenMP, 也可使用消也可使用消息传递息传递(MPI/PVM) (MPI/PVM) 及及HPFHPF。SGISGI Power Challenge , Dawning 1 Power Chall

4、enge , Dawning 1 11:055MPP：大规模并行计算机系统n MPP:MPP:大规模并行计算机系统大规模并行计算机系统(Massively (Massively Parallel Processors)Parallel Processors)。由大量具有局部内由大量具有局部内存的计算结点通过高速系统网络联接而存的计算结点通过高速系统网络联接而构成的并行处理系统构成的并行处理系统. . MPP MPP 系统的系统网络通常具有某种拓扑系统的系统网络通常具有某种拓扑结构结构( (如如tree, mesh, torus, hypercube).tree, mesh, torus, hy

5、percube).物理和逻辑上均是分布内存物理和逻辑上均是分布内存采用高通信带宽和低延迟的互联网络采用高通信带宽和低延迟的互联网络 ( (专专门设计和定制的门设计和定制的) )NORMANORMA或或CC-NUMACC-NUMA代表代表:CRAY T3E(2048), ASCI Red(3072), :CRAY T3E(2048), ASCI Red(3072), IBM SP2, IBM SP2, 曙光曙光1000100011:056DSM：分布共享存储多处理机系统n DSMDSM： 分布共享存贮并行机（分布共享存贮并行机（Distributed Distributed Shared Mem

6、oryShared Memory），由结点（一般是），由结点（一般是SMPSMP系系统）通过高速消息传递网络互连而成。存贮统）通过高速消息传递网络互连而成。存贮系统在物理上分布、逻辑上共享。各结点有系统在物理上分布、逻辑上共享。各结点有自己独立的寻址空间。自己独立的寻址空间。单地址空间单地址空间 、分布共享、分布共享NUMANUMA（ NonuniformNonuniform Memory Access Memory Access ）与与SMPSMP的主要区别：的主要区别：DSMDSM在物理上有分布在各在物理上有分布在各个节点的局部内存从而形成一个共享的存储个节点的局部内存从而形成一个共享的存

7、储器；器；代表代表: SGI Origin 2000, Cray T3D: SGI Origin 2000, Cray T3D 11:057Cluster：机群系统nCluster(Now,Cow)Cluster(Now,Cow)： 群集系统。将单个节点，用商业网群集系统。将单个节点，用商业网络络 ：EthernetEthernet，MyrinetMyrinet，QuadricsQuadrics，InfinibandInfiniband，SwitchSwitch等连结起来形成群等连结起来形成群集系统。集系统。 每个节点都是一个完整的计算机每个节点都是一个完整的计算机（SMPSMP或或DSMDS

8、M），有自己磁盘和操），有自己磁盘和操作系统作系统各个节点通过高性能网络相互连接各个节点通过高性能网络相互连接网络接口和网络接口和I/OI/O总线松耦合连接总线松耦合连接每个节点有完整的操作系统每个节点有完整的操作系统多地址空间、分布非共享、多地址空间、分布非共享、NORMANORMA通用性、可扩展性好，性价比高通用性、可扩展性好，性价比高11:058访存模型 11:059UMANORMANUMA:多处理机（单地址空间共享存储器）多处理机（单地址空间共享存储器） UMA: Uniform Memory Access NUMA: Nonuniform Memory Access多计算机（多地址空

9、间非共享存储器）多计算机（多地址空间非共享存储器） NORMA:No-Remote Memory Access最新的TOP500计算机11:051011:0511最新的TOP500计算机 来自Cray的美洲豹“Jaguar”，凭借1.75 PFlop/s(每秒1750万亿次)的计算能力傲视群雄。“Jaguar”采用了224162个处理器核心来自中国的曙光“星云”系统以1271万亿次/s的峰值速度名列第二采用了自主设计的HPP体系结构、高效异构协同计算技术处理器是32nm工艺的六核至强X5650，并且采用了Nvidia Tesla C2050 GPU做协处理的用户编程环境；异构体系结构 专用 通

10、用 TOP500中85%的系统采用了四核处理器，而有5%的系统已经使用了六核或者更多核的处理器。 11:0512并行编程基础11:0513并行计算软件环境n操作系统：UNIX、LINUX等 n通信库：MPI 、PVMn数学库：如MKL，ScaLAPACK等n编译器：GNU Compiler自由软件，持C/C+、Fortran77等语言高性能计算中常用的：C/C+：GCC (GNU C/C+ Compiler)Fortran ：gfortran;Intel Compiler由Intel公司针对Intel处理器开发,支持Linux、Windows支持C/C+（icc，mpicc：Intel C/C

11、+ Compiler）、Fortran77/90/95（ifc： Intel Fortran Compiler)支持多线程和OpenMP14并行程序设计方法n隐式并行程序设计：隐式并行程序设计：常用传统的语言编程成顺序源编码，把“并行”交给编译器实现自动并行程序的自动并行化是一个理想目标，存在难以克服的困难语言容易，编译器难n显式并行程序设计：显式并行程序设计：在用户程序中出现“并行”的调度语句显式并行是目前有效的并行程序设计方法。例如通过消息传递方式或多线程等语言难，编译器容易11:0515并行程序编程模型n隐式并行（Implicit Parallel）n数据并行（Data Parallel

12、）n共享变量（Shared Variable）n消息传递（Message Passing）11:0516隐式并行(Implicit Parallel)n概况：概况：程序员用熟悉的串行语言编写相应的串行程序通过编译器和运行支持系统将串行程序自动转化为并行代码n特点：特点：语义简单可移植性好单线程，易于调试和验证正确性细粒度并行效率很低11:0517数据并行（Data Parallel）n概况：概况：SIMD的自然模型局部计算和数据选路操作例：HPFn特点：特点：单线程并行操作于聚合数据结构（数组）松散同步单一地址空间隐式交互作用显式数据分布n优点优点:编程相对简单,串并行程序一致.n缺点缺点:程

13、序的性能在很大程度上依赖于所用的编译系统及用户对编译系统的了解. 并行粒度局限于数据级并行,粒度较小.18共享变量(Shared Variable)概况：PVP, SMP, DSM的自然模型特点：多线程：SPMD, MPMD异步单一地址空间显式同步隐式数据分布隐式通信典型代表：OpenMP19消息传递(Message Passing）概况：MPP、COW的自然模型特点：多进程异步并行多地址空间显式同步显式数据映射和负载分配显式通信典型代表MPI、PVM20并行编程模型标准n所有并行编程模型标准可分为以下三类所有并行编程模型标准可分为以下三类:u数据并行HPF, Fortran90用于SMP,

14、DSMu共享编程OpenMP用于SMP, DSMu消息传递MPI, PVM用于所有并行计算机n三者可混合使用三者可混合使用:u如对以SMP为节点的Cluster来说, 可以在节点间进行消息传递,在节点内进行共享变量编程.21基本并行化方法n相并行（相并行（Phase ParallelPhase Parallel）n流水线并行（流水线并行（Pipeline ParallelPipeline Parallel）n主从并行（主从并行（Master-Slave ParallelMaster-Slave Parallel）n分治并行（分治并行（Divide and Conquer ParallelDiv

15、ide and Conquer Parallel）n工作池并行（工作池并行（Work Pool ParallelWork Pool Parallel）11:0522加速比性能定律 并行系统的加速比简单的说就是指对于一个给定的应用，并行算法或并行程序的执行速度相对于串行算法或串行程序的执行速度加快了多少倍（既Sp=T1/Tp）三种加速比性能定律：Amdahl定律：适用固定计算负载 S=（Ws+Wp）/（Ws+Wp/p）Gustafson定律：适用于可扩放问题 S=（Ws+pWp）/（Ws+Wp）Sun和Ni定律：受限于存储器 其中： P ： 处理器数 W ：问题规模 Ws：问题中的串行分量 Wp

16、：并行分量 WWsWp S ：加速比 S=穿行并行时间 f：串行分量的比率 fWs/W11:0523可扩展性与评测标准（一）n可扩展性(Scalability): 确定的应用背景下，计算系统(算法或程序等)的性能随着处理器的数目的增加而按比例提高的能力n总是将并行算法和体系结构一并考虑算法的可扩放性: 该算法针对某一特定机器的可扩放性体系结构的可扩放性: 该体系结构的机器的某一并行算法的可扩放性n一般情况下，增加处理器数，会增加额外开销和降低处理器利用率；所以对于一个特定的并行系统、并行算法或并行程序，它们能否有效的利用不断增加的处理器的能力应是受限的n目的：确定某类问题用哪种并行算法与哪种并行体系结构结合。根据在小规模机器上的运行性能，预测在大规模机器上的性能对固定的问题规模，确定最有效的处理机数和加速比指导改进算法、体系结构，以利用可扩充的大量处理器11:0524可扩展性与评测标准（二）等效率度量标准: 若问题规模w不变，随着处理器数P的增加会导致开销To随之增加，效率E下降。为了保持E不变，则在增加p的同时相应的增加问题规模W，以抵消由于p增加而导致的T