清华大学计算机科学与技术系高性能计算研究所 郑纬民 教授 2007年9月 计算机科学与技术系研究生课程 高等计算机系统结构 清华大学计算机科学与技术系高性能计算研究所 郑纬民 教授 2007年9月

高等计算机系统结构 第一章 高等计算机的核心技术——并行处理 第二章 加速比性能模型与可扩展性分析 第三章 互连与通信 第四章 划分与调度 第一章 高等计算机的核心技术——并行处理 第二章 加速比性能模型与可扩展性分析 第三章 互连与通信 第四章 划分与调度 第五章 并行存储器系统 第六章 Cache Coherence 第七章 Memory Consistency 第八章 指令级并行处理 第九章 微处理器设计与实现方法 第十章 网格计算

高等计算机系统结构 第十一章 DSM 第十二章 传感器网络 第十三章 对等计算 第十四章 海量网络存储器 第十五章 多核CPU技术 第十二章 传感器网络 第十三章 对等计算 第十四章 海量网络存储器 第十五章 多核CPU技术 第十六章 可信计算系统 第十七章 虚拟化技术 第十八章 基于集群的海量数据处理

第二章 加速比性能模型与可扩展性分析 2.1 加速比性能分析 2.2 可扩展性分析 2.1.1 一般概念 2.1.2 加速比 第二章 加速比性能模型与可扩展性分析 2.1 加速比性能分析 2.1.1 一般概念 2.1.2 加速比 2.1.3 三种加速比性能模型 2.2 可扩展性分析

2.1 加速比性能模型 2.1.1 一般概念 1.处理机—时间积 处理机数目与处理时间的乘积用以度量这些处理机运行时的资源利用率。 若一程序在P台处理机上运行的时间为Tp，则此P台处理机在Tp时间间隔内完成的工作最大数量为Tp * P。 可将处理机实际工作曲线对时间的积分看成是这些处理机完成的有效工作量。 效率为有效工作量与最大工作量之比。

2.并行度（Degree Of Parallelism—DOP） 3.并行性分布图 执行一个给定的程序时DOP对时间的分布图。 DOP与对应时间的间隔之积即为处理机要完成的工作或工作负载。 下图所示为一个并行性分布图。

DOP t1 t2 t 并行性分布图

2.1.2 加速比 1. 绝对加速比 将最好的串行算法与并行算法相比较. 定义一（与具体机器有关）将最好的串行算法在一台上的运行时间与并行算法在N台运行的时间相比。 定义二（与具体机器无关）将最好的串行算法在最快的顺序机上的执行时间与并行算法在并行机上的运行时间相比。

2.相对加速比 同一并行算法在单节点上运行时间与在多个相同节点构成的处理机系统上的运行时间之比。 这种定义侧重于描述算法和并行计算机本身的可扩展性。 线性加速比：中间开销小，通信少，弱耦合计算 超线性加速比：当应用需要大内存时可能出现 病态加速比：加速比递减，可能是计算量太小

2.1.3 三种加速比性能模型 1.固定负载加速比性能模型—Amdahl定律 在许多实时应用领域，计算负载的大小常固定。在并行机中，此负载可分布至多台并行执行，获得的加速比称为fixed-load speedup。一个问题的负载可表示如下： 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变化的情况如下图：

固定负载加速比模型下的负载和执行时间情况 Workload Execution Time N Ws Ws Ws Ws Ts Tp 1 Wp Wp Wp Wp Ts Tp 2 Ts Tp 3 Ts Tp 4 1 2 3 4 N 固定负载 执行时间随N增加而减少 固定负载加速比模型下的负载和执行时间情况

当处理器数目n=1024，加速比Sn随α变化的情况如下： 得出曲线如下图： Sn 1024 91 48 31 10 24 α

可以比较不同的α对加速比带来的不同影响： α =0 Sn n α =0.01 α =0.1 α =0.9 α=0时得到理想加速比，当α值增加时，加速比性能急剧下降。

结论：加速比曲线随α的上升急剧下降，原因是存在顺序部分Ws，无法用增加系统的处理机数目来解决。这一性质在过去二十年间给人们造成了对并行处理非常悲观的印象。 影响：两种意见： 1.劝阻制造商生产大规模并行计算机。 2.研究并行编译器，以降低α的值，从而提高系统的性能。 规定负载加速比模型的可能应用范围： 对时间要求严格的应用问题。

2.固定时间加速比性能模型—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变化的情况如下图： Workload Execution Time N Ws Ts Tp 1 Ts Ts Ts Ws Wp Tp Tp Tp Ws Wp Ws Wp Wp 1 2 3 4 2 3 4 N 并行负载不断增加 执行时间固定 固定时间加速比模型下的负载和执行时间情况

增大问题规模的办法使所有处理机保持忙碌状态，在问题扩大到与可用的计算能力匹配时，程序中的顺序部分就不再是瓶颈了。 当处理器数目n=1024，加速比Sn随α变化的情况如下： Sn’ 1014 1024 993 1004 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 Workload Execution Time N Wp Ws Ts Wp Ts Ws Tp Ts Ts Tp Wp Tp Ws Tp Wp 1 2 3 4 1 2 3 4 N 规模扩展的工作负载 执行时间稍有增加 受限于存储器的加速比模型下的负载和执行时间情况

例： 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，那么效率为：

相应的处理器数目—效率曲线如下图： θ （指数） 效率 γ （线性） β （亚线性） α （常数） n

结论： 1.如果工作负载（问题规模）保持不变，那么效率E随机器规模的增大而迅速下降，其原因是开销h比机器规模增加得快，为了使效率保持在一定的水平上，我们可以按比例增大机器规模和问题规模。 2.如果工作负载按指数增长模式，效率要保持恒定或保持良好的加速比，必须使问题规模猛增才行，这样就会超过存储器或I/O限制，而问题规模只允许在计算机存储器可用的限度以内增长。

并行计算机的应用模型如下图： 工作负载 （问题规模） 受限于存储器模型 存储器界限 固定时间模型 通信界限 固定负载模型 机器规模

第二章 加速比性能模型与可扩展性分析 2.1 加速比性能分析 2.2 可扩展性分析 2.2.1 可扩展性 2.2.2 可扩展性分析

2.2 可扩展性分析 2.2.1 可扩展性 1.可扩展性与可编程性 增加 理想并行计算机 可扩展性 分布存储的消息 传递型多计算机 共享存储型 多处理机 增加可编程性

2.可扩展性指标 机器规模（n） 时钟频率（f） 问题规模（s） CPU时间（T） I/O需求（d） 存储容量（m） 通信开销（h）

3.可扩展性的直观定义 对任意数量（n）的处理机和任意规模（s）的问题，若所有算法的系统效率 E = 1， 则系统是可扩展的。

4.规模可扩展性 系统性能随处理机数量线性增长，包括： 处理速度和效率 存储速度和容量 互连带宽和时延 I/O速度和容量 软件开销 规模可扩展性与空间局部性、时间局部性以及部件瓶颈都有关系。 例子： Cray Y-MP：16台处理机范围可伸缩 CM-2： 8K-64K台处理机范围可伸缩 CM-5： 1024-16K台处理机范围可伸缩 KSR-1： 8-1088台处理机范围可伸缩

5.换代（时间）可扩展性 6.问题可扩展性 对系统各部分更换成新技术后，性能随之易扩展，要求算法、S/W均能兼容运行。 问题规模扩大时，系统仍能很好的运行，或说问题规模扩展到很大时，系统能在给定粒度下高效运行。

2.2.2 可扩展性 1.恒等效率概念（Isoefficiency） 设: 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 = W tc，W为以操作次数计算的总工作负载，tc为每个操作的平均执行时间。

如前面所述，工作负载W与开销h均可以表示成n与s的函数，所以，效率也可以表示如下： 为了使E保持不变，工作负载W（s）应该与开销h(s,n)成比例增长，由此可以得出以下条件：

如果工作负载W(s)与fE(n)一样快的增长，那么已知算法结构组合就能使效率保持恒定。 这个结论和前面的结论是一致的。 此时， W(s)与fE(n)是相同的，只要求出了W(s)的数量级，就可知道fE(n)了。为了得到恒等效率，只要使W(s)与h(s,n)同一个数量级就可以了。

例1： 矩阵乘法的W(s) = O（s3）（其中s为维数），还设 h（s，n）= O（nlogn+s2n0.5）。求fE(n) 。 解： 要满足W与h同数量级的条件，需要在两式中选出大的：

例2： W(s) = O（s3）， h（s，n）= O（nlogn+s2n1/3logn）。求fE(n) 。 解： 比较两个式子，选出较大的：

例3： W(s) = O（s3）， h（s，n）= O（nlogn+s3）。求fE(n) 。 解： 第二个式子显然成立，故

例4：在n台处理机网格和超立方体计算机上分别计算1维s点的FFT，其工作负载W(s) = O（slogs），已知： 超立方体计算机上：h1（s，n）= O（nlogn+slogn）， 网格计算机上：h2（s，n）= O（nlogn+sn0.5）， 问哪一种扩展性好？ 解：对超立方体计算机， 对网格计算机，

为了得到恒等效率，对网格计算机，它的负载必须以指数增长，而超立方体的负载的增长不超过多项式增长速度， 结论：超立方体具有更好的可扩展性。 对于相同的效率E，设k = 2，它们的机器规模-问题规模曲线可能如下图所示： 问题规模s 网格 超立方体 机器规模n