2.1与2.2 并行计算机系统结构模型与并行计算机性能测评_软件学院_徐悦甡_第二部分

Size: px

Start display at page:

Download "2.1与2.2 并行计算机系统结构模型与并行计算机性能测评_软件学院_徐悦甡_第二部分"

初杏斡史
5 years ago
Views:

1 并行计算 :Parallel Computing 结构编程算法应用 2.1 并行计算机系统结构模型 ( 第二部分 ) 徐悦甡 (Yueshen Xu) ysxu@xidian.edu.cn 软件工程系西安电子科技大学

2 上机安排上机时间 ( 四次,16 学时 ) 按周数 : 第周的星期三按日期 :5 月 16 号,5 月 23 号,6 月 6 号,6 月 27 号全部为星期三晚上,18:30 至 21:30, 每次三个小时地点 :G 楼机房内容 ( 视课程情况可能微调 ) 第一次 (5.16):Java 并发第二次 (5.23):Java 并行第三次 (6.6):Python 并发与并行第四次 (6.27):MapReduce 单机并行

3 上机安排星期三晚上 6 点半开始, 至 9 点半结束

4 本节提纲并行计算机访存模型均匀存储访问与非均匀存储访问高速缓存存储访问非远程存储访问模型等体系结构与访存模型的关系并行计算机性能测评并行计算机的基本性能指标加速比性能测评可扩展性性能测评从存储器的角度讨论一部分 2

5 上节课回顾并行计算机体系结构模型汇总各实现形式比对 VP VP VP P/C P/C P/C MB P/C MB P/C 交叉开关总线或交叉开关 LM LM SM SM SM SM SM I/O NIC NIC PVP SMP 定制网络 MB P/C MB P/C MB P/C MB P/C MPP LM LM M M DIR DIR Bridge Bridge NIC NIC LD IOB NIC LD IOB NIC 定制网络 DSM 商品网络 ( 以太网,ATM,etc.) COW 5

6 并行计算机体系结构汇总各并行计算机结构特性 ( 比较 ) 属性 SIMD PVP SMP MPP DSM COW 同构性 SIMD MIMD MIMD MIMD MIMD MIMD 同步性指令级同步异步或弱同步异步或弱同步异步或弱同步异步或弱同步异步或弱同步通信机制数据并行共享变量共享变量消息传递共享变量消息传递地址空间单空间单空间单空间多空间单空间多空间访存模型 UMA UMA UMA NORMA NUMA NORMA 互连网络定制交叉开关总线或交叉开关定制定制商用 6

7 并行计算机访存模型常见的并行计算机访存模型 vs. 体系结构 UMA(Uniform Memory Access), 均匀存储访问模型 NUMA(Non-uniform Memory Access), 非均匀存储访问模型五种常见的并行计算机访存模型 COMA(Cache-Only Memory Access), 全高速缓存存储访问 CC-NUMA(Coherent-Cache Nonuniform Memory Access), 高速缓存一致性非均匀存储访问 NORMA(No-Remote Memory Access), 非远程存储访问结构越来越复杂 7

8 并行计算机访存模型 UMA(Uniform Memory Access) 均匀存储访问模型处理器 P 1 P 2 P n 系统互连 ( 总线, 交叉开关, 多级网络 ) I/O SM 1 SM m 共享存储器物理存储器被所有处理器均匀共享所有处理器访问任何存储所用时间相同每台处理器可带私有高速缓存 8

9 并行计算机访存模型 NUMA(Non-uniform Memory Access) 非均匀存储访问模型被共享的存储器在物理上分布在所有的处理器中, 所有本地存储器的集合组成了全局地址空间处理器访问存储器的时间不同 - 访问本地存储器 LM 或群内共享存储器 CSM 较快, 而访问外地的存储器或全局共享存储器 GSM 较慢此即非均匀存储访问名称的由来 LM 1 P 1 GSM = Global Shared Memory CSM = Cluster Shared Memory 模型一, 名词解释 LM = Local Memory P = Processor LM 2 P 2 LM n... P n 共享本地存储模型互连网络... 9

10 并行计算机访存模型非均匀存储访问模型 (NUMA), 模型二 GSM GSM... GSM P P... C I N 全局互连网络 CSM P CSM P C I N CSM CSM... 模型二, 名词解释 GSM = Global Shared Memory CSM = Cluster Shared Memory CIN = Cluster Interconnection Network P = Processor P CSM P CSM 群 1 群 N 层次式机群模型 10

11 并行计算机访存模型 COMA(Cache-Only Memory Access) 全高速缓存存储访问各处理器节点中没有复杂的存储层次结构, 全部高速缓存组成了全局地址空间利用分布的高速缓存目录 D 进行远程高速缓存的访问使用 COMA 时, 数据开始时可任意分配, 因为在运行时它最终会被迁移到需要使用它们的地方名词解释互连网络 D = Directory C = Cache P = Processor D D D C C C P P P 11

12 并行计算机访存模型 CC-NUMA(Coherent-Cache Nonuniform Memory Access) 高速缓存一致性非均匀存储访问模型大多数使用基于目录的高速缓存一致性协议保留 SMP 结构易于编程的优点, 也改善常规 SMP 的可扩放性 P/C I/O 节点 1 节点 N P/C Mem P/C P/C Mem 总线或交叉开关总线或交叉开关 NIC,DIR,RC I/O NIC,DIR,RC 系统互连网路 SMP = Symmetric Multi-processor DSM = Distributed Shared-Memory RC = Remote Cache NIC = Network Interface Circuitry DIR = 高速缓存目录 12

13 并行计算机访存模型 NORMA(No-Remote Memory Access) 非远程存储访问模型所有存储器是私有的, 仅能由其所属的处理器访问 - 对应的典型的体系结构模型 : 集群绝大数 NORMA 都不支持远程存储器的访问各处理器之间通过消息传递方式通信 M P M P... M P M P... M P 消息传递互连网络 ( 网络, 环网, 超立方, 立方环等 ) P M... P M P M P M... P M 13

14 并行计算机体系结构概括并行计算机体系结构与存储结构关系 MIMD 多处理机单地址空间共享存储器集中式存储 UMA NUMA 分布式存储 PVP (Cray T90) SMP COMA (Intel SHV SunFire DEC 8400 SGI PowerChallenge IBMR60) CC-NUMA (KSR-1 DDM) NCC-NUMA (Cray T3E) (Stanford Dash SGI Origin 2000 Sequent NUMA-Q HP/Convex Exemplar) NORMA 多地址空间非共享存储器 Cluster (IBM SP2 DEC TruCluster Tandem Hymalaya HP Microsoft Wolfpack) 松散耦合 MPP 紧耦合 (Intel TFLOPS) DSM (TreadMarks Wind Tunnel IVY Shrimp) 14

15 并行计算机体系结构概括并行计算机体系结构与存储结构关系多处理机单地址空间共享存储器集中式存储 UMA NUMA PVP (Cray T90) SMP COMA (Intel SHV SunFire DEC 8400 SGI PowerChallenge IBMR60) CC-NUMA (KSR-1 DDM) (Stanford Dash SGI Origin 2000 Sequent NUMA-Q HP/Convex Exemplar) MIMD 分布式存储 NCC-NUMA (Cray T3E) 多处理机部分 UMA = Uniform Memory Access NUMA = Non-uniform Memory Access SMP = Symmetric Multi-processor PVP = Parallel Vector Processor 15

16 并行计算机体系结构概括并行计算机体系结构与存储结构关系 MIMD 分布式存储 NCC-NUMA (Cray T3E) NORMA 多地址空间非共享存储器 Cluster (IBM SP2 DEC TruCluster Tandem Hymalaya HP Microsoft Wolfpack) 松散耦合 MPP 紧耦合 (Intel TFLOPS) DSM (TreadMarks Wind Tunnel IVY Shrimp) NORMA 部分多地址空间非共享存储 vs. 单地址空间共享存储 NORMA = No-Remote Memory Access MPP = Massive Parallel processor DSM = Distributed shared memory 16

与 Sandia 联合开发,MPP 并行计算机 SGI Origin 2000 系统典型的

17 并行计算机体系结构概括扩展学习资源 SGI 公司的 Power Challenge 系统典型的 SMP 并行计算机 SGI Power Challenge XL OptionRed 系统 Intel 与 Sandia 联合开发,MPP 并行计算机 SGI Origin 2000 系统典型的 CC-NUMA 结构 Berkeley 的 NOW 计划工作站机群的先驱性系统 SGI Origin

18 并行计算 :Parallel Computing 结构编程算法应用 2.2 并行计算机性能测评

19 并行计算机性能测评并行计算机性能测评概述硬件层面或机器层面程序层面或软件层面或算法层面并行计算机性能测评硬件层面测试测评计算开销通信开销存储开销加速比性能测评程序 / 软件层面测评可扩展性测评 19

20 并行计算机性能测评为什么要进行并行机性能测评? 对管理人员发挥并行机长处, 提高并行机使用效率对用户减少用户购机盲目性, 降低投资风险对架构师与设计人员改进系统结构设计促进软硬件结合, 合理划分功能对市场人员提供客观公正的评价标准

21 并行计算机性能测评 CPU 的部分通用性能指标浮点运算数 (FLOPS) 每秒浮点运算次数,floating-point operations per second, FLOPS 原因 : - 1. 并行计算, 特别是科学计算中大量使用浮点数, 即小数 - 2. 浮点数运算比整数运算更花费时间, 更有测量的意义与效果执行时间 T T comput : 计算时间,T paro : 为并行开销时间,T comm : 为相互通信时间 T n = T comput + T paro + T comm 21

22 并行计算机性能测评存储器性能存储器的层次结构 (C,L,B) Capacity: 容量 ;Latency: 延迟 ; Bandwidth: 带宽远程存储器 1-100GB K 周期 1-300MB/S 寄存器 1 级高速缓存 2 级高速缓存主存磁盘 C<2KB L=0 周期 B=1-32GB/S 4-256KB 0-2 周期 1-16GB/S 64KB-4MB 2-10 周期 1-4GB/S 16MB-16GB 周期 0.4-2GB/S 1-100GB 100K-1M 周期 1-16MB/S 估计存储器的带宽 RISC 命令 add r1,r2,r3 8bytes 100MHz B = 3*8*100*10 6 B/s= 2.4GB/s 注 :RISC,Reduced Instruction Set Computing, 精简指令集 22

23 并行计算机性能测评并行通信开销多机, 多核, 并行通信开销相对于计算很大以 PowerPC 为例 PowerPC - 全称 :Performance Optimization With Enhanced RISC Performance Computing, 基于精简指令集 (RISC) 架构的中央处理器 - 由 IBM Apple 等发起, 但后被 Intel 取代 ; 仍为重要的 CPU 种类每个周期 15ns, 执行 4flops; 创建一个进程 1.4ms, 可执行 flops 开销的测量乒乓方法 (Ping-Pong Scheme) 23

24 并行计算机性能测评 - 节点 0 发送 m 个字节给节点 1; 节点 1 从节点 0 接收 m 个字节后, 立即将消息发回节点 0 - 总的时间除以 2, 即可得到点到点通信时间, 也就是执行单一发送或接收操作的时间可一般化为热土豆法 (Hot-Potato), 也称为救火队法 (Fire- Brigade) n-1 0 热土豆法 Hot-potato routing 当收到一个分组时, 不管它的目的地址如何, 一定要以最快的速度转发出去, 就像拿到一个烫手的热土豆一样

25 并行计算机性能测评 for i=0 to Runs 1 do if (my _node _id =0) then /* 发送者 */ start _time =second() send an m-byte message to node 1 receive an m-byte message from node 1 end_time = second() total_time = end_time start_time communication_time[i] = total_time/2 else if (my_node_id = 1) then /* 接收者 */ receive an m-byte message from node 0 send an m-byte message to node 0 endif endfor 关键字注释 25

26 并行计算机性能测评并行开销的表达式 : 整体通信典型的整体通信包括播送 (Broadcasting) - 处理器 0 发送 m 个字节给所有的 n 个处理器收集 (Gather) - 处理 0 接收所有 n 个处理器发来在消息, 所以处理器 0 最终接收了 m n 个字节散射 (Scatter) - 处理器 0 发送了 m 个字节的不同消息给所有 n 个处理器, 因此处理器 0 最终发送了 m n 个字节全交换 (Total Exchange) - 每个处理器均彼此相互发送 m 个字节的不同消息给对方, 所以总通信量为 m n 2 个字节 27

27 并行计算机性能测评循环移位 (Circular-shift) - 处理器 i 发送 m 个字节给处理器 i+1, 处理器 n-1 发送 m 个字节给处理器 0, 所以通信量为 m n 个字节并行计算在机器上的成本与价格机器的性能 / 价格比 (Performance/Cost Ratio) 指用单位代价 ( 通常以百万美元表示 ) 所获取的性能 ( 通常以 MIPS 或 MFLOPS 表示 ) 两个重要的单位 - MIPS: 每秒百万条指令数,Million Instructions Per Second, 侧重衡量整数运算性能 - MFLOPS: 每秒百万条浮点运算次数, megaflops (mega floating point operations per second) 利用率 (Utilization): 可达到的速度与峰值速度之比 28

28 并行计算机性能测评算法层面 / 程序层面性能评测开始关注软件, 而不是硬件加速比性能评测并行系统的加速比是指对于一个给定的应用, 并行算法 ( 或并行程序 ) 的执行速度相对于串行算法 ( 或串行程序 ) 的执行速度加快了多少倍 Amdahl 定律 Gustafson 定律 Sun Ni 定律可扩展性评测等效率度量标准等速度度量标准平均延迟度量标准 29

或串行程序 ) 的执行速度加快了多少倍 Amdahl 定律 Gustafson 定律 Sun Ni 定律

29 并行计算机性能测评算法层面 / 程序层面性能评测开始关注软件, 而不是硬件加速比性能评测并行系统的加速比是指对于一个给定的应用, 并行算法 ( 或并行程序 ) 的执行速度相对于串行算法 ( 或串行程序 ) 的执行速度加快了多少倍 Amdahl 定律 Gustafson 定律 Sun Ni 定律可扩展性评测等效率度量标准等速度度量标准平均延迟度量标准 Gene Amdahl John L. Gustafson 30

30 并行计算机性能测评 Amdahl 定律 ( 相等负载 ) P: 处理器数 W: 问题规模 ( 计算负载工作负载, 给定问题的总计算量等 ) W s : 应用程序中的串行分量,f 是串行分量比例 f = W s / W W p : 应用程序中可并行化部分,1- f 为并行分量比例 W s + W p = W Amdahl 定律的出发点 - 固定不变的计算负载 - 固定的计算负载分布在多个处理器上的 - 增加处理器加快执行速度, 从而达到了加速的目的 31

31 并行计算机性能测评 Amdahl 定律 S: 加速比如何计算? 固定负载的加速公式 S = W s + W p W s + W p Τp W s + W p 可相应地表示为 W (f+(1-f)) 注 : W s + W p = W W s = W f S = f + (1 fሻ f + 1 f p = p 1 + f(p 1ሻ p 时, 上式极限为 S= 1 f 这意味着随着处理器数目的无限增大, 并行系统所能达到的加速比上限为 = 1 f, 这是不是一个很有利的结论 32

32 并行计算机性能测评 Amdahl 定律

33 并行计算机性能测评继续考虑并行的额外开销 W o 为额外开销 S = W s + W p W s + W p p + W O = = W W(1 fሻ Wf + p + W O p 1 + f(p 1ሻ + W O Τ p W p 时, 上式极限为 S= 1 f+ W O ΤW 串行分量越大和并行额外开销越大, 则加速越小 34

34 并行计算机性能测评 Gustafson 定律 ( 相等时间 ) 出发点精度要求 - 对于很多大型计算, 精度要求很高, 即在此类应用中精度是个关键因素, 而计算时间是固定不变的 - 此时为了提高精度, 必须加大计算量, 相应地亦必须增多处理器数才能维持时间不变实际应用 - 除非学术研究, 在实际应用中没有必要固定工作负载而计算程序运行在不同数目的处理器上 - 增多处理器必须相应地增大问题规模才有实际意义 35

35 并行计算机性能测评 Gustafson 定律 W s : 应用程序中的串行分量,f 是串行分量比例 W p : 应用程序中可并行化部分,1 f 为并行分量比例 S = W s + pw p W s + p W p Τp = W s + pw p W s + W p S = f + p(1 f) = p + f(1 pሻ = p f(p 1ሻ 结论当 p 充分大时,S 与 p 几乎成线性关系, 其斜率为 1 f 这意味着随着处理器数目的增加, 加速几乎与处理器数成比例的线性增加串行比例 f 不再是程序的瓶颈, 这对并行计算来说是一个乐观的结论 36

36 并行计算机性能测评 Gustafson 定律

37 并行计算机性能测评并行机的性能指标汇总名称符号含义单位机器规模 n 处理器的数目无量纲时钟速率 f 时钟周期长度的倒数 MHZ 工作负载 W 计算操作的数目 Mflop 顺序执行时间 T 1 程序在单处理机上的运行时间 s( 秒 ) 并行执行时间 T n 程序在并行机上的运行时间 s( 秒 ) 速度 R n = W/T n 每秒百万次浮点运算 Mflop/s 加速 S n =T 1 /T n 衡量并行机有多快无量纲效率 E n = S n /n 衡量处理器的利用率无量纲峰值速度 R peak = n R peak 所有处理器峰值速度之积, R peak 为一个处理器的峰值速度 Mflop/s 利用率 U =R n /R peak 可达速度与峰值速度之比无量纲通信延迟 t o 传送 0- 字节或单字的时间 Μs 渐近带宽 r 传送长消息通信速率 MB/s

38 并行计算机性能测评并行计算的可扩展性 (Scalability) 影响加速比的因素处理器数与问题规模求解问题中的串行分量并行处理所引起的额外开销 - 通信等待竞争冗余操作和同步等可扩展性在确定的应用背景下, 计算机系统 ( 或算法或程序等 ) 性能随处理器数的增加而按比例提高的能力可扩展性的内涵增加处理器数会增大额外开销和降低处理器利用率 39

39 并行计算机性能测评额外开销的增加可能慢于有效计算的增加算法中的串行分量比例不是固定不变的 - 串行部分所占的比例随着问题规模的增大而缩小并行计算中可扩展性的作用确定解决某类问题用何种并行算法与何种并行体系结构的组合 - 可以有效地利用大量的处理器对固定的问题规模, 确定在某类并行机上最优的处理器数与可获得的最大的加速比用于指导改进并行算法和并行机体系结构 - 以使并行算法尽可能地充分利用可扩充的大量处理器 40

40 并行计算机性能测评可扩展性 : 如何衡量并行计算要调整的是处理数 p 和问题规模 W 两者可按不同比例进行调整, 此比例关系可能是线性的, 多项式的或指数的等 ) 就反映了可扩展的程度目前没有一个公认的, 或者被普遍接受测评标准常用的可扩展性测评标准 ( 三个 ) - 等效率度量标准 - 等速度度量标准 - 平均延迟度量标准 41

41 第一次作业 ( 已布置 ) 题目题目 1. 从可扩展性上比较 SMP 与 MPP 两种体系结构 - 可扩展性的角度包括 : 内存大小可扩展性处理器数目可扩展性磁盘容量可扩展性等, 至少选取一个题目 2. 试说明 ( 可举例, 也可论证 ): 如何使用 SIMD 的机器上实现 MIMD 并行应用? - 即假设你身边有的只是 SIMD 的机器, 但任务却是要实现一个并行应用, 那是否有办法可完成? 42

42 第一次作业 ( 已布置 ) 要求独立完成, 发送电子版, 可以是 word, 也可以 pdf 作业提交地址 xdsepc2018@163.com 附件命名规则 : 学号 + 姓名 + 作业一时间 : 两周之内, 至第四次上课之前提交篇幅 : 没有绝对的页数要求, 但是两道题目一般不应少于 1 页 A4 纸的 2/3 课件地址 43

43 课件地址 44

44 2.2 主流并行计算机系统与性能测评结构编程算法应用

分层并行计算模型 Loyered Models of Parallel Computation

分层并行计算模型 Loyered Models of Parallel Computation 并行计算 Parallel Computing 主讲人孙广中 Spring, 2018 2018/3/19 1 / 43 思考题 1 问题 1: 谈谈你所知道的高性能计算与云计算的区别? 问题 2: 并行程序的描述应如何? 与串行程序有什么不同? 问题 3: 如何并行地尽快求解 n 个元素的最大值或排序? 2018/3/19 2 / 43 并行计算结构算法编程 ( 第三版 ) 第一篇并行计算硬件平台