高等计算机体系结构第5章

1第五章工作负载驱动的性能评价2第一节性能指标和测量一、基本性能指标1、机器参数结点参数：CPU速度、主频、存储系统（主存大小、页大小、Cache大小、块大小、关联度等）等；通信系统参数：互连网络参数(占用度、网络距离、带宽)、启动延迟、传送粒度、通信模型；系统参数：结点数。2、程序参数问题规模、工作负载、负载不平衡开销、通信/计算、并行度、数据访问模式、工作集尺寸、通信开销、并行开销、同步开销等。33、系统性能指标系统性能靠程序反映，分绝对性能和性能可扩展性两部分。执行时间)()()()log2(0ntntwnttnwTpcfn处理速度Pn=w/Tn吞吐率：单位时间内处理作业的数量利用率Un=Pn/[n(t0(n)+αwtc(n))]性能/价格：处理速度与购买价格的比可扩展性：性能随问题规模、处理器数、机器参数的加速比趋势。对程序而言还有下列性能：顺序执行时间、并行执行时间、加速比、效率。影响因素：程序参数、机器参数，以及他们之间的相互作用产生的影响。4二、如何评价系统性能性能评价目的：评价实际机器性能、推断设计是否合理（如机器特性对系统性能的影响）、探索可能的折中方案。1、评价性能方法模拟：通过软件方法对系统进行评价。内容：编写模拟器、选择工作负载、模拟结果分析与评价。测量：通过实际测量方法对系统进行评价。内容：选择工作负载及参数，在固定和变化PE数的情况下运行程序，测量性能。52、评价性能内容用测试程序进行测试，测试程序可为实际程序。系统绝对性能：机器的分离性能--执行不同的微测试程序；机器的总体性能—执行不同的宏测试程序。并行性产生的性能改善：机器的可扩展性—在可改变机器参数及工作负载时，执行相同程序，分析机器特性对系统性能的影响。系统比较：性能相对性—在不同的机器上，执行算法最优的相同程序。63、基准测试程序类型名称测量范围微基准程序LINPACK数值计算（线性代数）LMBENCHUnix中的系统调用和数据移动STREAM存储器带宽宏基准程序NAS并行计算（CFD）PARKBENCH并行计算SPEC混合基准测试程序Splash并行计算STAP信号处理TPC商业应用注意：基准测试程序只是全部测试程序的一部分；基准测试程序不能有效反映可扩展性。74、对测试程序要求测试程序应能够覆盖整个应用领域，即选择多个有代表性的问题进行编程；测试程序应保证工作负载呈现足够的并发性和负载平衡，以真实地反映系统的性能；测试程序的算法、数据结构、数据的规划和分布、通信和同步的协调应最优化，负载应平衡，使编程不影响系统性能；测试程序的问题规模应能够覆盖系统结构的各方面，以实现公正的评价，和对系统分离性能的评价。8第二节可扩展性和加速比分析一、考虑扩展性的原因1、问题规模的不确定性问题规模：指特定问题的输入配置，通常用参数向量表示。应与机器规模相适应，才能准确反映并行性带来的性能。问题规模太大：单处理机上不能运行，无法测量性能；系统呈超线性加速，性能失真。问题规模太小：多处理机通信开销失衡，性能失真。用户需求变化：应能根据机器参数特性改变配置，取得良好性能。92、机器规模的可变化性机器规模：是刻画结点的处理性能、存储结构等的向量。问题规模只有与处理器数量和机器规模相匹配，才能取得最佳性能。增加机器规模：解决更大问题或更快解决相同问题。机器规模与问题规模的匹配：不同问题规模的特性对机器规模的要求不同，如存储结构。3、可扩展研究研究问题规模、处理器数量、机器规模三者关系，及在不同需求时的最佳扩展方法。10二、扩展模型与加速比的测量可扩展性分类：面向用户扩展、面向资源扩展。面向资源扩展：固定负载扩展(PC)、固定时间扩展(TC)、固定存储器扩展(MC)。1、Amdahl定律：固定负载目的：使高频部分更快，解决顺序瓶颈。设：工作负载W=αW+(1-α)W，n个PE的固定负载加速比：1)1(1)/)(1(nnn→∞时Amdahl定律含义：对给定工作负载，最大加速比为1/α；为获得好的加速比，应使顺序瓶颈α尽可能小；应设法使较大（使用频率高）部分执行得更快。11W1WnW1WnW1WnW1WnW1WnW1Wnn工作负载123456(a)固定负载T1TnT1TnT1TnT1TnT1TnT1Tnn执行时间(b)减少执行时间123456α加速比Sn1024×0%1%2%3%4%91×48×31×24×1023110241024S©固定负载的加速比结论：顺序瓶颈无法单纯用增加处理器数量来解决。引入开销后的固定负载加速比：WTWnTnnTn)1(1)/)(1(000当n→∞时注意：程序性能受限于顺序瓶颈和平均开销。122、Gustafson定律：固定时间目的：提高并行性，缓解顺序瓶颈。设：扩大后的工作负载W’=αW+(1-α)nW，n个PE的固定时间加速比：nSWnWWn)1()1(Gustafson定律含义：若扩展工作负载以维持固定时间，则固定时间加速比是n的线性函数；工作负载扩展到与可扩展计算能力相匹配时，顺序部分便不再成为瓶颈。Gustafson定律成立的关键：顺序部分αW不变，并行化部分从(1-α)W扩展到(1-α)nW。13W1WnW1WnW1WnW1WnW1WnW1Wnn工作负载123456(a)规模扩展的负载T1Tnn执行时间(b)固定执行时间123456T1TnT1TnT1TnT1TnT1Tnα加速比Sn1024×0%1%2%3%4%1014×1004×993×983ש固定时间的加速比Sn=1024-1023α引入开销后的固定时间加速比：WTnTWnWWnS/1)1()1(00注意：平均开销T0也是n的函数，T0随n而增加，应控制其增长的幅度，以取得线性加速比。14工作负载扩放注意点：是工作负载线性扩放，非问题规模线性扩放；问题规模向量中各部分的平衡性。问题规模的扩放方法：用基于应用的解析表达式扩放各参数：通过算法分析，推导出问题规模向量中各参数间关系。参数之间的实际关系和扩放规则，依赖于应用的领域。运行串行程序，测量机器操作形式的工作量来扩放：在单处理器上运行程序，计算出扩放操作的数量；逐个改变问题规模参数，得出参数的最佳近似关系。注意：要消除所有扩展带来的人为因素的开销（如高速缓存扑空）或操作，否则测量数据不准确。153、Sun和Ni定律：固定存储器目的：最大限度利用CPU能力和存储器容量，提高性能。设：扩大后的工作负载W’=αW+(1-α)G(n)W，n个PE（存储器总容量为nM）的存储器受限加速比：nnGnGnWnGWWnGWnS/)()1()()1(/)()1()()1(有三种特殊情况：a.G(n)=1时，相当于固定负载的情况，该加速比与Amdahl定律等效；b.G(n)=n时，相当于固定时间的情况，即存储器扩大n倍时工作负载扩大n倍，该加速比与Gustafson定律一致；c.G(n)＞n时，相当于工作负载的增长存储器增长快的情况，该加速比比固定负载加速比、固定时间加速比都高。16W1WnW1WnW1WnW1WnW1WnW1Wnn工作负载123456(a)规模扩展的负载T1Tnn执行时间(b)执行时间稍增123456T1TnT1TnT1TnT1TnT1Tnα加速比Sn1024×0%1%2%3%4%1016×1007×999×991ש存储器受限的加速比25.025.112791280nS引入开销后的固定存储器加速比：WTnnGnGTnWnGWWnGWnS//)()1()()1(/)()1()()1(00如果可用的存储器得到了充分利用，固定时间加速比和固定存储器加速比非常接近。17加速比定律比较：相同处理器数量时，三种加速比曲线如右图。Snn固定存储器加速比固定时间加速比固定负载加速比加速比定律应用：若用户目标是减少固定工作负载的执行时间，则系统的可扩展性定义为受Amdahl定律支配的加速比；若用户目标是随机器规模扩大的问题规模扩大，则系统的可扩展性定义为受Sun和Ni定律支配的加速比；若用户目标是随机器规模扩大的问题规模扩大，但执行时间不超过顺序执行时间，则系统的可扩展性定义为受Gustafson定律支配的加速比。184、工作负载增长的可扩展性分析（1）工作负载增长模式与效率曲线1101001000工作负载（问题规模）机器规模nα(常数)Β（亚线性)γ（线性)δ（指数)1101001000效率机器规模nαΒγδ10.5α通信/计算很大，效率最差，不追求效率时可扩展性最好；γ最理想（W与n线性关系），效率较好，可扩展性较好；β比γ略差，可扩展性较好；δ效率虽好，但可扩展性差（会超过MEM、I/O界限）。返回20页19（2）负载增长模式的可扩展性α模式扩展：采用Amdahl定律（固定负载模型）扩展；工作负载（问题规模）机器规模n固定负载模型通信界限存储器界限αδγ模式扩展：采用Gustafson定律（固定时间模型）扩展；固定时间模型γβ模式（含α至γ之间）扩展：采用Gustafson定律（固定时间模型）扩展；γ至δ间扩展：采用Sun和Ni定律（固定存储器模型）扩展。固定存储器模型205、等性能模型目的：在小系统上推导可扩展函数，预测大系统性能。分类：等效率模型、等速度模型、等利用率模型。（1）恒等效率),()()(nshsWsWE效率：效率固定值越小，W(s)对h(s,n)的限制越小；效率固定值越小，扩大机器规模时，需要增加的负载越小。转18页恒等效率：并行系统运行时，为保持E固定所需的工作负载W和机器规模n的相对关系。具有较小恒等效率的系统比具有较大恒等效率的系统有更好的可扩展性。21（2）恒等效率函数),(),()(1nshCnshsWEE其中C为常数对等式W(s)=C×h(s,n)求解方程，得s=y(n)。恒等效率函数：))(()(nyWnfE恒等函数值越小，当机器增大规模时，为保持恒等效率所需增加的工作负载就越小，具有更好的可扩展性。22例：两个N×N矩阵相乘，W(s)=cN3，A、B两系统运行时间分别为、，比较E分别保持1/3和1/4时哪个系统具有更好的可扩展性。nbNcN/23)2/(223nbNcN(1)E=1/3时，对A系统有，即等效率函数为对B系统，等效率函数为322/cNnbN)2/(ncbN5.13)]2/([)(ncbcnfE5.13)]2/([)(ncbcnfE当E保持1/3时，A、B两系统具有相同的可扩展性。(2)E=1/4时，对A系统有，即等效率函数为对B系统，等效率函数为323/cNnbN)3/(ncbN5.13)]3/([)(ncbcnfE5.13)]4/([)(ncbcnfE当E保持1/4时，B系统比A系统具有更好的可扩展性。23第三节评价实际机器时的问题规模一、选择问题规模目标：使固有行为特征对体系结构有足够的覆盖性；限制所需要的不同问题规模的数量。1、确定问题规模范围根据用户对问题规模的要求，确定问题规模的最小值。2、确定覆盖问题固有特征的问题规模不同问题有不同的固有特征，基本上都具有通信/计算、负载平衡与通信的特征。选择覆盖固有特性的问题规模进入问题规模集中。对通信/计算：根据固有的通信/计算和网络流量确定；对负载平衡与通信：根据两者变化趋势确定。243、确定覆盖工作集的问题规模应选择覆盖工作集两侧情况的问题规模到问题规模集中。4、确定覆盖存储分配粒度的问题规模应选择覆盖存储分配粒度两侧情况的问题规模到问题规模集中。问题规模集应覆盖通信/计算、负载平衡和通信、工作集、存储分配粒度几方面的要求。25二、改变机器规模目标：为评价系统的可扩展性而选择问题规模扩放的起点。1、从固定数量处理机评价的问题规模开始问题规模选择：小、中、大三种；问题规模与三种扩展模型相结合（问题可向上或向下扩展），构成9种扩展曲线。2、从单处理机的问