第二章 加速比性能模型与可扩展性分析.ppt

第2章：加速比性能模型和可扩展性分析，2.1加速比性能分析，2.1.1一般概念，2.1.2加速比，2.1.3三个加速比性能模型，2.2可扩展性分析，2.1加速比性能模型，2.1一般概念，1。处理器时间产品处理器号和处理时间产品，用于测量这些处理器在运行期间的资源利用率。如果一个程序在P个处理器上运行时间为Tp，那么在Tp间隔内P个处理器完成的最大作业数为TP * P。处理器的实际工作曲线与时间的积分可视为这些处理器的有效工作负荷。效率是有效工作量与最大工作量的比率。并行度并行度是指在一定时间间隔内，用来执行一个程序的处理器数量。3.并行度分布图当执行一个给定的程序时，DOP对时间的分布图。DOP和相应时间间隔的乘积是处理器要完成的工作或工作量。下图显示了并行度分布图。DOP，t1，t，t2，平行度分布图，2.1.2加速比1。绝对加速比比较最佳串行算法和并行算法。定义一个(特定于机器)将最佳串行算法在一个表上的运行时间与并行算法在N个表上的运行时间进行比较。定义2(不考虑具体的机器)比较最快的顺序机器上的最佳串行算法的执行时间和并行机器上的并行算法的执行时间。2.相对加速比同一并行算法在单个节点上的运行时间与由多个相同节点组成的处理器系统的运行时间之比。这个定义着重于描述算法和并行计算机本身的可伸缩性。线性加速比：中间开销低，通信量少，超线性加速比的弱耦合计算：应用需要大内存时可能出现病态加速比：加速比下降，可能是计算量太小。2.1.3三种加速比性能模型：1。固定负载加速比性能模型阿姆达尔定律在许多实时应用领域，计算负载大小通常是固定的。在并行机中，这种负载可以分配给多个并行机执行，获得的加速比称为固定负载加速比。问题的负载可以表示如下：W=Ws Wp，其中Ws表示问题中不可并行的串行部分负载，Wp表示可并行的部分负载。那么在n个节点的情况下，加速度比可以表示如下：让串联因子是串联部分的比例。换句话说，代入得到Amdahllaw:不管使用多少个处理器，可以达到的最佳加速比：效率en可以表示为：处理器n越多，效率En越低。阿姆达尔定律告诉我们，由于对系统中的某个组件采用更快的执行模式而导致的整个系统性能的提高，与该执行模式的使用频率或总执行时间的比例有关。加速度比的两个决定因素：1。计算机执行某项任务的总时间中可改进的时间百分比，即改进部分可占用的时间/改进前整个任务的执行时间，记录为Fe，该值始终小于1。2.采用改进措施后的改进部分的性能比未采用改进措施前提高了数倍，即改进前的改进部分的执行时间/改进后的改进部分的执行时间记录为Se。例1:假设某个系统的某个部分的处理速度提高到10倍，但该部分原来的处理时间只占整个运行时间的40%，那么整个系统的性能提高了多少？解决方案：Fe=0.4，Se=10，示例2:使用哪种实现技术来找到浮点数的平方根FPSQR对系统性能有很大影响。假设FPSQR操作占整个测试程序执行时间的20%。一种实现方法是使用fpqr硬件将fpqr操作速度提高到10倍。另一种方法是加快所有浮点数据指令的速度，并将浮点指令的速度提高一倍。还假设FP指令占总执行时间的50%。请比较这两种设计在固定比例加速模式下，系统的负载和执行时间随处理器数n而变化，如下图所示：ws，WP，ws，WP，workload，n，1，2，3，4，固定负载，执行时间随n的增加而减少，在固定负载加速模式下，当处理器数n=1024时，加速比s n随的变化如下：91，s n，1024，444可以比较不同对加速比的不同影响：当=0时获得理想的加速比，当值增大时加速比性能急剧下降。结论：加速度比曲线随着的增加而急剧下降，因为存在一个连续的部分Ws，这不能通过增加系统中处理器的数量来解决。在过去的20年里，这种性质给人们留下了并行处理的非常悲观的印象。影响：两种意见：1。阻止制造商生产大规模并行计算机。2.研究并行编译器，降低值，提高系统性能。指定负载加速比模型的可能应用范围：具有严格时间要求的应用问题。2.固定时间加速比性能模型古斯塔夫逊定律有许多应用领域，强调在运行时的精确性。1988年，古斯塔夫逊提出了一个固定时间加速比模型。当机器的规模扩大时，解决问题的规模也会扩大，从而在保持运行时间不变的情况下获得更精确的解决方案。例如，结构分析采用有限元方法，天气预报和偏微分方程求解采用流体动力学方法，精度有待提高。粗网格需要较少的计算，而细网格需要更多的计算，从而导致更高的精度。天气预报模拟用于求解四维偏微分方程。如果每个实际方向(x，y，z)上的网格距离减少了10倍，并且时间步长增加了相同的幅度，那么网格点可以说增加了104倍，因此工作量也增加了至少10，000倍。该模型的背景是固定负载模型有缺陷：因为阿姆达尔定律中的依赖于并行编译器的问题和效率，不能描述系统的固有特性。加速度比公式：其中Wp=nWp，Ws Wp=Ws Wp/n是固定时间的条件。Ws Wp/n表示在扩展负载后增加处理机器数量的情况下的平均负载(执行时间)，它应该等于在不扩展负载的情况下的平均负载(执行时间)Ws Wp。存在wswp=ws wp/n，同时，负载的串行部分没有改变，即Ws=Ws 。在固定时间加速模式下，负载和执行时间随系统中处理器数量的变化而变化，如下图所示：ws、WP、ws、WP、ws、WP、workload、n、1、2、3、4、ts、TP、2、ts、TP、3、ts、TP、4，并行负载持续增加，执行时间固定，固定时间加速模式下的负载和执行时间不变。问题越大，所有处理器就越忙，当问题扩展到与可用计算能力相匹配时，程序的顺序部分就不再是瓶颈。当处理器数量n=1024时，加速度比s n随变化如下：Sn，1024，1014，1004，993，983，3。孙和倪于1993年提出了一种记忆限制加速比模型。大规模科学计算和工程设计需要大的存储空间，许多应用问题是内存限制，而不是CPU限制或I/O限制。例如，在分布式存储系统中，经常会遇到总存储容量随节点数量线性增加的情况，许多节点聚集在一起解决一个大问题。基本思想：为了在有限的存储空间下解决尽可能大的问题，还需要扩展工作负载以提供更高的加速比、更高的精度和更好的资源利用率。加速比可以表示如下：其中：在单个处理器上顺序执行的工作负载与问题的规模或系统的规模无关，即：并且G(n)反映了当存储容量增加n倍时并行工作负载增加的倍数。讨论：1。G(n)=1，即固定负载的情况；2.G(n)=n，即存储器增加n倍，负载也增加n倍，这是固定时间的情况；3.G(n)n，计算量的增加比比较三种加速比，对于相同数量的处理器，有：在内存限制的加速比模型下，负载和执行时间随着系统中处理器数量的变化而变化，如下图所示：ws，WP，ws，WP，WP，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)=1.5曲线对应于G(n)=n曲线对应于G(n)=0.5n曲线对应于G(n)=1具有加速度比公式：给定一个程序，假设Ws/Wp=0.4，那么效率为：对应的处理器数-效率曲线如下：效率，n，(指数)，(线性)，(次线性)，(常数)，结论：1。如果工作量(问题规模)保持不变，那么效率E随着机器规模的增加而迅速降低，因为成本H的增加比机器规模快。为了将效率保持在一定水平，我们可以按比例增加机器规模和问题规模。2.如果工作负载呈指数级增长，并且效率需要保持不变，或者加速比需要保持良好，则问题规模必须急剧增加，这将超过内存或输入/输出限制，而问题规模只允许在计算机内存的可用限制内增长。并行计算机的应用模型如下：通信限制、内存限制、受内存模型限制、工作负载(问题规模)、机器规模、固定负载模型、固定时间模型、第2章加速性能模型和可伸缩性分析、2.1加速性能分析、2.2可伸缩性分析、2.2.1可伸缩性分析、2.2.2可伸缩性分析、2.2可伸缩性分析、2.2.1可伸缩性1。可扩展性和可编程性，提高可扩展性，提高可编程性，分布式存储消息传递多计算机，共享存储多处理器，理想的并行计算机，2。可扩展性指标机器规模时钟频率问题规模处理器时间输入输出要求存储容量通信开销计算机价格编程开销3。可伸缩性的直观定义对于任何数量(N)的处理器和任何大小(S)的问题，如果所有算法的系统效率E=1，则系统是可伸缩的。可扩展性系统性能随着处理器数量的增加而线性增加，包括处理速度和效率存储速度和容量互连带宽和延迟输入/输出速度和容量软件开销可扩展性与空间局部性、时间局部性和组件瓶颈有关。示例：Cray-MP:16处理器可扩展CM-2: 8K-64K处理器可扩展CM-5: 1024-16K处理器可扩展KSR:1:8-1088处理器可扩展。5.代(时间)可扩展性在系统的所有部分被新技术取代后，性能将很容易扩展，需要算法和软件的兼容操作。问题可伸缩性当问题规模扩大时，系统仍然可以很好地运行，或者当问题规模扩大到大规模时，系统可以在给定的粒度下有效地运行。2.2.2可扩展性1。等效率(Isoefficiency)等效率定义为当并行算法在并行计算机上实现时，保持效率不变所需的工作量和机器规模之间的相对关系。假设：瓦=瓦(s)是工作负载，h=小时(s，n)是通信开销，它随着s和n的增加而增加。其中s是问题规模，n是机器规模。那么效率可以表述为：问题的关键在于W(s)和h(s，n)之间的相对增长率。机器的大小是固定的，成本的增加比工作量的增加慢。因此，对于一定规模的机器，效率将随着问题规模的增加而增加。因此，如果工作负荷W随着机器的尺寸适当增加，则希望效率保持不变。对于已知的算法，为了保持恒定的效率，工作负荷W可能需要通过多项式或指数规则增加n。不同的算法可能需要不同的工作负载增长率，以防止效率随着n的增加而降低。一般并行算法的常数效率函数是n的多项式函数，即它们是O(nk)、k1。n的幂越小，并行系统的可伸缩性越强(该系统包括算法和结构的组合)。2。恒定效率函数并行程序执行时间Tp=(T1 T0)/p，其中T1是总工作负载串行执行时间，T0是总多节点通信延迟，而P是节点数。然后，加速比是：T1=Wtc，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个处理器网格和超立方体计算机上