高级体系结构-2资料.ppt

Amdahl’law又称为固定规模加速比模型，问题规模不随处理机变化而变化。固定问题规模，看用并行技术能达到的最短时间是多少。 在固定规模加速比模型下，负载和执行时间随系统中处理机数目n变化的情况如下图： Ws Wp Ws Wp Ws Wp Ws Wp Workload N 1 2 3 4 Execution Time N Ts Tp 1 Ts Tp 2 Ts Tp 3 Ts Tp 4 固定负载 执行时间随N增加而减少 固定负载加速比模型下的负载和执行时间情况 当处理器数目n=1024，加速比Sn随α变化的情况如下： 得出曲线如下图： 91 Sn α 1024 48 31 24 10 可以比较不同的α对加速比带来的不同影响： α =0 Sn n α =0.01 α =0.1 α =0.9 α=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 Execution Time N Ts Tp 1 Ts Tp 2 Ts Tp 3 Ts Tp 4 并行负载不断增加 执行时间固定 固定时间加速比模型下的负载和执行时间情况 增大问题规模的办法使所有处理机保持忙碌状态，在问题扩大到与可用的计算能力匹配时，程序中的顺序部分就不再是瓶颈了。 当处理器数目n=1024，加速比Sn随α变化的情况如下： Sn’ α 1024 1014 1004 993 983 3.受限于存储器的加速比模型 1993年，由Xian-he Sun和Lionel Ni将Amdahl和Gustafson定律一般化，提出了存储受限加速比模型 大型科学计算和工程设计需要较大的存储空间，许多应用问题是存储器受限，而不是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 Execution Time N Ts Tp 1 Ts Tp 2 Ts Tp 3 Ts Tp 4 规模扩展的工作负载 执行时间稍有增加 受限于存储器的