并行程序性能课件

1

并行程序性能说明：讨论有关并行应用的一些性能问题和性能指标提出的所有性能指标，有通用性2一、性能指标1.前言设顺序程序C由一串A个分计算阶段C1，C2，…Ck所组成DOPi是并行性下图给出了一个阶段并行程序342.基本指标从语义上讲，上图有顺序执行的步Ci计算的工作负载，如上图示可求总并行性开销5当在n个处理器上执行工作负载时，步Ci并行执行时间：Tn(i)=T1(i)/n在n个结点上总的并行执行时间为：

63.极值指标

存在几个极值指标以给出Pn、Tn和Sn的下限和上限。设T∞是关键路径的长度，有：7使得Tn=T∞的n最小值称为最大并行性，记为Nmax。可由Nmax=max1≤j

k(DOPi)计算该指标。持续加速比Pn的最大值P∞=W／T∞是它的上限。N个结点执行时间Tn的下限值为T1／n和T∞。Tn≥max(T1/n,T∞

)8平均并行性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∞。这些不等式在估计并行执行时间时很有用。9下表基于阶段并行模型性能的一些指标：10114.例题：STP中APT基准程序

为便于理解，STAP基准程序组中的APT程序可描述如下：其中变量N为问题参数。记号[.]变量house是一个含有约80KB信息的矩阵，与N无关12For(j=0；j<N；j++)for(k=0；k<32；k++)fft(data[.][j][k])；ht(data[1][.][.]，house)；for(i=0；i<N；i++)bf(data[i][.][.],housedetect[i][.])For(j=0；j<N；j++)for(i=0；i<N；i++)td(detect[i][j]，target_report)；13145.例题：并行APT基准测试程序的性能指标15假设条件：每个计算步的工作负载由上图(STP中APT图）中值求得，以单SP2结点的Mflop和执行时间表示。并行性开销忽略不计。在忽略不计所有通信开销情况下，来预测性能指标的极端值，称其为0_开销预测。一个粗粒度阶段并行算法，参数N=256。16由上图可知最大并行性为:max(8192，1，256，256)=8192总工作负载W=1447Mflop；顺序执行时间T1=14．37s；关键路径为17求得最大性能值P∞=W/T∞=1447/0.08=18087Mflop／s，而平均并行性为T1/T∞=14．37/0.08=180。186.例题：估计APT基准测试程序中的交互开销可用上述表的表达式来估计运行在SP2上的并行APT程序的交互开销。交互开销是3种通信的和：T=Tcomp+Tpar+Tinteract19202122从上表和图可见，16.7/n2MB的全交换开销为：Tindex=80logn+0.03n1.29mμs=0.00008logn+0.5n-0.71秒广播开销的表达式为:Tbcast=52logn+(0.029logn)mμs=0.00237logn秒23归约n个flop数所需时间为：20logn+23μs；其中由n个结点中的每一个提供一个flop数。在APT图的归约步中，组合了n个目标报告，每个有100个flop数。可保守地评估归约开销：Treduce=100(20logn+23)μs=0.002logn+0.0023秒24那么总的交互开销为：T0=Tinteract=0.5n-0.71+0.00445logn+0.0023；有以下说明：并行处理中的一个观念是通信开销随所使用结点数的增加而增长。但由上面例子可见，这可能是错的。在APT程序中当所使用结点不多于256时，总的通信开销随机器规模增加而减少。257.例题：APT基准测试程序期望执行时间来预测并行APT算法在n<256结点的SP2上的执行时间。并计算当n=256时的平均颗粒度。使用n个结点的总执行时间为：T=Tcomp+Tpar+Tinteract=14.33/n+0.5n-0.71+0.00445logn+0.042326单SP2结点的总工作负载W=1447Mflop或14．37s。平均颗粒度为:W/T0=1447M/0.0479=30209对于每Mflop计算，平均的通信开销为:1／30209=33μs27也可将执行时间作为工作负载。那么平均颗粒度变为W/T0=14.37/0.0479=300

因此平均而言，对于每秒通信，256个结点共完成300s计算，或对于每秒通信，每个结点完成300／256=1．17s计算。28二、基准程序中的可用并行性关于并行成分的讨论应用程序中潜在并行性有很宽的范围。工程和科学代码具有数据并行性，有很高的DOP。29数据的并行：Kumar(1988年)已报导过密集计算代码在理想环境下于每个时钟内可并发地执行500到3500个算术操作。指令级并行：要低得多。Wall指出指令级并行性的极限约在5左右，很少超过7。Bulter等(1991年)曾报道过当去除所有约束时，在某些科学程序中lLP可超过每周期17条指令。30某些程序跟踪结果指出，如果体系结构和编译器能完满地工作，则在一个合理设计的超标量处理器上，可期待的lLP为每周期并发执行2.0到5.8条指令。下表中为PERFECT基准测试程序组中12个程序中的每一个给出了其平均并行性。

3132例题：3个STAP基准测试程序性能下表中示出了使用最小、最大和名义数据集时，STAP基准测试程序组中3个程序的某些性能指标。其中的输入数据规模和工作负载由STAP基准测试程序规范给定。333