第3章_性能指标和基准程序 第5节 基本性能指标 并行处理与体系结构教学课件.pptVIP

哈尔滨工业大学计算机科学与技术学院 并行处理与体系结构 第3章 性能指标和基准程序 ?1 系统和应用的基准程序 ?2 性能和成本 ?3 基本性能指标 ?4 并行计算机性能 ?5 并行程序性能 ?6 可扩展性和加速比分析 ?5 并行程序性能 说明： 讨论有关并行应用的一些性能问题和性能指标 提出的所有性能指标，有通用性 一、性能指标 1.前言 设顺序程序C由一串A个分计算阶段C1，C2，…Ck所组成 DOPi是并行性 下图给出了一个阶段并行程序 2.基本指标 从语义上讲，上图有顺序执行的 步Ci计算的工作负载，如上图示 可求总并行性开销 当在n个处理器上执行工作负载时，步Ci并行执行时间： Tn(i)=T1(i)/ n 在n个结点上总的并行执行时间为： 3.极值指标 存在几个极值指标以给出Pn、Tn和Sn的下限和上限。设T∞是关键路径的长度，有： 使得Tn=T∞的n最小值称为最大并行性，记为Nmax。 可由Nmax=max1≤j?k(DOPi)计算该指标。 持续加速比Pn的最大值P∞=W／T ∞是它的上限。 N个结点执行时间Tn的下限值为 T1／n和T∞。Tn≥max(T1/n, T∞ ) 平均并行性T1/T∞，是加速比的上限。即Sn≤T1/Tn。 Brent已证明，若不计所有并行性和交互开销，Tn受限于下列不等式： T1/n≤ Tn? T1/n+T∞ 将Tn≥max(T1/n, T∞ )代入可得： max(T1/n ,T∞)≤ Tn ? T1/n+T∞。 这些不等式在估计并行执行时间时很有用。 下表基于阶段并行模型性能的一些指标： 4.例题：STP中APT基准程序 为便于理解，STAP基准程序组中的APT程序可描述如下： 其中变量N为问题参数。记号[.] 变量house是一个含有约80KB信息的矩阵，与N无关 For(j=0；jN；j++) for(k=0；k32；k++) fft(data[.][j][k])； ht(data[1][.][.]，house)； for(i=0；iN；i++) bf(data[i][.][.],housedetect[i][.]) For(j=0；jN；j++) for(i=0；iN；i++) td(detect[i][j]，target_report)； 5.例题：并行APT基准测试程序的性能指标 假设条件： 每个计算步的工作负载由上图(STP中APT图）中值求得，以单SP2结点的Mflop和执行时间表示。并行性开销忽略不计。 在忽略不计所有通信开销情况下，来预测性能指标的极端值，称其为0_开销预测。 一个粗粒度阶段并行算法，参数N=256。 由上图可知最大并行性为: max(8192，1，256，256)=8192 总工作负载W=1447Mflop； 顺序执行时间T1=14．37s； 关键路径为 求得最大性能值 P∞=W/T∞=1447/0.08=18087Mflop／s， 而平均并行性为T1/T∞=14．37/0.08=180。 6.例题：估计APT基准测试程序中的交互开销 可用上述表的表达式来估计运行在SP2上的并行APT程序的交互开销。交互开销是3种通信的和：T=Tcomp+Tpar+Tinteract 从上表和图可见，16.7/n2MB的全交换开销为： Tindex=80logn+0.03n1.29mμs=0.00008logn+0.5n-0.71秒 广播开销的表达式为:Tbcast=52logn+(0.029logn) mμs=0.00237logn秒 归约n个flop数所需时间为：20logn+23μs； 其中由n个结点中的每一个提供一个flop数。在APT图的归约步中，组合了n个目标报告，每个有100个flop数。可保守地评估归约开销： Treduce=100(20logn+23)μs=0.002logn+0.0023秒 那么总的交互开销为： T0=Tinteract=0.5n-0.71+ 0.00445logn+ 0.0023； 有以下说明： 并行处理中的一个观念是通信开销随所使用结点数的增加而增长。但由上面例子可见，这可能是错的。 在APT程序中当所使用结点不多于256时，总的通信开销随机器规模增加而减少。 7.例题：APT基准测试程序期望执行时间 来预测并行APT算法在n256结点的SP2上的执行时间。并计算当n=256时的平均颗粒度。 使用n个结点的总执行时间为： T=Tcomp+Tpar+Tinteract =14.33/n+0.5n-0.71+ 0.00445logn + 0.0423 单SP2结点的总工作负载W=1447Mflop或14．37s。 平均颗粒度为: W/T0=1447M/0.0479=302