体系结构与并行基础

体系结构与并行基础 赵永华中科院计算机网络信息中心超级计算中心yhzhao 02 54 2 并行机体系结构 并行计算机系统结构分类 02 54 3 Flynn分类 instruction datastream SISD 单指令单数据 SIMD 单指令多数据 MIMD MISD结构模型分类 PVP 并行向量机 SMP 共享内存 MPP 大规模并行计算机 DSM 分布共享内存 COW 集群 访存模型分类 UMA UniformMemory access 均匀存储访问模型 NUMA non UMA COMA Cache OnlyMemoryArchitecture 全高速缓存内存体系结构 CC NUMA Cache Coherent0一致性高速缓存非均匀存储访问模型 NORMA No RomateMemoryAccess非远程存储访问模型 结构模型 共享内存 对称多处理机系统 SMP PVP 并行向量机单地址空间共享存储UMA UniformMemoryAccess SMP 共享内存并行机 SharedMemoryProcessors 多个处理器通过交叉开关 Crossbar 或总线与共享内存互连 任意处理器可直接访问任意内存地址 且访问延迟 带宽 几率都是等价的 系统是对称的 单地址空间 共享存储 UMA 并行编程方式 通常采用OpenMP 也可使用消息传递 MPI PVM 及HPF SGIPowerChallenge Dawning1 02 54 5 MPP 大规模并行计算机系统 MPP 大规模并行计算机系统 MassivelyParallelProcessors 由大量具有局部内存的计算结点通过高速系统网络联接而构成的并行处理系统 MPP系统的系统网络通常具有某种拓扑结构 如tree mesh torus hypercube 物理和逻辑上均是分布内存采用高通信带宽和低延迟的互联网络 专门设计和定制的 NORMA或CC NUMA代表 CRAYT3E 2048 ASCIRed 3072 IBMSP2 曙光1000 02 54 6 DSM 分布共享存储多处理机系统 DSM 分布共享存贮并行机 DistributedSharedMemory 由结点 一般是SMP系统 通过高速消息传递网络互连而成 存贮系统在物理上分布 逻辑上共享 各结点有自己独立的寻址空间 单地址空间 分布共享NUMA NonuniformMemoryAccess 与SMP的主要区别 DSM在物理上有分布在各个节点的局部内存从而形成一个共享的存储器 代表 SGIOrigin2000 CrayT3D 02 54 7 Cluster 机群系统 Cluster Now Cow 群集系统 将单个节点 用商业网络 Ethernet Myrinet Quadrics Infiniband Switch等连结起来形成群集系统 每个节点都是一个完整的计算机 SMP或DSM 有自己磁盘和操作系统各个节点通过高性能网络相互连接网络接口和I O总线松耦合连接每个节点有完整的操作系统多地址空间 分布非共享 NORMA通用性 可扩展性好 性价比高 02 54 8 访存模型 02 54 9 UMA NORMA NUMA 多处理机 单地址空间共享存储器 UMA UniformMemoryAccessNUMA NonuniformMemoryAccess多计算机 多地址空间非共享存储器 NORMA No RemoteMemoryAccess 最新的TOP500计算机 02 54 10 02 54 11 最新的TOP500计算机 来自Cray的美洲豹 Jaguar 凭借1 75PFlop s 每秒1750万亿次 的计算能力傲视群雄 Jaguar 采用了224162个处理器核心来自中国的曙光 星云 系统以1271万亿次 s的峰值速度名列第二采用了自主设计的HPP体系结构 高效异构协同计算技术处理器是32nm工艺的六核至强X5650 并且采用了NvidiaTeslaC2050GPU做协处理的用户编程环境 异构体系结构专用通用TOP500中85 的系统采用了四核处理器 而有5 的系统已经使用了六核或者更多核的处理器 02 54 12 并行编程基础 02 54 13 并行计算软件环境 操作系统 UNIX LINUX等通信库 MPI PVM数学库 如MKL ScaLAPACK等编译器 GNUCompiler自由软件 持C C Fortran77等语言高性能计算中常用的 C C GCC GNUC C Compiler Fortran gfortran IntelCompiler由Intel公司针对Intel处理器开发 支持Linux Windows支持C C icc mpicc IntelC C Compiler Fortran77 90 95 ifc IntelFortranCompiler 支持多线程和OpenMP 14 并行程序设计方法 隐式并行程序设计 常用传统的语言编程成顺序源编码 把 并行 交给编译器实现自动并行程序的自动并行化是一个理想目标 存在难以克服的困难语言容易 编译器难显式并行程序设计 在用户程序中出现 并行 的调度语句显式并行是目前有效的并行程序设计方法 例如通过消息传递方式或多线程等语言难 编译器容易 02 54 15 并行程序编程模型 隐式并行 ImplicitParallel 数据并行 DataParallel 共享变量 SharedVariable 消息传递 MessagePassing 02 54 16 隐式并行 ImplicitParallel 概况 程序员用熟悉的串行语言编写相应的串行程序通过编译器和运行支持系统将串行程序自动转化为并行代码特点 语义简单可移植性好单线程 易于调试和验证正确性细粒度并行效率很低 02 54 17 数据并行 DataParallel 概况 SIMD的自然模型局部计算和数据选路操作例 HPF特点 单线程并行操作于聚合数据结构 数组 松散同步单一地址空间隐式交互作用显式数据分布优点 编程相对简单 串并行程序一致 缺点 程序的性能在很大程度上依赖于所用的编译系统及用户对编译系统的了解 并行粒度局限于数据级并行 粒度较小 18 共享变量 SharedVariable 概况 PVP SMP DSM的自然模型特点 多线程 SPMD MPMD异步单一地址空间显式同步隐式数据分布隐式通信典型代表 OpenMP 19 消息传递 MessagePassing 概况 MPP COW的自然模型特点 多进程异步并行多地址空间显式同步显式数据映射和负载分配显式通信典型代表MPI PVM 20 并行编程模型标准 所有并行编程模型标准可分为以下三类 数据并行HPF Fortran90用于SMP DSM共享编程OpenMP用于SMP DSM消息传递MPI PVM用于所有并行计算机三者可混合使用 如对以SMP为节点的Cluster来说 可以在节点间进行消息传递 在节点内进行共享变量编程 21 基本并行化方法 相并行 PhaseParallel 流水线并行 PipelineParallel 主从并行 Master SlaveParallel 分治并行 DivideandConquerParallel 工作池并行 WorkPoolParallel 02 54 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 WpS 加速比S 穿行并行时间f 串行分量的比率f Ws W 02 54 23 可扩展性与评测标准 一 可扩展性 Scalability 确定的应用背景下 计算系统 算法或程序等 的性能随着处理器的数目的增加而按比例提高的能力总是将并行算法和体系结构一并考虑算法的可扩放性 该算法针对某一特定机器的可扩放性体系结构的可扩放性 该体系结构的机器的某一并行算法的可扩放性一般情况下 增加处理器数 会增加额外开销和降低处理器利用率 所以对于一个特定的并行系统 并行算法或并行程序 它们能否有效的利用不断增加的处理器的能力应是受限的目的 确定某类问题用哪种并行算法与哪种并行体系结构结合 根据在小规模机器上的运行性能 预测在大规模机器上的性能对固定的问题规模 确定最有效的处理机数和加速比指导改进算法 体系结构 以利用可扩充的大量处理器 02 54 24 可扩展性与评测标准 二 等效率度量标准 若问题规模w不变 随着处理器数P的增加会导致开销To随之增加 效率E下降 为了保持E不变 则在增加p的同时相应的增加问题规模W 以抵消由于p增加而导致的To的增加 从而保持效率不变随着系统规模的增加 处理器数目的增加 测量增加多少运算量会保持效率不变增加越少表明可扩放性越好E 1 1