体系结构和并行基础课件

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

2、A(Cache-Coherent0一致性高速缓存非均匀存储访问模型), NORMA（No-Romate Memory Access 非远程存储访问模型）结构模型共享内存/对称多处理机系统(SMP) PVP：并行向量机 单地址空间 共享存储 UMA( Uniform Memory Access) SMP：共享内存并行机（ Shared Memory Processors ）。多个处理器通过交叉开关（Crossbar）或总线与共享内存互连。任意处理器可直接访问任意内存地址,且访问延迟、带宽、几率都是等价的; 系统是对称的；单地址空间 、共享存储、UMA；并行编程方式: 通常采用OpenMP, 也可

3、使用消息传递(MPI/PVM) 及HPF。SGI Power Challenge , Dawning 1 *5MPP：大规模并行计算机系统 MPP:大规模并行计算机系统(Massively Parallel Processors)。由大量具有局部内存的计算结点通过高速系统网络联接而构成的并行处理系统. MPP 系统的系统网络通常具有某种拓扑结构(如tree, mesh, torus, hypercube).物理和逻辑上均是分布内存采用高通信带宽和低延迟的互联网络 (专门设计和定制的)NORMA或CC-NUMA代表:CRAY T3E(2048), ASCI Red(3072), IBM SP2,

4、 曙光1000*6DSM：分布共享存储多处理机系统 DSM： 分布共享存贮并行机（Distributed Shared Memory），由结点（一般是SMP系统）通过高速消息传递网络互连而成。存贮系统在物理上分布、逻辑上共享。各结点有自己独立的寻址空间。单地址空间 、分布共享NUMA（ Nonuniform Memory Access ）与SMP的主要区别：DSM在物理上有分布在各个节点的局部内存从而形成一个共享的存储器；代表: SGI Origin 2000, Cray T3D *7Cluster：机群系统Cluster(Now,Cow)： 群集系统。将单个节点，用商业网络 ：Etherne

5、t，Myrinet，Quadrics，Infiniband，Switch等连结起来形成群集系统。 每个节点都是一个完整的计算机（SMP或DSM），有自己磁盘和操作系统各个节点通过高性能网络相互连接网络接口和I/O总线松耦合连接每个节点有完整的操作系统多地址空间、分布非共享、NORMA通用性、可扩展性好，性价比高*8访存模型 *9UMANORMANUMA:多处理机（单地址空间共享存储器） UMA: Uniform Memory Access NUMA: Nonuniform Memory Access多计算机（多地址空间非共享存储器） NORMA:No-Remote Memory Access最

6、新的TOP500计算机*10*11最新的TOP500计算机 来自Cray的美洲豹“Jaguar”，凭借1.75 PFlop/s(每秒1750万亿次)的计算能力傲视群雄。“Jaguar”采用了224162个处理器核心来自中国的曙光“星云”系统以1271万亿次/s的峰值速度名列第二采用了自主设计的HPP体系结构、高效异构协同计算技术处理器是32nm工艺的六核至强X5650，并且采用了Nvidia Tesla C2050 GPU做协处理的用户编程环境；异构体系结构 专用 通用 TOP500中85%的系统采用了四核处理器，而有5%的系统已经使用了六核或者更多核的处理器。 *12并行编程基础*13并行计

7、算软件环境操作系统：UNIX、LINUX等 通信库：MPI 、PVM数学库：如MKL，ScaLAPACK等编译器：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+ Compiler）、Fortran77/90/95（ifc： Intel Fortran Compiler)支持多线程和OpenMP14并行程序设计

8、方法隐式并行程序设计：常用传统的语言编程成顺序源编码，把“并行”交给编译器实现自动并行程序的自动并行化是一个理想目标，存在难以克服的困难语言容易，编译器难显式并行程序设计：在用户程序中出现“并行”的调度语句显式并行是目前有效的并行程序设计方法。例如通过消息传递方式或多线程等语言难，编译器容易*15并行程序编程模型隐式并行（Implicit Parallel）数据并行（Data Parallel）共享变量（Shared Variable）消息传递（Message Passing）*16隐式并行(Implicit Parallel)概况：程序员用熟悉的串行语言编写相应的串行程序通过编译器和运行支持

9、系统将串行程序自动转化为并行代码特点：语义简单可移植性好单线程，易于调试和验证正确性细粒度并行效率很低*17数据并行（Data Parallel）概况：SIMD的自然模型局部计算和数据选路操作例：HPF特点：单线程并行操作于聚合数据结构（数组）松散同步单一地址空间隐式交互作用显式数据分布优点:编程相对简单,串并行程序一致.缺点:程序的性能在很大程度上依赖于所用的编译系统及用户对编译系统的了解. 并行粒度局限于数据级并行,粒度较小.18共享变量(Shared Variable)概况：PVP, SMP, DSM的自然模型特点：多线程：SPMD, MPMD异步单一地址空间显式同步隐式数据分布隐式通信

10、典型代表：OpenMP19消息传递(Message Passing）概况：MPP、COW的自然模型特点：多进程异步并行多地址空间显式同步显式数据映射和负载分配显式通信典型代表MPI、PVM20并行编程模型标准所有并行编程模型标准可分为以下三类:数据并行HPF, Fortran90用于SMP, DSM共享编程OpenMP用于SMP, DSM消息传递MPI, PVM用于所有并行计算机三者可混合使用:如对以SMP为节点的Cluster来说, 可以在节点间进行消息传递,在节点内进行共享变量编程.21基本并行化方法相并行（Phase Parallel）流水线并行（Pipeline Parallel）主从

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

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