高性能计算导论：并行计算性能评价1.ppt

并行计算性能评价 上海大学计算机工程与科学学院 计算的本质串行计算模型 图灵机并行计算模型计算效能评价 计算模型与效能评价 高性能计算导论 并行计算 研究的四大分支 并行计算机体系结构并行算法并行程序设计并行计算的性能评测而介于并行计算机体系结构与并行算法之间的是并行计算模型 PerformanceEvaluation 并行计算效能评价 程序性能评价与优化 给定并行算法 采用并行程序设计平台 通过并行实现获得实际可运行的并行程序后 一个重要的工作就是 在并行机上运行该程序 评价该程序的实际性能 揭示性能瓶颈 指导程序的性能优化 性能评价和优化是设计高效率并行程序必不可少的重要工作 并行程序执行时间 评价并行程序的性能之前 必须清楚并行程序的执行时间是由哪些部分组成的 众所周知 独享处理器资源时 串行程序的执行时间近似等于程序指令执行花费的CPU时间 但是 并行程序相对复杂 其执行时间 executiontime 等于从并行程序开始执行 到所有进程执行完毕 墙上时钟走过的时间 也称之为墙上时间 walltime 对各个进程 墙上时间可进一步分解为 计算CPU时间通信CPU时间同步开销时间进程空闲时间 是由同步导致的 并行程序执行时间 计算CPU时间进程指令执行所花费的CPU时间 它可以分解为两个部分 一个是程序本身指令执行占用的CPU时间 即通常所说的用户时间 usertime 主要包含指令在CPU内部的执行时间和内存访问时间 另一个是为了维护程序的执行 操作系统花费的CPU时间 即通常所说的系统时间 systemtime 主要包含内存调度和管理开销 I O时间 以及维护程序执行所必需要的操作系统开销等 通常地 系统时间可以忽略 并行程序执行时间 通信CPU时间包含进程通信花费的CPU时间 同步开销时间包含进程同步花费的时间进程空闲时间当一个进程阻塞式等待其他进程的消息时 CPU通常是空闲的 或者处于等待状态 进程空闲时间是指并行程序执行过程中 进程所有这些空闲时间的总和 显然 进程的计算CPU时间小于并行程序的墙上时间 而并行程序的墙上时间才是用户真正关心的时间 是评价一个并行程序执行速度的时间 2020 3 15 9 59 并行算法设计及效能分析 并行算法效能分析 并行加速比 并行效率 可扩展性 简单表述 处理机数p增加时 并行效率Ep不显著下降 效能分析分析说明 需要说明的是 T1指处理器个数为1时 并行程序的执行时间 通常情形下 T1大于TS 因为并行程序往往引入一些冗余的控制和管理开销 加速比和效率是衡量一个并行程序性能的最基本的评价方法 显然 执行最慢的进程将决定并行程序的性能 在以上加速比和效率的定义中 有一个基本的假设 要求并行机的各个处理器是同构 homogeneous 的 即并行机各个处理器的结构完全一致 包含CPU类型 内存大小与性能 cache特征等等 或者说 串行程序在各个处理器执行的墙上时间相等 效能分析分析说明 如果并行机的各个处理器功能不一致 称之为异构并行机 对此 以上加速比和效率的定义不是很合适 其中 两个突出的问题就是 串行程序的执行时间是选择最快的处理器运行 还是选择最慢的处理器运行 在效率定义中 处理器个数选择为P是否合适 一个比较好的方法就是 将所有处理器以最快的处理器为基准 进行归一化处理 并行程序性能评价方法 以上介绍的加速比和效率 只能反映并行程序的整体执行性能 但是 无法反映并行程序的性能瓶颈 性能评价的主要目的在于 揭示并行程序的性能瓶颈 指导并行程序的性能优化 因此 有必要进一步分解加速比和效率 提出更细致的性能评价方法 并行计算性能评测 3 1并行机的一些基本性能指标3 2加速比性能定律3 2 1Amdahl定律3 2 2Gustafson定律3 2 3Sun和Ni定律3 3可扩放性评测标准3 3 1并行计算的可扩放性3 3 2等效率度量标准3 3 3等速度度量标准3 3 4平均延迟度量标准 3 4基准测试程序 并行计算的性能评测 机器级的性能评测CPU和存储器的某些基本性能指标并行通信开销机器的成本 价格 和性能 价格比等算法级的性能评测加速比效率可扩展性程序级的性能评测基本测试程序数学库测试并行测试程序等 并行机基本性能参数一览表 工作负载 工作负载 荷 计算操作数目执行时间 掠过时间 墙上时间所执行的指令数目所完成的浮点运算数 CPU的某些基本性能指标 工作负载执行时间 程序从开始到结束的时间 浮点运算数指令数目 通常用百万条指令并行执行时间Tn Tcomput为计算时间 Tparo为并行开销时间 Tcomm为相互通信时间Tn Tcomput Tparo Tcomm例 估计APRAM模型下执行时间其中T1为串行时间 n为处理器数 T 为使用无限多处理器且不考虑Tparo与Tcomm的并行执行时间 存储器性能 存储器的层次结构 C L B 容量C 延迟L 带宽B估计存储器的带宽RISC指令addr1 r2 r3 寄存器8bytes 主频100MHzB 3 8 100 106B s 2 4GB s 并行与通信开销 并行和通信开销 相对于计算很大 PowerPC 每个周期15ns执行4flops 创建一个进程1 4ms可执行372000flops 开销的测量 乒 乓方法 Ping PongScheme 节点0发送m个字节给节点1 节点1从节点0接收m个字节后 立即将消息发回节点0 总的时间除以2 即可得到点到点通信时间 也就是执行单一发送或接收操作的时间 可一般化为热土豆法 Hot Potato 也称为救火队法 Fire Brigade 0 1 2 n 1 0即从节点0发送m字节给1 节点1给节点2 依次类推 最后节点n 1再将其返回给0 最后时间再除以n即可 Ping PongScheme if my node id 0 then 发送者 start time second sendanm bytemessagetonode1 发送receiveanm bytemessagefromnode1 接收end time second total time end time start timecommunication time i total time 2elseif my node id 1 then 接收者 receiveanm bytemessagefromnode0sendanm bytemessagetonode0endif 并行开销的表达式 点到点通信 通信开销t m t0 m r 通信启动时间t0渐近带宽r 传送无限长的消息时的通信速率m为传输的字节数半峰值长度m1 2 达到一半渐近带宽所要的消息长度特定性能 0 表示短消息带宽t0 m1 2 r 1 0 并行开销的表达式 组通信 典型的组通信有 播送 Broadcasting 处理器0发送m个字节给所有的n个处理器 广播收集 Gather 处理0接收所有n个处理器发来在消息 所以处理器0最终接收了mxn个字节 散射 Scatter 处理器0发送了m个字节的不同消息给所有n个处理器 因此处理器0最终发送了mxn个字节 全交换 TotalExchange 每个处理器均彼此相互发送m个字节的不同消息给对方 所以总通信量为mxn2个字节 循环移位 Circular shift 处理器i发送m个字节给处理器i 1 处理器n 1发送m个字节给处理器0 所以通信量为mxn个字节 机器的成本 价格与性 价比 机器的成本与价格机器的性能 价格比Performance CostRatio 系指用单位代价 通常以百万美元表示 所获取的性能 通常以MIPS或MFLOPS表示 利用率 Utilization 可达到的速度与峰值速度之比 并行计算性能评测 3 1并行机的一些基本性能指标3 2加速比性能定律3 2 1Amdahl定律3 2 2Gustafson定律3 2 3Sun和Ni定律3 3可扩放性评测标准3 3 1并行计算的可扩放性3 3 2等效率度量标准3 3 3等速度度量标准3 3 4平均延迟度量标准 3 4基准测试程序 算法级性能评测 加速比性能定律并行系统的加速比是指对于一个给定的应用 并行算法 或并行程序 的执行速度相对于串行算法 或串行程序 的执行速度加快了多少倍 Amdahl定律Gustafson定律SunNi定律可扩放性评测标准等效率度量标准等速度度量标准平均延迟度量标准 Amdahl定律 1967 参数约定P 处理器数 W 问题规模 计算负载 工作负载 给定问题的总计算量 Ws 应用程序中的串行分量 f是串行分量比例 f Ws W Ws W1 WP 应用程序中可并行化部分 1 f为并行分量比例 Ws Wp W Ts T1 串行执行时间 Tp 并行执行时间 S 加速比 E 效率 出发点 固定不变的计算负载 固定的计算负载分布在多个处理器上 增加处理器加快执行速度 从而达到了加速的目的 Amdahl定律 cont d 固定负载的加速公式 归一化 Ws Wp可相应地表示为f 1 f 近似公式 p 时 上式极限为S 1 f考虑额外开销Wo Amdahl slaw cont d Gustafson定律 1988 出发点 对于很多大型计算 精度要求很高 即在此类应用中精度是个关键因素 而计算时间是固定不变的 此时为提高精度 必须加大计算量 相应地亦必须增多处理器数才能维持时间不变 除非学术研究 在实际应用中没有必要固定工作负载而计算程序运行在不同数目的处理器上 增多处理器必须相应地增大问题规模才有实际意义 Gustafson定律 1988 Gustafson加速定律 近似公式 p 时 S p fp 1 f P 1 f为斜率并行开销Wo Gustafson定律 cont d Sun和Ni定律 基本思想 只要存储空间许可 应尽量增大问题规模以产生更好和更精确的解 此时可能使执行时间略有增加 假定在单节点上使用了全部存储容量M并在相应于W的时间内求解之 此时工作负载W fW 1 f W 在p个节点的并行系统上 能够求解较大规模的问题是因为存储容量可增加到pM 令因子G p 反应存储容量增加到p倍时并行工作负载的增加量 所以扩大后的工作负载W fW 1 f G p W Sun和Ni定律 存储受限的加速公式 并行开销Wo Sun和Ni定律 cont d Sun和Ni定律 cont d 讨论 G p 1时 就是Amdahl加速定律 G p p时 s 变为f p 1 f 就是Gustafson加速定律G p p时 相应于计算机负载比存储要求增加得快 此时Sun和Ni加速均比Amdahl加速和Gustafson加速为高 加速比讨论 参考的加速经验公式 p logp S P线性加速比 很少通信开销的矩阵相加 内积运算等p logp的加速比 分治类的应用问题通信密集类的应用问题 S 1 C p C p 为与p有关的通信函数超线性加速 并行搜索 Cache效应绝对加速 最佳并行算法与串行算法相对加速 同一算法在单机和并行机的运行时间 可扩展分析 给定并行算法 程序 和并行机 如何调整参与并行计算的处理器个数P和求解问题的计算规模W 使得随着处理器个数的增长 并行计算的效率可以保持不变 称之为并行程序和并行机相结合的可扩展分析 可扩展分析是并行计算一个重要研究课题 被广泛应用于描述并行算法 程序 能否有效利用可扩展的处理器个数的能力 可扩展分析目的 通常地 可扩展分析具有四个目的 选择合理的算法与结构组合确定求解某类问题的何种并行算法与何种并行机的组合 它可以有效地利用所期望的处理器规模 性能预测对于运行在某台并行机上的某种算法 程序 根据算法 程序 在小处理器规模上的运行性能 预测该算法 程序 移植到大处理器规模上后运行的性能 最优性能选择对某类算法 假设问题规模固定 确定在某类并行机上最优的处理器个数和可获得的最优的加速比 指导性能优化指导改进并行算法 程序 使得并行算法充分利用可扩展的处理器规模 指导性能优化指导改进并行算法 程序 使得并行算法充分利用可扩展的处理器规模 可扩展分析方法 1 等效率度量对于某类算法和并行机 如何保持问题规模W与处理器个数P之间的关系WpPq 使得随着处理器个数P的增长 保持并行计算的效率不变 也就是求出等效率函数 W fE P E固定等效率值越小 则当处理器个数增多时为保持相同效率所需增加的问题规模就越小 因此就有更好的可扩展性 可扩展分析方法 2 等速度度量对于运行在并行机上的某个算法 当处理器个数增加时 需要增加多大的计算量 才能保持并行程序的平均速度不变 定义平均速度 V为并行程序的执行速度 问题规模从 W P 变化到 W P 则等速度可扩展度量公式可写为 越接近1 说明可扩展性越好 并行程序性能优化 并行程序的性能优化相对于串行程序而言更加复杂 其中最主要的是选择好的并行算法及通信模式 在并行算法确定之后 影响并行程序效率的主要因素是通信开销 由于数据相关性或负载不平衡引起的进程空闲等待 以及并行算法引入的冗余计算 在设计并行程序时 可以采用多种技术来减少或消除这些因素对并行效率的影响 并行程序优化技术 1 减少通信量 提高通信粒度2 全局通信尽量利用高效聚合通信算法3 挖掘算法的并行度 减少CPU空闲等待4 负载平衡5 通信 计算的重叠6 通过引入重复计算来减少通信 1 减少通信量 提高通信粒度 在消息传递并行程序中 花费在通信上的时间是纯开销 因此如何减少通信时间是并行程序设计中首先要考虑的问题 减少通信时间的途径主要有三个 减少通信量 提高通信粒度和提高通信中的并发度 即不同结点对间同时进行通信 要注意的是 这些手段都是相对于特定条件而言的 例如 在网络重负载的情况下 提高通信并行度并不能改善程序的性能 提高通信粒度的有效方法是减少通信次数 即尽可能将可以一起传递的数据合并起来一次传递 在收发不同类型的数据时 定义适当的MPI数据类型来避免内存中的数据拷贝 2 全局通信尽量利用高效聚合通信算法 当组织多个进程之间的聚合通信时 使用高效的通信算法可以大大提高通信效率 降低通信开销 对于标准的聚合通信 如广播 归约 数据散发与收集等 尽量调用MPI标准库中的函数 因为这些函数往往经过专门优化 但使用标准库函数的一个缺点是整个通信过程被封装起来 无法在通信的同时进行计算工作 此时 可以自行编制相应通信代码 将其与计算过程结合起来 以达到最佳的效果 3 挖掘算法的并行度 减少CPU空闲等待 一些具有数据相关性的计算过程会导致并行运行的部分进程空闲等待 在这种情况下 可以考虑改变算法来消除数据相关