并行计算

Size: px

Start display at page:

Download "并行计算"

淇孟
7 years ago
Views:

1 并行计算 Parallel Comuting 主讲人孙广中 Sring, 2016

2 并行计算结构算法编程第一篇并行计算的基础第一章并行计算与并行计算机结构模型第二章并行计算机系统互连与基本通信操作第三章典型并行计算机系统介绍第四章并行计算性能评测 2

3 第四章并行计算性能评测 4.1 并行机的一些基本性能指标 4.2 加速比性能定律 Amdahl 定律 Gustafson 定律 Sun 和 Ni 定律 4.3 可扩放性评测标准并行计算的可扩放性等效率度量标准等速度度量标准平均延迟度量标准 3

4 CPU 的某些基本性能指标工作负载执行时间浮点运算数 : Flos 指令数目 : MIPS 无重叠的假定下 : 并行执行时间包括 T comut 计算时间, T aro 并行开销时间,T comm 相互通信时间 T n T comut + T aro+ T comm T aro : 进程管理 ( 如进程生成结束和切换等 ), 组操作 ( 如进程组的生成与消亡等 ), 进程查询 ( 如询问进程的标志等级组标志和组大小等 ) T comm : 同步 ( 如路障锁临界区事件等 ), 通讯 ( 如点到点通信整体通信 ), 聚合操作 ( 如规约前缀运算等 ) 4

5 存储器性能存储器的层次结构 ( 容量 C, 延迟 L, 带宽 B) 远程存储器 1-100GB K 周期 1-300MB/S 寄存器 1 级高速缓存 2 级高速缓存主存磁盘 C<2KB L0 周期 B1-32GB/S 4-256KB 0-2 周期 1-16GB/S 估计存储器的带宽 64KB-4MB 2-10 周期 1-4GB/S 16MB-16GB 周期 0.4-2GB/S RISC 的加法可在单拍内完成, 假定字长 8bytes, 时钟频率 100MHz, 则带宽 B 3*8*100*10 6 B/s 2.4GB/s 1-100GB 100K-1M 周期 1-16MB/S 5

6 并行与通信开销并行和通信开销 : 相对于计算很大 PowerPC ( 每个周期 15ns 执行 4flos; 创建一个进程 1.4ms 可执行 flos) 开销的测量 : 乒 -- 乓方法 (Ping-Pong Scheme) 节点 0 发送 m 个字节给节点 1; 节点 1 从节点 0 接收 m 个字节后, 立即将消息发回节点 0 总的时间除以 2, 即可得到点到点通信时间, 也就是执行单一发送或接收操作的时间可一般化为热土豆法 (Hot-Potato), 也称为救火队法 (Fire-Brigade) n-1 0 6

7 Ping-Pong Scheme 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 7

8 并行开销的表达式 : 点到点通信通信开销 t(m) t 0 + m/ r m 为消息长度 ( 字节数 ) 通信启动时间 t 0 渐近带宽 r : 传送无限长的消息时的通信速率半峰值长度 m 1/2 : 达到一半渐近带宽所要的消息长度特定性能 π 0 : 表示短消息带宽 4 个参数只有两个是独立的 : t 0 m 1/2 / r 1 /π 0 以上是由 Hockney 提出的 8

9 并行开销的表达式 : 整体通信典型的整体通信有 : 播送 (Broadcasting): 处理器 0 发送 m 个字节给所有的 n 个处理器收集 (Gather): 处理 0 接收所有 n 个处理器发来在消息, 所以处理器 0 最终接收了 m n 个字节 ; 散射 (Scatter): 处理器 0 发送了 m 个字节的不同消息给所有 n 个处理器, 因此处理器 0 最终发送了 m n 个字节 ; 全交换 (Total Exchange): 每个处理器均彼此相互发送 m 个字节的不同消息给对方, 所以总通信量为 mn 2 个字节 ; 循环移位 (Circular-shift): 处理器 i 发送 m 个字节给处理器 i+1, 处理器 n-1 发送 m 个字节给处理器 0, 所以通信量为 m n 个字节 9

10 机器的成本价格与性 / 价比机器的成本与价格机器的性能 / 价格比 Performance/Cost Ratio : 系指用单位代价 ( 通常以百万美元表示 ) 所获取的性能 ( 通常以 MIPS 或 MFLOPS 表示 ) 利用率 (Utilization): 可达到的速度与峰值速度之比 10

11 加速比性能定律算法级性能评测并行系统的加速比是指对于一个给定的应用, 并行算法 ( 或并行程序 ) 的执行速度相对于串行算法 ( 或串行程序 ) 的执行速度加快了多少倍 Amdahl 定律 Gustafson 定律 Sun Ni 定律可扩放性评测标准等效率度量标准等速度度量标准平均延迟度量标准 11

12 第四章并行计算性能评测 4.1 并行机的一些基本性能指标 4.2 加速比性能定律 Amdahl 定律 Gustafson 定律 Sun 和 Ni 定律 4.3 可扩放性评测标准并行计算的可扩放性等效率度量标准等速度度量标准平均延迟度量标准 12

13 Amdahl 定律 (1) P: 处理器数 ; W: 问题规模 ( 计算负载工作负载, 给定问题的总计算量 ); W s : 应用程序中的串行分量,f 是串行分量比例 (f W s /W, W s ); W P : 应用程序中可并行化部分,1-f 为并行分量比例 ; W s +W W; T s : 串行执行时间,T : 并行执行时间 ; S: 加速比,E: 效率 ; 出发点 :Base on Fixed Problem Size 固定不变的计算负载 ; 固定的计算负载分布在多个处理器上的, 增加处理器加快执行速度, 从而达到了加速的目的 13

14 Amdahl s Law 表明 : Amdahl 定律 (2) 适用于实时应用问题当问题的计算负载或规模固定时, 我们必须通过增加处理器数目来降低计算时间 ; 加速比受到算法中串行工作量的限制 Amdahl s law: argument against massively arallel systems 公式推导 T S s fw fw + (1 W (1 f ) W + f ) W f T + 1 f fw + (1 1 ( 1) f f ) W f 14

15 Amdahl s law (3) 1024x 工作负载 W W W W W W W 执行时间 T T T T T T T 加速比 S S /(1+1023f) 91x 48x 31x 24x 1x 0% 1% 2% 3% 4% 100% 处理器数 P 处理器数 P 程序中顺序部分的百分比 f (a) (b) (c) 实际上并行加速不仅受限于串行分量, 而且也受并行实现时的额外开销的限制 :P124(old P84) 15

16 Gustafson 定律 (1) 出发点 :Base on Fixed Execution Time 对于很多大型计算, 精度要求很高, 即在此类应用中精度是个关键因素, 而计算时间是固定不变的此时为了提高精度, 必须加大计算量, 相应地亦必须增多处理器数才能维持时间不变 ; 表明 : 随着处理器数目的增加, 串行执行部分 f 不再是并行算法的瓶颈 Gustafson 加速定律 : S' WS W + S' f + ( 1 -f) + f ( 1-) -f (-1 ) 并行开销 W o : S ' WS + WP W + W + W S P O S + W W / f + 1+ W W W ( 1 f ) O / W S S + W + W P 16

17 Gustafson 定律 (2) 工作负载 W W W W W W W 执行时间 T T T T T T T 加速比 S ' 1024x 1014x 1004x 993x 983x S ' f 处理器数 P (a) 处理器数 P (b) 0% 1% 2% 3% 4% 程序中顺序部分的百分比 f (c) 17

18 Sun 和 Ni 定律 (1) 出发点 : Base on Memory Bounding 充分利用存储空间等计算资源, 尽量增大问题规模以产生更好 / 更精确的解是 Amdahl 定律和 Gustafson 定律的推广公式推导 : 设单机上的存储器容量为 M, 其工作负载 WfW+(1-f)W 当并行系统有个结点时, 存储容量扩大了 M, 用 G() 表示系统的存储容量增加倍时工作负载的增加量则存储容量扩大后的工作负载为 WfW+(1-f)G()W, 所以存储受限的加速为 '' fw + ( 1 f ) ) W f + ( 1 f ) G( ) S fw + ( 1 f ) G( ) W / f + 1 f G / 并行开销 W o : S '' fw + ( 1 f ) WG( ) ( 1 f ) G( ) W / fw + ( ) ( ) f + ( 1 f ) G( ) ( 1 f ) G( ) / + W W + WO f + O / 18

19 Sun 和 Ni 定律 (2) 工作负载 W W W W 执行时间 T T T T W W W T T T 处理器数 P (a) 处理器数 P G()1 时就是 Amdahl 加速定律 ; G() 变为 f + (1-f), 就是 Gustafson 加速定律 G()> 时, 相应于计算机负载比存储要求增加得快, 此时 Sun 和 N i 加速均比 Amdahl 加速和 Gustafson 加速为高 (b) 19

20 加速比讨论参考的加速经验公式 : /log S P 线性加速比 : 很少通信开销的矩阵相加内积运算等 /log 的加速比 : 分治类的应用问题通信密集类的应用问题 :S 1 / C () 这里 C() 是个处理器的某一通信函数超线性加速绝对加速 : 最佳串行算法与并行算法相对加速 : 同一算法在单机和并行机的运行时间 20

21 第四章并行计算性能评测 4.1 并行机的一些基本性能指标 4.2 加速比性能定律 Amdahl 定律 Gustafson 定律 Sun 和 Ni 定律 4.3 可扩放性评测标准并行计算的可扩放性等效率度量标准等速度度量标准平均延迟度量标准 21

22 可扩放性评测标准 (1) 并行计算的可扩放性 (Scalability) 也是主要性能指标可扩放性最简朴的含意是在确定的应用背景下, 计算机系统 ( 或算法或程序等 ) 性能随处理器数的增加而按比例提高的能力影响因素 : 处理器数与问题规模, 还有求解问题中的串行分量 ; 并行处理所引起的额外开销 ( 通信等待竞争冗余操作和同步等 ); 加大的处理器数超过了算法中的并发程度 ; 增加问题规模的好处 : 提供较高的并发机会 ; 额外开销的增加可能慢于有效计算的增加 ; 算法中的串行分量比例不是固定不变的 ( 串行部分所占的比例随着问题规模的增大而缩小 ) 增加处理器数会增大额外开销和降低处理器利用率, 所以对于一个特定的并行系统 ( 算法或程序 ), 它们能否有效利用不断增加的处理器的能力应是受限的, 而度量这种能力就是可扩放性这一指标 22

23 可扩放性评测标准 (2) 可扩放性 : 调整什么和按什么比例调整并行计算要调整的是处理数和问题规模 W, 两者可按不同比例进行调整, 此比例关系 ( 可能是线性的, 多项式的或指数的等 ) 就反映了可扩放的程度与并行算法和体系结构相关可扩放性研究的主要目的 : 确定解决某类问题用何种并行算法与何种并行体系结构的组合, 可以有效地利用大量的处理器 ; 对于运行于某种体系结构的并行机上的某种算法当移植到大规模处理机上后运行的性能 ; 对固定的问题规模, 确定在某类并行机上最优的处理器数与可获得的最大的加速比 ; 用于指导改进并行算法和并行机体系结构, 以使并行算法尽可能地充分利用可扩充的大量处理器目前无一个公认的标准的和被普遍接受的严格定义和评判它的标准 23

24 等效率度量标准 (1) 令 t ie 和 t io 分别是并行系统上第 i 个处理器的有用计算时间和额外开销时间 ( 包括通信同步和空闲等待时间等 ) 1 i Te te Ts i T o t o i 0 i 0 T 是个处理器系统上并行算法的运行时间, 对于任意 i 显然有 T t ie +t io, 且 T e + T o T 问题的规模 W 定义为最佳串行算法所完成的计算量,WT e S T T e T e Te + T o T 1 + T o e To 1 + W 如果问题规模 W 保持不变, 处理器数增加, 开销 T o 增大, 效率 E 下降为了维持一定的效率 ( 介于 0 与 1 之间 ), 当处理数增大时, 需要相应地增大问题规模 W 的值由此定义函数 f E () 为问题规模 W 随处理器数变化的函数, 为等效率函数 (ISO-efficiency Function) (Kumar1987) E S 1 1 T 1+ T o + e 1 1 To W 24

25 等效率度量标准 (2) 曲线 1 表示算法具有很好的扩放性 ; 曲线 2 表示算法是可扩放的 ; 曲线 3 表示算法是不可扩放的优点 : 简单可定量计算的少量的参数计算等效率函数缺点 : 如果 T o 无法计算出 ( 在共享存储并行机中 ) 曲线 3 曲线 2 工作负载 W 曲线 1 处理器数 P 25

26 等速度度量标准 (1) 出发点 : 对于共享存储的并行机, T o 难以计算, 如果速度能以处理器数的增加而线性增加, 则说明系统具有很好的扩放性表示处理器个数,W 表示要求解问题的工作量或称问题规模 ( 在此可指浮点操作个数 ),T 为并行执行时间, 定义并行计算的速度 V 为工作量 W 除以并行时间 T 个处理器的并行系统的平均速度定义为并行速度 V 除以处理器个数 : V V W T W 是使用个处理器时算法的工作量, 令 W 表示当处理数从增大到时, 为了保持整个系统的平均速度不变所需执行的工作量, 则可得到处理器数从到时平均速度可扩放度量标准公式 ( 介于 0 与 1 之间, 比值越靠近 1 越好 ) W / Ψ(, ' ) W ' / ' ' W W ' 26

27 等速度度量标准 (2) 优点 : 直观地使用易测量的机器性能速度指标来度量缺点 : 某些非浮点运算可能造成性能的变化没有考虑等速度度量标准的扩放性与传统加速比之间的关系 : 当 1 时, 等速度度量标准为 W /1 Ψ( ') Ψ(1, ') W '/ ' ' W W ' 其主要差别 : 加速比的定义是保持问题规模不变, 标志对于串行系统的性能增加 ; 扩放性定义是保持平均速度不变, 标志对于小系统到大规模系统所引起的性能变化 1 T ' 解决工作量为 W的问题所需串行时间解决工作量为 W 的问题所需并行时间 T 27

28 平均延迟度量标准 (1) 一个并行系统执行的时间图谱 5 T 5 T ara 执行时间 Tara T 2 T3 T 4 T 5 1 T6 T 7 T 8 P 1 P 2 P 3 P 4 P 5 P 6 P 7 P 8 处理器数 P 启动前与结束后空闲时间开销延迟 L i 运行时间 T i 28

29 平均延迟度量标准 (2) T i 为 P i 的执行时间, 包括延迟 L i Pi 的总延迟时间为 L i+ 启动时间 + 停止时间定义系统平均延迟时间为 L 又有 T ara T o + T seq, 所以 ( W, ) ( T T L ) ara i + i L i 1 ( W ) T T, ara ( W ) T o L, seq ( ) L W ', ' 在个处理器上求解工作量为 W 问题的平均延迟当处理器数由变到, 而维持并行执行效率不变, 则定义平均延迟可扩放性度量标准为 Φ (,, ' ) E L L ( W, ) ( W ', ' ) 该值在 0 1 之间, 值越接近 1 越好 29

30 平均延迟度量标准 (3) 优点 : 平均延迟能在更低层次上衡量机器的性能缺点 : 需要特定的软硬件才能获得平均延迟 30

<453A5CBDCCD1A72DBFCEB3CC5C C4EAB4BA20B2A2D0D0BCC6CBE35C536C E65775C D E >

<453A5CBDCCD1A72DBFCEB3CC5C C4EAB4BA20B2A2D0D0BCC6CBE35C536C E65775C D E > 并行计算 Parallel Computing 主讲人孙广中 Spring, 2018 2018-4-11 并行计算结构算法编程第一篇并行计算的基础第一章并行计算与并行计算机结构模型第二章并行计算机系统互连与基本通信操作第三章典型并行计算机系统介绍第四章并行计算性能评测 2018-4-11 第四章并行计算性能评测 4.1 并行机的一些基本性能指标 4.2 加速比性能定律 4.2.1