第一章 加速比.ppt

高等计算机系统结构 总学时 32理论学时 28讨论 4平时 课堂发言 讨论等等 10 作业 5次 占总分数30 期末考试 60 上课地点 工一508 1 16周 周二1 2节 高等计算机系统结构课程介绍 教材1 KaiHuang著 王鼎兴 郑纬民 沈美明译 高等计算机系统结构并行性可扩展性可编程性 清华大学出版社 2 PattersonD A HennesyJ L ComputerArchitecture AQuantitativeApproach MorganKanfmannPublishers 1995 3 PattersonD A HennesyJ L ComputerOrganization Design TheHardware SoftwareInterface 高等计算机系统结构 第一章加速比性能模型与可扩展性分析第二章高等计算机的核心技术 并行处理第三章互连与通信第四章划分与调度第五章并行存储器系统第六章CacheCoherence第七章MemoryConsistency第八章指令级并行处理第九章多处理机实例第十章高性能微处理器第十一章网格计算与云计算 课程概述 系统结构研究的范围 指令集设计 功能组织 逻辑设计与实现HPC的性能分析 评价方法 标准并行处理 各个功能部件 各个级别指令集 软件的作用 程序员眼中的结构系统集成 部件之间的配合 平衡发展趋势 制造技术进步 设计的创新 上个世纪90年代后 后者带来的性能提高几乎是前者的5倍 高性能计算机简介 TOP500 HTC 第一章加速比性能模型与可扩展性分析 1 1计算机的发展变化及影响体系结构的因素1 1 1计算机发展历程1 1 2影响体系结构的因素1 1 3计算机性能评价1 2加速比性能分析1 2 1一般概念1 2 2加速比1 2 3三种加速比性能模型1 3可扩展性分析 1 1计算机的发展变化及影响体系结构的因素 1 1 1计算机发展历程1 第一代 真空管 1946 1957 2 第二代 电子管 1957 1964 3 集成电路 1965 1971 4 以后几代 LSIVLSI 1972 至今 1 1 1计算机发展历程 1 第一代 电子真空管代表 ENIAC 1946年 特点 体积庞大 占地1500平方英尺 功率 200KW 必须手动编程 性能 读卡速度120张 分钟 加法运算5000 秒 除法150 秒 不太可靠 机器的正确率仅为20 目标 机器有18000真空管 在炮弹到达目标之前 ENIAC能够计算出大口径海军炮弹轨道 2 晶体管代表 IBM7094特点 磁芯存储技术 容量32K 周期2微秒 十几万个晶体管目标 科学计算 商业应用 3 集成电路代表 特点 存储容量512k 处理器周期0 2微秒 第一次提出 兼容性 概念 模块化设计 目标 科学计算 商业应用 影响 奠定大型机体系结构 4 LSIVLSI代表 微处理器的变化从4004到PentiumII时钟 108K 300MHZ晶体管数 2300 750万晶体管尺寸 10微米 0 3微米可寻址存储器 640bit 64GB 1 1 2影响影响体系结构的因素 1 硬件 技术进步 改变软硬件界面 2 软件 兼容性 高级语言 模拟与仿真 3 应用 应用的规模 精度等增长对计算机速度的要求提高 4 价格 性能与价格的平衡 1 1 3计评价算机性能 1 执行时间是衡量计算机性能的标准 2 主要标准 1 MIPS millioninstructionspersecond 2 MFLOPS millionfloatingpointoperationspersecond 3 基准测试程序a 实际应用程序b 核心程序c 基准测试程序d 综合基准测试程序 3 性能的比较和总结评价一台计算机的性能既是简单又是复杂的 1 不同程序对机器的性能的不确定性 2 不同输入的不确定性 1 1加速比性能模型 1 1 1一般概念1 处理机 时间积处理机数目与处理时间的乘积用以度量这些处理机运行时的资源利用率 若一程序在 P台处理机上运行的时间为Tp 则此P台处理机在Tp时间间隔内完成的工作最大数量为Tp P 可将处理机实际工作曲线对时间的积分看成是这些处理机完成的有效工作量 效率为有效工作量与最大工作量之比 2 并行度 DegreeOfParallelism DOP 并行度 DOP 是在一定时间间隔内执行一个程序所用的处理机的数目 3 并行性分布图执行一个给定的程序时DOP对时间的分布图 DOP与对应时间的间隔之积即为处理机要完成的工作或工作负载 下图所示为一个并行性分布图 DOP t1 t t2 并行性分布图 1 1 2加速比1 绝对加速比将最好的串行算法与并行算法相比较 定义一 与具体机器有关 将最好的串行算法在一台上的运行时间与并行算法在N台运行的时间相比 定义二 与具体机器无关 将最好的串行算法在最快的顺序机上的执行时间与并行算法在并行机上的运行时间相比 2 相对加速比同一并行算法在单节点上运行时间与在多个相同节点构成的处理机系统上的运行时间之比 这种定义侧重于描述算法和并行计算机本身的可扩展性 线性加速比 中间开销小 通信少 弱耦合计算超线性加速比 当应用需要大内存时可能出现病态加速比 加速比递减 可能是计算量太小 1 1 3三种加速比性能模型 1 固定负载加速比性能模型 Amdahl定律在许多实时应用领域 计算负载的大小常固定 在并行机中 此负载可分布至多台并行执行 获得的加速比称为fixed loadspeedup 一个问题的负载可表示如下 W Ws Wp其中 Ws代表问题中不可并行化的串行部分负载 Wp表示可并行化的部分负载 则n个节点情况下 加速比可以表示如下 设串行因子 为串行部分所占的比例 即 代入即得Amdahl law 不管采用多少处理机 可望达到的最好加速比 效率En可以表示为 处理机数目n越大 效率En越低 Amdahl定律告诉我们 系统中某一部件由于采用某种更快的执行方式后整个系统性能的提高与这种执行方式的使用频率或占总执行时间的比例有关 加速比的两个决定因素 1 计算机执行某个任务的总时间中可被改进部分的时间所占的百分比 即可被改进部分占用时间 改进前整个任务的执行时间 记为Fe 它总小于1 2 改进部分采用改进措施后比没有采用改进措施前性能提高的倍数 即改进前改进部分执行时间 改进后改进部分执行时间 记为Se 例1 假设将某系统的某一部件的处理速度加快到10倍 但该部件的原处理时间仅为整个运行时间的40 则整个系统的性能提高了多少 解 Fe 0 4 Se 10 例2 采用哪种实现技术来求浮点数平方根FPSQR的操作对系统的性能影响较大 假设FPSQR操作占整个测试程序执行时间的20 一种实现方法是采用FPSQR硬件 使FPSQR操作的速度加快到10倍 另一种方法是使所有浮点数据指令的速度加快 使FP指令的速度加快到2倍 还假设FP指令占整个执行时间的50 请比较这两种设计方案 解 Fe FPSQR 0 2 Se FPSQR 10 Fe FP 0 5 Se FP 2 Amdahl law又称为固定规模加速比模型 问题规模不随处理机变化而变化 固定问题规模 看用并行技术能达到的最短时间是多少 在固定规模加速比模型下 负载和执行时间随系统中处理机数目n变化的情况如下图 Ws Wp Ws Wp Ws Wp Ws Wp Workload N 1 2 3 4 固定负载 执行时间随N增加而减少 固定负载加速比模型下的负载和执行时间情况 当处理器数目n 1024 加速比Sn随 变化的情况如下 得出曲线如下图 91 Sn 1024 48 31 24 10 可以比较不同的 对加速比带来的不同影响 0时得到理想加速比 当 值增加时 加速比性能急剧下降 结论 加速比曲线随 的上升急剧下降 原因是存在顺序部分Ws 无法用增加系统的处理机数目来解决 这一性质在过去二十年间给人们造成了对并行处理非常悲观的印象 影响 两种意见 1 劝阻制造商生产大规模并行计算机 2 研究并行编译器 以降低 的值 从而提高系统的性能 固定负载加速比模型的可能应用范围 对时间要求严格的应用问题 2 固定时间加速比性能模型 Gustafsun定律有许多应用领域强调精度而不是运行时间 1988年 Gustafsun提出了固定时间加速比模型 当机器的规模扩大时 解题的规模也随着扩大 从而得到更加精确的解 而使运行时间保持不变 比如 有限元方法做结构分析 流体动力学做天气预报解PDE 偏微分方程组 就需要提高精度 粗格要求的计算量较少 而细格的计算量多 得到的精确度也较高 天气预报模拟求解四维PDE 如果使每个实际方向 X Y Z 的格点距离减少10倍 并以同一幅度增加时间步 那么可以说格点增加了104倍 因而工作负载也至少增大了10000倍 模型提出的背景 固定负载模型有缺陷 因为Amdahl law中 取决于问题及并行编译器的效率 无法描述系统固有的特性 加速比的公式 其中 Wp nWp和Ws Wp Ws Wp n作为固定时间的条件 Ws Wp n表示在扩大负载后在增加处理机台数的情况下的平均负载 执行时间 它应当和负载没有扩大情况下的平均负载 执行时间 Ws Wp相等 即有Ws Wp Ws Wp n 同时 负载的串行部分并没有改变 即有Ws Ws 在固定时间加速比模型下 负载和执行时间随系统中处理机数目n变化的情况如下图 Ws Wp Ws Wp Ws Wp Ws Wp Workload N 1 2 3 4 Ts Tp 2 Ts Tp 3 Ts Tp 4 并行负载不断增加 执行时间固定 固定时间加速比模型下的负载和执行时间情况 增大问题规模的办法使所有处理机保持忙碌状态 在问题扩大到与可用的计算能力匹配时 程序中的顺序部分就不再是瓶颈了 当处理器数目n 1024 加速比Sn随 变化的情况如下 Sn 1024 1014 1004 993 983 3 受限于存储器的加速比模型1993年 由Sun和Ni提出 大型科学计算和工程设计需要较大的存储空间 许多应用问题是存储器受限 而不是CPU受限或者I O受限 比如 在分布存储系统中常遇到 总存储容量随节点数线性增加 许多节点集合起来解一个大题 基本思想 要在存储空间有限条件下解尽可能大的问题 这同样需要扩展工作负载 才能提供较高的加速比 较高的精度和较好的资源利用率 加速比可以表示如下 其中 在单个处理机上顺序执行的工作负载与问题的规模或系统的规模无关 即 而G n 反映的是存储容量增加n倍时并行工作负载增加的倍数 讨论 1 G n 1 即为固定负载的情况 2 G n n 即存储器增加n倍 负载也增加n倍 为固定时间的情形 3 G n n 计算负载的增加情况比存储器增加快 会有较高的加速比 比较三种加速比 对于相同的处理机数量 有 在受限于存储器的加速比模型下 负载和执行时间随系统中处理机数目n变化的情况如下图 Ws Wp Ws Wp Ws Wp Ws Wp Workload N 1 2 3 4 Ts Tp 1 Ts Tp 2 Ts Tp 3 Ts Tp 4 规模扩展的工作负载 执行时间稍有增加 受限于存储器的加速比模型下的负载和执行时间情况 例 n维矩阵乘法 A B C 其中A B C都是n n的方阵 为得到C的每一个元素需要进行n次乘法 n次加法 所以总的计算量为 n n n2 2n3 需要的存储量为3n2 两个源矩阵 一个结果矩阵 如果n台计算机组成多计算机系统 则存储容量扩大n倍 那么矩阵的维数 原来为n 也可以增加了 设为N倍 那么加速比为多少 解 存储容量变为 nM n 3n2 3n3 而N维需要的存储量为3N2 计算量变为2N3 则有 4 并行计算的应用模型随机器规模的增大 工作负载增长的模式如下图 工作负载 问题规模 n 指数 线性 亚线性 常数 上图中 采用受限于存储器的加速比模型中给出的公式 曲线对应的G n n1 5 曲线对应的G n n 曲线对应的G n 0 5n 曲线对应的G n 1则有加速比公式 给定一个程序 假设Ws Wp 0 4 那么效率为 并行计算机的应用模型如下图 通信界限 存储器界限 受限于存储器模型 工作负载 问题规模 机器规模 固定负载模型 固定时间模型 第一章加速比性能模型与可扩展性分析 1 3可扩展性分析1 3 1可扩展性1 3 2可扩展性分析 1 3可扩展性分析 1 3 1可扩展性1 可扩展性与可编程性 增加可扩展性 增加可编程性 分布存储的消息传递型多计算机 共享存储型多处理机 理想并行计算机 2 可扩展性指标机器规模 n 时钟频率 f 问题规模 s CPU时间 T I O需求 d 存储容量 m 通信开销 h 计算机价格 c 程序设计开销 p 3 可扩展性的直观定义对任意数量 n 的处理机和任意规模 s 的问题 若所有算法的系统效率E 1 则系统是可扩展的 4 规模可扩展性系统性能随处理机数量线性增长 包括 处理速度和效率存储速度和容量互连带宽和时延I O速度和容量软件开销规模可扩展性与空间局部性 时间局部性以及部件瓶颈都有关系 例子 CrayY MP 16台处理机范围可伸缩CM 2 8K 64K台处理机范围可伸缩CM 5 1024 16K台处理机范围可伸缩KSR 1 8 1088台处理机范围可伸缩 5 换代 时间 可扩展性对系统各部分更换成新技术后 性能随之易扩展 要求算法 S W均能兼容运行 6 问题可扩展性问题规模扩大时 系统仍能很好的运行 或说问题规模扩展到很大时 系统能在给定粒度下高效运行 1 3 2可扩展性1 恒等效率概念 Isoefficiency 恒等效率定义为一个并行算法在并行计算机上实现时 为保持效率E固定所需的工作负载与机器规模n的相对关系 设 W W s 为工作负载 h h s n 为通信开销 它随s n增加而增大 其中 s为问题规模 n为机器规模 则效率可以表示为 问题的关键在于W s 与h s n 之间的相对增长速度 机器规模一定 开销h的增长比工作负载W要慢 因而 对一定规模的机器来说 效率会随问题规模增大而提高 所以 假若工作负载W随机器规模适当增加 那么就有希望保持效率不变 对于已知的算法来说 为了保持恒定的效率 工作负载W可能需要对n以多项式或指数规律增长 不同的算法可能需要不同的工作负载增长速率以便在n增加时保持效率不致下降 一般并行算法的恒定效率函数是n的多项式函数 即它们为O nk k 1 n的幂越小 并行系统的可扩展性越大 系统包括算法和结构的组合 2 恒等效率函数并行程序执行时间Tp T1 T0 p 其中 T1为总工作负载串行执行时间 T0为多节点总通信延时 p为节点数 那么 加速比为 而T1 Wtc W为以操作次数计算的总工作负载 tc为每个