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

并行处理与体系结构;第3章 性能指标和基准程序;?5 并行程序性能;一、性能指标 1.前言 设顺序程序C由一串A个分计算阶段C1，C2，…Ck所组成 DOPi是并行性 下图给出了一个阶段并行程序;5;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∞。 这些不等式在估计并行执行时间时很有用。; 下表基于阶段并行模型性能的一些指标： ;12;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)；;15;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;21;22;23;从上表和图可见，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=30209 对于每Mflop计算，平均的通信开销为: 1／30209=33μs;也可将执行时间作为工作负载。 那么平均颗粒度变为 W/T0=14.37/0.0479=300  因此平均而言，对于每秒通信，256个结点共完成300s计算， 或对于每秒通信，每个结点完成300／256=1．17s计算。 ;二、基准程序中的可用并行性 关于并行成分的讨论 应用程序中潜在并行性有很宽的范围。 工程和科学代码具有数据并行性，有很高的