第一章 加速比.ppt

高等计算机系统结构高等计算机系统结构课程介绍高等计算机系统结构课程概述高性能计算机简介（TOP500）第一章加速比性能模型与可扩展性分析1.1计算机的发展变化及影响体系结构的因素1.1.1计算机发展历程1.1.2影响影响体系结构的因素1.1.3计评价算机性能3.性能的比较和总结
评价一台计算机的性能既是简单又是复杂的
（1）不同程序对机器的性能的不确定性；
（2）不同输入的不确定性；1.1加速比性能模型2.并行度（DegreeOfParallelism—DOP）
并行度（DOP）是在一定时间间隔内执行一个程序所用的处理机的数目。
3.并行性分布图
执行一个给定的程序时DOP对时间的分布图。
DOP与对应时间的间隔之积即为处理机要完成的工作或工作负载。
下图所示为一个并行性分布图。DOP1.1.2加速比
1.绝对加速比
将最好的串行算法与并行算法相比较.
定义一（与具体机器有关）将最好的串行算法在一台上的运行时间与并行算法在N台运行的时间相比。
定义二（与具体机器无关）将最好的串行算法在最快的顺序机上的执行时间与并行算法在并行机上的运行时间相比。2.相对加速比
同一并行算法在单节点上运行时间与在多个相同节点构成的处理机系统上的运行时间之比。
这种定义侧重于描述算法和并行计算机本身的可扩展性。1.1.3三种加速比性能模型设串行因子α为串行部分所占的比例。即效率En可以表示为：加速比的两个决定因素：
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当处理器数目n=1024，加速比Sn随α变化的情况如下：可以比较不同的α对加速比带来的不同影响：结论：加速比曲线随α的上升急剧下降，原因是存在顺序部分Ws，无法用增加系统的处理机数目来解决。这一性质在过去二十年间给人们造成了对并行处理非常悲观的印象。
影响：两种意见：
1.劝阻制造商生产大规模并行计算机。
2.研究并行编译器，以降低α的值，从而提高系统的性能。
固定负载加速比模型的可能应用范围：
对时间要求严格的应用问题。 2.固定时间加速比性能模型—Gustafsun定律
有许多应用领域强调精度而不是运行时间。1988年，Gustafsun提出了固定时间加速比模型。当机器的规模扩大时，解题的规模也随着扩大，从而得到更加精确的解，而使运行时间保持不变。
比如：有限元方法做结构分析，流体动力学做天气预报解PDE(偏微分方程组）就需要提高精度。
粗格要求的计算量较少，而细格的计算量多，得到的精确度也较高。天气预报模拟求解四维PDE，如果使每个实际方向（X，Y，Z）的格点距离减少10倍，并以同一幅度增加时间步，那么可以说格点增加了104倍，因而工作负载也至少增大了10000倍。
模型提出的背景：
固定负载模型有缺陷：因为Amdahl’law中，α取决于问题及并行编译器的效率，无法描述系统固有的特性。
加速比的公式：在固定时间加速比模型下，负载和执行时间随系统中处理机数目n变化的情况如下图： 增大问题规模的办法使所有处理机保持忙碌状态，在问题扩大到与可用的计算能力匹配时，程序中的顺序部分就不再是瓶颈了。
当处理器数目n=1024，加速比Sn随α变化的情况如下： 3.受限于存储器的加速比模型
1993年，由Sun和Ni提出。
大型科学计算和工程设计需要较大的存储空间，许多应用问题是存储器受限，而不是CPU受限或者I/O受限。
比如：在分布存储系统中常遇到，总存储容量随节点数线性增加，许多节点集合起来解一个大