体系结构与并行基础

体系结构与并行基础赵永华中科院计算机网络信息中心超级计算中心yhzhao@*2 并行机体系结构并行机体系结构并行计算机系统结构分类*3n 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，全高速缓存内存体系结构） 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 ）。

多个处理器通过交叉开关）多个处理器通过交叉开关（（CrossbarCrossbar）或总线与共享内存互连或总线与共享内存互连•任任意意处处理理器器可可直直接接访访问问任任意意内内存存地地址址, ,且且访访问问延迟、带宽、几率都是等价的延迟、带宽、几率都是等价的; ;• 系统是对称的；系统是对称的；•单地址空间单地址空间 、共享存储、、共享存储、UMAUMA；；•并行编程方式并行编程方式: : 通常采用通常采用OpenMP, OpenMP, 也可使用消也可使用消息传递息传递(MPI/PVM) (MPI/PVM) 及及HPFHPF•SGISGI Power Challenge , Dawning 1 Power Challenge , Dawning 1 *5MPP：大规模并行计算机系统n MPP:MPP:大规模并行计算机系统大规模并行计算机系统(Massively￿Parallel￿Processors)(Massively￿Parallel￿Processors)由大量具由大量具有局部内存的计算结点通过高速系统网有局部内存的计算结点通过高速系统网络联接而构成的并行处理系统络联接而构成的并行处理系统. .•￿ ￿MPP￿MPP￿系统的系统网络通常具有某种拓扑系统的系统网络通常具有某种拓扑结构结构( (如如tree,￿mesh,￿torus,￿hypercube).tree,￿mesh,￿torus,￿hypercube).•物理和逻辑上均是分布内存物理和逻辑上均是分布内存•采采用用高高通通信信带带宽宽和和低低延延迟迟的的互互联联网网络络￿ ￿( (专专门设计和定制的门设计和定制的) )•NORMANORMA或或CC-NUMACC-NUMA•代代表表:CRAY￿:CRAY￿ T3E(2048),￿T3E(2048),￿ ASCI￿ASCI￿ Red(3072),￿Red(3072),￿IBM￿SP2,￿IBM￿SP2,￿曙光曙光10001000*6DSM：分布共享存储多处理机系统n DSMDSM：： 分布共享存贮并行机（分布共享存贮并行机（Distributed Shared Distributed Shared MemoryMemory），由结点（一般是），由结点（一般是SMPSMP系统）通过系统）通过高速消息传递网络互连而成。

存贮系统在物高速消息传递网络互连而成存贮系统在物理上分布、逻辑上共享各结点有自己独立理上分布、逻辑上共享各结点有自己独立的寻址空间的寻址空间•单地址空间单地址空间 、分布共享、分布共享•NUMANUMA（（ Nonuniform Memory AccessNonuniform Memory Access ））•与与SMPSMP的主要区别：的主要区别：DSMDSM在物理上有分布在各在物理上有分布在各个节点的局部内存从而形成一个共享的存储个节点的局部内存从而形成一个共享的存储器；器；•代表代表: SGI Origin 2000, Cray T3D: SGI Origin 2000, Cray T3D *7Cluster：机群系统nCluster(Now,Cow)Cluster(Now,Cow)：： 群群集集系系统统将将单单个个节节点点，，用用商商业业网网 络络 ：： EthernetEthernet，， MyrinetMyrinet，，QuadricsQuadrics，， InfinibandInfiniband，， SwitchSwitch等等连结起来形成群集系统。

连结起来形成群集系统 •每个节点都是一个完整的计算机每个节点都是一个完整的计算机（（SMPSMP或或DSMDSM），有自己磁盘和操作），有自己磁盘和操作系统系统•各个节点通过高性能网络相互连接各个节点通过高性能网络相互连接•网络接口和网络接口和I/OI/O总线松耦合连接总线松耦合连接•每个节点有完整的操作系统每个节点有完整的操作系统•多地址空间、分布非共享、多地址空间、分布非共享、NORMANORMA•通用性、可扩展性好，性价比高通用性、可扩展性好，性价比高*8访存模型￿*9UMANORMANUMA:多处理机（单地址空间共享存储器）多处理机（单地址空间共享存储器） UMA: Uniform Memory Access NUMA: Nonuniform Memory Access多计算机（多地址空间非共享存储器）多计算机（多地址空间非共享存储器） NORMA:No-Remote Memory Access最新的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并行计算软件环境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++ Compiler）、Fortran77/90/95（ifc：￿Intel Fortran Compiler)³支持多线程和OpenMP14并行程序设计方法n隐式并行程序式并行程序设计：：•常用传统的语言编程成顺序源编码，把“并行”交给编译器实现自动并行•程序的自动并行化是一个理想目标，存在难以克服的困难•语言容易，编译器难n显式并行程序式并行程序设计：：•在用户程序中出现“并行”的调度语句•显式并行是目前有效的并行程序设计方法。

例如通过消息传递方式或多线程等•语言难，编译器容易*15并行程序编程模型n隐式并行（Implicit Parallel）n数据并行（Data Parallel）n共享变量（Shared Variable）n消息传递（Message Passing）*16隐式并行(Implicit Parallel)n概况：概况：•程序员用熟悉的串行语言编写相应的串行程序•通过编译器和运行支持系统将串行程序自动转化为并行代码n特点：特点：•语义简单•可移植性好•单线程，易于调试和验证正确性•细粒度并行•效率很低*17数据并行（Data Parallel）n概况：概况：•SIMD的自然模型•局部计算和数据选路操作•例：HPFn特点：特点：•单线程•并行操作于聚合数据结构（数组）•松散同步•单一地址空间•隐式交互作用•显式数据分布n优点点:编程相对简单,串并行程序一致.n缺点缺点:程序的性能在很大程度上依赖于所用的编译系统及用户对编译系统的了解. 并行粒度局限于数据级并行,粒度较小.18共享变量(Shared Variable)概况：³PVP, SMP, DSM的自然模型特点：³多线程：SPMD, MPMD³异步³单一地址空间³显式同步³隐式数据分布³隐式通信典型代表：³OpenMP19消息传递(Message Passing）概况：³MPP、COW的自然模型特点：³多进程异步并行³多地址空间³显式同步³显式数据映射和负载分配³显式通信典型代表³MPI、PVM20并行编程模型标准n所有并行所有并行编程模型程模型标准可分准可分为以下三以下三类:u数据并行•HPF, Fortran90•用于SMP, 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 Divide and Conquer ParallelParallel））n工作池并行（工作池并行（Work Pool ParallelWork Pool Parallel））*22加速比性能定律￿￿￿￿￿￿￿￿￿并行系统的加速比简单的说就是指对于一个给定的应用，并行算法或并行程序的执行速度相对于串行算法或串行程序的执行速度加快了多少倍（既Sp=T1/Tp）三种加速比性能定律：³Amdahl定律：适用固定计算负载￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿S=（Ws+Wp）/（Ws+Wp/p）³Gustafson定律：适用于可扩放问题￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿S=（Ws+pWp）/（Ws+Wp）³Sun和Ni定律：受限于存储器￿￿￿￿￿￿其中：￿￿￿P ：￿处理器数￿￿￿￿￿￿￿￿￿￿￿￿W ：问题规模￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿Ws：问题中的串行分量￿￿Wp：并行分量 ￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿W＝Ws＋Wp ￿￿￿￿S ：加速比￿￿￿S=穿行并行时间￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿f：串行分量的比率￿￿f＝Ws/W*23可扩展性与评测标准（一）n可扩展性(Scalability): 确定的应用背景下，计算系统(算法或程序等)的性能随着处理器的数目的增加而按比例提高的能力n总是将并行算法和体系结构一并考虑•算法的可扩放性: 该算法针对某一特定机器的可扩放性•体系结构的可扩放性: 该体系结构的机器的某一并行算法的可扩放性n一般情况下，增加处理器数，会增加额外开销和降低处理器利用率；所以对于一个特定的并行系统、并行算法或并行程序，它们能否有效的利用不断增加的处理器的能力应是受限的n目的：•确定某类问题用哪种并行算法与哪种并行体系结构结合。

•根据在小规模机器上的运行性能，预测在大规模机器上的性能•对固定的问题规模，确定最有效的处理机数和加速比•指导改进算法、体系结构，以利用可扩充的大量处理器*24可扩展性与评测标准（二）等效率度量标准: ³若问题规模w不变，随着处理器数P的增加会导致开销To随之增加，效率E下降为了保持E不变，则在增加p的同时相应的增加问题规模W，以抵消由于p增加而导致的To的增加，从而保持效率不变³随着系统规模的增加(处理器数目的增加) ，测量增加多少运算量会保持效率不变³增加越少表明可扩放性越好³E＝1/(1+To/W) ￿￿￿￿￿To: 额外开销时间之和*25可扩展性与评测标准（三）等速度度量标准³系统规模增加时，若保持平均速度(每个处理器的速度)不变，每个处理器增加浮点操作的量³速度常以每秒多少次浮点运算(Flops)来表示等计算时间/通信开销比率度量标准³系统规模增加时，保持计/通信比不变所需要增加的问题规模计算时间/通信开销比率³并行计算时间与系统开销之比*26谢谢大家！*27。