哈尔滨工业大学计算机科学与技术学院 1
并行处理与体系结构
哈尔滨工业大学计算机科学与技术学院 2
第 3章 性能指标和基准程序
??1 系统和应用的基准程序
??2 性能和成本
??3 基本性能指标
??4 并行计算机性能
??5 并行程序性能
??6 可扩展性和加速比分析
哈尔滨工业大学计算机科学与技术学院 3
?5 并行程序性能
说明,
1,讨论有关并行应用的一些性能问
题和性能指标
2,提出的所有性能指标，有通用性
哈尔滨工业大学计算机科学与技术学院 4
?一、性能指标
?1.前言
? 设顺序程序 C由一串 A个分计算阶段 C1，
C2,… Ck所组成
?DOPi是并行性
? 下图给出了一个阶段并行程序
哈尔滨工业大学计算机科学与技术学院 5
哈尔滨工业大学计算机科学与技术学院 6
2.基本指标
?从语义上讲，上图有顺序执行的
?步 Ci计算的工作负载，如上图示
?可求总并行性开销
哈尔滨工业大学计算机科学与技术学院 7
?当在 n个处理器上执行工作负载时，
步 Ci并行执行时间,
Tn(i)=T1(i)/ n
?在 n个结点上总的并行执行时
间为,
哈尔滨工业大学计算机科学与技术学院 8
? 3.极值指标
① 存在几个极值指标以给出 Pn,Tn和
Sn的下限和上限。设 T∞ 是关键路
径的长度，有,
哈尔滨工业大学计算机科学与技术学院 9
② 使得 Tn=T∞ 的 n最小值称为最大并
行性，记为 Nmax。 可由
Nmax=max1≤j ?k(DOPi)计算该指标。
③ 持续加速比 Pn的最大值 P∞ =W／ T
∞ 是它的上限。
④ N个结点执行时间 Tn的下限值为
T1／ n和 T∞ 。 Tn≥max(T 1/n,T∞ )
哈尔滨工业大学计算机科学与技术学院 10
⑤ 平均并行性 T1/T∞, 是加速比的上限。
即 Sn≤T 1/Tn。
⑥ Brent已证明，若不计所有并行性和
交互开销,Tn受限于下列不等式,
T1/n≤ Tn ? T1/n+T∞
⑦ 将 Tn≥max(T 1/n,T∞ )代入可得,
max(T1/n,T∞ )≤ Tn ? T1/n+T∞ 。
? 这些不等式在估计并行执行时间时
很有用。
哈尔滨工业大学计算机科学与技术学院 11
?下表基于阶段并行模型性能的一
些指标,
哈尔滨工业大学计算机科学与技术学院 12
哈尔滨工业大学计算机科学与技术学院 13
?4.例题,STP中 APT基准程序
?为便于理解,STAP基准程序组中
的 APT程序可描述如下,
?其中变量 N为问题参数。记号 [.]
?变量 house是一个含有约 80KB信息
的矩阵，与 N无关
哈尔滨工业大学计算机科学与技术学院 14
? For(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)；
哈尔滨工业大学计算机科学与技术学院 15
哈尔滨工业大学计算机科学与技术学院 16
?5.例题：并行 APT基准测试程序的
性能指标
哈尔滨工业大学计算机科学与技术学院 17
? 假设条件,
① 每个计算步的工作负载由上图 (STP中
APT图 ）中值求得，以单 SP2结点的 Mflop
和执行时间表示。 并行性开销忽略不计 。
② 在忽略不计所有通信开销情况下，来预
测性能指标的极端值，称其为 0_开销预
测。
③ 一个粗粒度阶段并行算法，参数 N=256。
哈尔滨工业大学计算机科学与技术学院 18
?由上图可知最大并行性为,
max(8192,1,256,256)=8192
?总工作负载 W=1447Mflop；
?顺序执行时间 T1=14,37s；
?关键路径为
哈尔滨工业大学计算机科学与技术学院 19
?求得最大性能值
?P∞ =W/T∞ =1447/0.08=18087Mflop
／ s,
?而平均并行性为
T1/T∞ =14,37/0.08=180。
哈尔滨工业大学计算机科学与技术学院 20
?6.例题：估计 APT基准测试程序中
的交互开销
?可用上述表的表达式来估计运行
在 SP2上的并行 APT程序的交互开
销。交互开销是 3种通信的和：
T=Tcomp+Tpar+Tinteract
哈尔滨工业大学计算机科学与技术学院 21
哈尔滨工业大学计算机科学与技术学院 22
哈尔滨工业大学计算机科学与技术学院 23
哈尔滨工业大学计算机科学与技术学院 24
?从上表和图可见,16.7/n2MB的全
交换开销为,
?Tindex=80logn+0.03n1.29mμ s=0.00
008logn+0.5n-0.71秒
?广播开销的表达式
为,Tbcast=52logn+(0.029logn)
mμ s=0.00237logn秒
哈尔滨工业大学计算机科学与技术学院 25
? 归约 n个 flop数所需时间为：
20logn+23μ s；
? 其中由 n个结点中的每一个提供一个
flop数。在 APT图 的归约步中，组合
了 n个目标报告，每个有 100个 flop数。
可保守地评估归约开销,
Treduce=100(20logn+23)μ s=0.002log
n+0.0023秒
哈尔滨工业大学计算机科学与技术学院 26
? 那么总的交互开销为,
? T0=Tinteract=0.5n-0.71+ 0.00445logn+
0.0023； 有以下说明,
① 并行处理中的一个观念是通信开销
随所使用结点数的增加而增长。但
由上面例子可见，这可能是错的。
② 在 APT程序中当所使用结点不多于
256时，总的通信开销随机器规模增
加而减少。
哈尔滨工业大学计算机科学与技术学院 27
? 7.例题,APT基准测试程序期望执行时间
? 来预测并行 APT算法在 n<256结点的 SP2上
的执行时间。并计算当 n=256时的平均颗
粒度。
? 使用 n个结点的总执行时间为,
?T=Tcomp+Tpar+Tinteract
=14.33/n+0.5n-0.71+ 0.00445logn +
0.0423
哈尔滨工业大学计算机科学与技术学院 28
? 单 SP2结点的总工作负载
W=1447Mflop或 14,37s。
? 平均颗粒度为,
W/T0=1447M/0.0479=30209
? 对于每 Mflop计算，平均的通信开销
为,
1／ 30209=33μ s
哈尔滨工业大学计算机科学与技术学院 29
? 也可将执行时间作为工作负载。
? 那么平均颗粒度变为
? W/T0=14.37/0.0479=300
? 因此平均而言，对于每秒通信,256个结
点共完成 300s计算,
? 或对于每秒通信，每个结点完成 300／
256=1,17s计算。
哈尔滨工业大学计算机科学与技术学院 30
?二、基准程序中的可用并行性
?关于并行成分的讨论
?应用程序中潜在并行性有很宽的范
围。
?工程和科学代码具有数据并行性，
有很高的 DOP 。
哈尔滨工业大学计算机科学与技术学院 31
? 数据的并行,
? Kumar(1988年 )已报导过密集计算代码在理想
环境下于每个时钟内可并发地执行 500到 3500
个算术操作。
? 指令级并行,
? 要低得多。 Wall指出指令级并行性的极限约
在 5左右，很少超过 7。
? Bulter等 (1991年 )曾报道过当去除所有约束
时，在某些科学程序中 lLP可超过每周期 17条
指令。
哈尔滨工业大学计算机科学与技术学院 32
? 某些程序跟踪结果指出，如果体系结构
和编译器能完满地工作，则在 一个合理
设计的超标量处理器 上，可期待的 lLP
为每周期并发执行 2.0到 5.8条指令。
? 下表中为 PERFECT基准测试程序组中
12个程序中的每一个给出了其平均
并行性。
哈尔滨工业大学计算机科学与技术学院 33
哈尔滨工业大学计算机科学与技术学院 34
?例题,3个 STAP基准测试程序性能
?下表中示出了使用最小、最大和名
义数据集时,STAP基准测试程序组
中 3个程序的某些性能指标。
?其中的输入数据规模和工作负载由
STAP基准测试程序规范给定。
哈尔滨工业大学计算机科学与技术学院 35
哈尔滨工业大学计算机科学与技术学院 36
?以上可用并行性的测量表明,
?非数值计算的相对并行性很小。
?编译器优化和算法的重新设计可增
加应用中的可用并行性，但对基本
块的有限并行性的抽取使得一般程
序中的潜在并行性因子被限制在 2到
5之间。
?使用多处理器同时地开发科学代码
中的 DOP值。
哈尔滨工业大学计算机科学与技术学院 37
?总结,
?讨论了并行程序
?基本性能
?一些有用的指标 。
并行处理与体系结构
哈尔滨工业大学计算机科学与技术学院 2
第 3章 性能指标和基准程序
??1 系统和应用的基准程序
??2 性能和成本
??3 基本性能指标
??4 并行计算机性能
??5 并行程序性能
??6 可扩展性和加速比分析
哈尔滨工业大学计算机科学与技术学院 3
?5 并行程序性能
说明,
1,讨论有关并行应用的一些性能问
题和性能指标
2,提出的所有性能指标，有通用性
哈尔滨工业大学计算机科学与技术学院 4
?一、性能指标
?1.前言
? 设顺序程序 C由一串 A个分计算阶段 C1，
C2,… Ck所组成
?DOPi是并行性
? 下图给出了一个阶段并行程序
哈尔滨工业大学计算机科学与技术学院 5
哈尔滨工业大学计算机科学与技术学院 6
2.基本指标
?从语义上讲，上图有顺序执行的
?步 Ci计算的工作负载，如上图示
?可求总并行性开销
哈尔滨工业大学计算机科学与技术学院 7
?当在 n个处理器上执行工作负载时，
步 Ci并行执行时间,
Tn(i)=T1(i)/ n
?在 n个结点上总的并行执行时
间为,
哈尔滨工业大学计算机科学与技术学院 8
? 3.极值指标
① 存在几个极值指标以给出 Pn,Tn和
Sn的下限和上限。设 T∞ 是关键路
径的长度，有,
哈尔滨工业大学计算机科学与技术学院 9
② 使得 Tn=T∞ 的 n最小值称为最大并
行性，记为 Nmax。 可由
Nmax=max1≤j ?k(DOPi)计算该指标。
③ 持续加速比 Pn的最大值 P∞ =W／ T
∞ 是它的上限。
④ N个结点执行时间 Tn的下限值为
T1／ n和 T∞ 。 Tn≥max(T 1/n,T∞ )
哈尔滨工业大学计算机科学与技术学院 10
⑤ 平均并行性 T1/T∞, 是加速比的上限。
即 Sn≤T 1/Tn。
⑥ Brent已证明，若不计所有并行性和
交互开销,Tn受限于下列不等式,
T1/n≤ Tn ? T1/n+T∞
⑦ 将 Tn≥max(T 1/n,T∞ )代入可得,
max(T1/n,T∞ )≤ Tn ? T1/n+T∞ 。
? 这些不等式在估计并行执行时间时
很有用。
哈尔滨工业大学计算机科学与技术学院 11
?下表基于阶段并行模型性能的一
些指标,
哈尔滨工业大学计算机科学与技术学院 12
哈尔滨工业大学计算机科学与技术学院 13
?4.例题,STP中 APT基准程序
?为便于理解,STAP基准程序组中
的 APT程序可描述如下,
?其中变量 N为问题参数。记号 [.]
?变量 house是一个含有约 80KB信息
的矩阵，与 N无关
哈尔滨工业大学计算机科学与技术学院 14
? For(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)；
哈尔滨工业大学计算机科学与技术学院 15
哈尔滨工业大学计算机科学与技术学院 16
?5.例题：并行 APT基准测试程序的
性能指标
哈尔滨工业大学计算机科学与技术学院 17
? 假设条件,
① 每个计算步的工作负载由上图 (STP中
APT图 ）中值求得，以单 SP2结点的 Mflop
和执行时间表示。 并行性开销忽略不计 。
② 在忽略不计所有通信开销情况下，来预
测性能指标的极端值，称其为 0_开销预
测。
③ 一个粗粒度阶段并行算法，参数 N=256。
哈尔滨工业大学计算机科学与技术学院 18
?由上图可知最大并行性为,
max(8192,1,256,256)=8192
?总工作负载 W=1447Mflop；
?顺序执行时间 T1=14,37s；
?关键路径为
哈尔滨工业大学计算机科学与技术学院 19
?求得最大性能值
?P∞ =W/T∞ =1447/0.08=18087Mflop
／ s,
?而平均并行性为
T1/T∞ =14,37/0.08=180。
哈尔滨工业大学计算机科学与技术学院 20
?6.例题：估计 APT基准测试程序中
的交互开销
?可用上述表的表达式来估计运行
在 SP2上的并行 APT程序的交互开
销。交互开销是 3种通信的和：
T=Tcomp+Tpar+Tinteract
哈尔滨工业大学计算机科学与技术学院 21
哈尔滨工业大学计算机科学与技术学院 22
哈尔滨工业大学计算机科学与技术学院 23
哈尔滨工业大学计算机科学与技术学院 24
?从上表和图可见,16.7/n2MB的全
交换开销为,
?Tindex=80logn+0.03n1.29mμ s=0.00
008logn+0.5n-0.71秒
?广播开销的表达式
为,Tbcast=52logn+(0.029logn)
mμ s=0.00237logn秒
哈尔滨工业大学计算机科学与技术学院 25
? 归约 n个 flop数所需时间为：
20logn+23μ s；
? 其中由 n个结点中的每一个提供一个
flop数。在 APT图 的归约步中，组合
了 n个目标报告，每个有 100个 flop数。
可保守地评估归约开销,
Treduce=100(20logn+23)μ s=0.002log
n+0.0023秒
哈尔滨工业大学计算机科学与技术学院 26
? 那么总的交互开销为,
? T0=Tinteract=0.5n-0.71+ 0.00445logn+
0.0023； 有以下说明,
① 并行处理中的一个观念是通信开销
随所使用结点数的增加而增长。但
由上面例子可见，这可能是错的。
② 在 APT程序中当所使用结点不多于
256时，总的通信开销随机器规模增
加而减少。
哈尔滨工业大学计算机科学与技术学院 27
? 7.例题,APT基准测试程序期望执行时间
? 来预测并行 APT算法在 n<256结点的 SP2上
的执行时间。并计算当 n=256时的平均颗
粒度。
? 使用 n个结点的总执行时间为,
?T=Tcomp+Tpar+Tinteract
=14.33/n+0.5n-0.71+ 0.00445logn +
0.0423
哈尔滨工业大学计算机科学与技术学院 28
? 单 SP2结点的总工作负载
W=1447Mflop或 14,37s。
? 平均颗粒度为,
W/T0=1447M/0.0479=30209
? 对于每 Mflop计算，平均的通信开销
为,
1／ 30209=33μ s
哈尔滨工业大学计算机科学与技术学院 29
? 也可将执行时间作为工作负载。
? 那么平均颗粒度变为
? W/T0=14.37/0.0479=300
? 因此平均而言，对于每秒通信,256个结
点共完成 300s计算,
? 或对于每秒通信，每个结点完成 300／
256=1,17s计算。
哈尔滨工业大学计算机科学与技术学院 30
?二、基准程序中的可用并行性
?关于并行成分的讨论
?应用程序中潜在并行性有很宽的范
围。
?工程和科学代码具有数据并行性，
有很高的 DOP 。
哈尔滨工业大学计算机科学与技术学院 31
? 数据的并行,
? Kumar(1988年 )已报导过密集计算代码在理想
环境下于每个时钟内可并发地执行 500到 3500
个算术操作。
? 指令级并行,
? 要低得多。 Wall指出指令级并行性的极限约
在 5左右，很少超过 7。
? Bulter等 (1991年 )曾报道过当去除所有约束
时，在某些科学程序中 lLP可超过每周期 17条
指令。
哈尔滨工业大学计算机科学与技术学院 32
? 某些程序跟踪结果指出，如果体系结构
和编译器能完满地工作，则在 一个合理
设计的超标量处理器 上，可期待的 lLP
为每周期并发执行 2.0到 5.8条指令。
? 下表中为 PERFECT基准测试程序组中
12个程序中的每一个给出了其平均
并行性。
哈尔滨工业大学计算机科学与技术学院 33
哈尔滨工业大学计算机科学与技术学院 34
?例题,3个 STAP基准测试程序性能
?下表中示出了使用最小、最大和名
义数据集时,STAP基准测试程序组
中 3个程序的某些性能指标。
?其中的输入数据规模和工作负载由
STAP基准测试程序规范给定。
哈尔滨工业大学计算机科学与技术学院 35
哈尔滨工业大学计算机科学与技术学院 36
?以上可用并行性的测量表明,
?非数值计算的相对并行性很小。
?编译器优化和算法的重新设计可增
加应用中的可用并行性，但对基本
块的有限并行性的抽取使得一般程
序中的潜在并行性因子被限制在 2到
5之间。
?使用多处理器同时地开发科学代码
中的 DOP值。
哈尔滨工业大学计算机科学与技术学院 37
?总结,
?讨论了并行程序
?基本性能
?一些有用的指标 。
