哈尔滨工业大学计算机科学与技术学院 1
并行处理与体系结构
哈尔滨工业大学计算机科学与技术学院 2
第 3章 性能指标和基准程序
??1 系统和应用的基准程序
??2 性能和成本
??3 基本性能指标
??4 并行计算机性能
??5 并行程序性能
??6 可扩展性和加速比分析
哈尔滨工业大学计算机科学与技术学院 3
?4 并行计算机性能
?针对一个并行系统，需讨论计算
和开销特征
一、计算特征
?下表给出了 3种商品化并行计算
机系列的性能参数的历史值
哈尔滨工业大学计算机科学与技术学院 4
哈尔滨工业大学计算机科学与技术学院 5
?存储器层次结构,
① 存储器容量
② 存储器时延
③ 存储器带宽
?1996年前后计算机中这 3个参数
的典型值
哈尔滨工业大学计算机科学与技术学院 6
哈尔滨工业大学计算机科学与技术学院 7
? 二、并行性和通信开销
? 并行程序中的开销可分为 3类
① 负载不平衡开销；
② 并行性开销；
③ 通信开销 (包括同步、通信和聚集 )。
T=Tcomp+Tpar+Tinteract
哈尔滨工业大学计算机科学与技术学院 8
? 说明,
? 有 3种类型的并行性操作。它们是
并行性开销的来源,
? 进程管理；
? 分组操作
? 进程查询操作
哈尔滨工业大学计算机科学与技术学院 9
? 通信开销的来源有 3种类型的
操作
? 同步
? 聚集
? 通信
哈尔滨工业大学计算机科学与技术学院 10
? 巨大开销,
? 注意有关并行性和 通信 开销的两
个要点,
① 通常比基本计算时间要大得多,
② 在不同系统上变化很大。
哈尔滨工业大学计算机科学与技术学院 11
哈尔滨工业大学计算机科学与技术学院 12
哈尔滨工业大学计算机科学与技术学院 13
?三、开销定量化
1.问题的提出
?应对计算的并行性和 通信 开销
进行量化。
哈尔滨工业大学计算机科学与技术学院 14
2.开销测量条件
?进行测量实验的确切条件必须清
楚地加以说明。以下是部分列表,
?所使用的数据结构。
?所使用的编程语言、库以及编译器
选择。
?一般地，开销测量应以批处理方式
进行，都会被执行。
哈尔滨工业大学计算机科学与技术学院 15
?所使用的通信硬件和协议。因为
在这种方式下大多数生成路径
(production run)
?测量挂钟时间或是 CPU时间。一般
来讲，挂钟时间更有用。
哈尔滨工业大学计算机科学与技术学院 16
3.开销测量方法
? 虽然测量开销粗看起来非常简单，
但要获得精确测量结果却是很具
挑战性的任务
? 主要的原因有 3种
哈尔滨工业大学计算机科学与技术学院 17
① 乒乓方案,
? 是测量点对点通信常用的方法,
? 结点 0执行一个发送操作向结点 1
发送一个 m字节的消息，后者执行
一个接收操作收到此消息
? 结点 1立即发送相同消息给结点 0
哈尔滨工业大学计算机科学与技术学院 18
?例题：测量时延的乒乓方案,
for(i=0； i<Runs； i++)
? if(my_node_id==0){ /*发送方 */
? Tmp=Second()；
? start_time=Second()；
? 向结点 1发送一个 m字节消息；
? 从结点 1接收一个 m字节消息；
? end_time=Second()；
哈尔滨工业大学计算机科学与技术学院 19
?timer_overhead=start_time-tmp；
?total_time=end_time-start_time-
timer_overhead；
?communication_time[i]=total_time
／ 2；
?}else if(my_node_id==1){ /*接收
方 */
? 从结点 0接收一个 m字节消息；
? 向结点 0发送一个 m字节消息；
?}}
哈尔滨工业大学计算机科学与技术学院 20
② 热土豆 (hot_potato)方法 (也称
为救火队方法 )。
? 该方法面向 n个结点；
? 方法是个循环的发送接收。
哈尔滨工业大学计算机科学与技术学院 21
③ 集合通信
? 条件：设分布式存储器多计算机
中 n个结点中的每一个均执行以下
的 SPMD程序 。
? 使用路障来同步测量进程中的 异
步操作 。
哈尔滨工业大学计算机科学与技术学院 22
? for(i=0； i<Runs； i++ ){
? Barrier synchronization；
? Tmp=Second()；
? start_time=Second()；
? for(j=0； j<Iterations； j++)
The_collective_routine_being_meas
ured；
? End_time=Second()；
哈尔滨工业大学计算机科学与技术学院 23
?Timer_overhead=start_time-tmp；
?Total_time=end_time-start_time
–timer_overhead；
?Local_ time=total_time/
Iterations；
?Communication_time[i]=maxim
um Of all n local time values；
?}
哈尔滨工业大学计算机科学与技术学院 24
? 改用集合操作的通用化乒乓方法,
? for(i=0； i<Runs； i++){
? if(my_node_id==0){
? tmp=Second()；
? start_time=Second();
? 结点 0向所有 n个结点广播一个空消
息；
? For(j=0； i<Iterations； j++)
哈尔滨工业大学计算机科学与技术学院 25
? the collective_routine_ being_
measured；
? 所有结点向结点 0完成一个空归约；
if(my_node_id=0){
?end_time=Second()；
?timer_overhead=start_time-tmp；
?Communication_time[i]=end_time-
start_time- timer_overhead
?}
哈尔滨工业大学计算机科学与技术学院 26
4.开销表达式
? 经测量获得开销数据，有 3种表
示方法,
① 用表格来表示数据。
例如，下表给出了在 SP2上运行
专有 MPL通信库所测得的点对点
通信的定时结果。
哈尔滨工业大学计算机科学与技术学院 27
哈尔滨工业大学计算机科学与技术学院 28
② 以曲线来表示数据
? 如下图所示。
? 其优点是曲线可示出通信开
销增长趋向。
哈尔滨工业大学计算机科学与技术学院 29
哈尔滨工业大学计算机科学与技术学院 30
③ 表达式表示
? 例如，将所测得的定时数据用最小
二乘法适当地加以拟合。就可将 SP2
上的点对点通信开销表示成消息长
度的线性函数,
t=46+0.035mμ s
? 如果加以拟合，它与曲线之间的误
差是很小的，如上图所表明的那样。
哈尔滨工业大学计算机科学与技术学院 31
5.点对点通信表达式
?Hockney提出操作通信时间 (以 μ s
表示 )特征的 1个模型,
?其中的通信开销 t(m)是消息长度
m(以字节表示 )的线性函数,
t(m)=t0+m／ r∞
?式中 t0是以 μ s表示的启动时间，
而 r∞ 是渐近带宽，单位 MB／ s。
哈尔滨工业大学计算机科学与技术学院 32
? Hockney还引入了两个附加的参
数。
① 半峰值长度记为 m1/2字节，是达
到半渐近带宽所需的消息长度。
② 特殊性能，记为 ?0MB／ s，用来
表明短消息带宽。
哈尔滨工业大学计算机科学与技术学院 33
?4个参数 t0, r∞, m1/2, ?0
MB中的两个是独立的。
?另两个可用以下关系推得,
?t0 = m1/2 ／ r∞ =1/ ?0
?其中 m1/2是表示系统支持短消息
通信好坏程序的参数。
哈尔滨工业大学计算机科学与技术学院 34
?例如,
?SP2的 t(m)=46+0.035m。
?启动开销为 t0=46μ s；
?渐近带宽为,
r∞ =1／ 0.035=28.57MB／ s,
?以及半峰值消息长度为,
m1/2 = t0 × r∞ =1314字节。
哈尔滨工业大学计算机科学与技术学院 35
6.集合通信
?将式 Hockney表达式扩展成如下,
?通信开销 T(m,n)现改为是 m和 n两者的
函数。但启动时延仍只依赖于 n。
?渐近带宽变为 r∞ (n) 。
T(m,n)=t0(n)+m/r∞ (n)
哈尔滨工业大学计算机科学与技术学院 36
?在将测得的定时数据与不同的 t0(n)
和 r∞ (n)形式拟合
?可推得如表中所示的 4个集合操作
的公式
哈尔滨工业大学计算机科学与技术学院 37
哈尔滨工业大学计算机科学与技术学院 38
7.集合计算
① 测量了 3种代表性的集合计算操作：
路障、归约和扫描。它们拟合曲线
开销表达式如下表所示。
② 注意当处理器数超过 256时，路障开
销为 762μ s，相当于执行
762x266=202,692 flop所需的时间。
③ 现在可以回答这样问题，是否应使
用同步算法?
哈尔滨工业大学计算机科学与技术学院 39
哈尔滨工业大学计算机科学与技术学院 40
④ 短消息和长消息全交换开销的方法
作了比较,
? 在下图中示出了当 mn2=16MB(例如，
m=1024字节和 n=128)时两种表示方
法的相对误差。
? 结论：如图
哈尔滨工业大学计算机科学与技术学院 41
哈尔滨工业大学计算机科学与技术学院 42
?在下图，比较了当 mn2=64KB (例
如,m=4字节及 n=128)时,
?所测得的开销与由两种方法推测
所得的开销。
哈尔滨工业大学计算机科学与技术学院 43
哈尔滨工业大学计算机科学与技术学院 44
?本节结束！
并行处理与体系结构
哈尔滨工业大学计算机科学与技术学院 2
第 3章 性能指标和基准程序
??1 系统和应用的基准程序
??2 性能和成本
??3 基本性能指标
??4 并行计算机性能
??5 并行程序性能
??6 可扩展性和加速比分析
哈尔滨工业大学计算机科学与技术学院 3
?4 并行计算机性能
?针对一个并行系统，需讨论计算
和开销特征
一、计算特征
?下表给出了 3种商品化并行计算
机系列的性能参数的历史值
哈尔滨工业大学计算机科学与技术学院 4
哈尔滨工业大学计算机科学与技术学院 5
?存储器层次结构,
① 存储器容量
② 存储器时延
③ 存储器带宽
?1996年前后计算机中这 3个参数
的典型值
哈尔滨工业大学计算机科学与技术学院 6
哈尔滨工业大学计算机科学与技术学院 7
? 二、并行性和通信开销
? 并行程序中的开销可分为 3类
① 负载不平衡开销；
② 并行性开销；
③ 通信开销 (包括同步、通信和聚集 )。
T=Tcomp+Tpar+Tinteract
哈尔滨工业大学计算机科学与技术学院 8
? 说明,
? 有 3种类型的并行性操作。它们是
并行性开销的来源,
? 进程管理；
? 分组操作
? 进程查询操作
哈尔滨工业大学计算机科学与技术学院 9
? 通信开销的来源有 3种类型的
操作
? 同步
? 聚集
? 通信
哈尔滨工业大学计算机科学与技术学院 10
? 巨大开销,
? 注意有关并行性和 通信 开销的两
个要点,
① 通常比基本计算时间要大得多,
② 在不同系统上变化很大。
哈尔滨工业大学计算机科学与技术学院 11
哈尔滨工业大学计算机科学与技术学院 12
哈尔滨工业大学计算机科学与技术学院 13
?三、开销定量化
1.问题的提出
?应对计算的并行性和 通信 开销
进行量化。
哈尔滨工业大学计算机科学与技术学院 14
2.开销测量条件
?进行测量实验的确切条件必须清
楚地加以说明。以下是部分列表,
?所使用的数据结构。
?所使用的编程语言、库以及编译器
选择。
?一般地，开销测量应以批处理方式
进行，都会被执行。
哈尔滨工业大学计算机科学与技术学院 15
?所使用的通信硬件和协议。因为
在这种方式下大多数生成路径
(production run)
?测量挂钟时间或是 CPU时间。一般
来讲，挂钟时间更有用。
哈尔滨工业大学计算机科学与技术学院 16
3.开销测量方法
? 虽然测量开销粗看起来非常简单，
但要获得精确测量结果却是很具
挑战性的任务
? 主要的原因有 3种
哈尔滨工业大学计算机科学与技术学院 17
① 乒乓方案,
? 是测量点对点通信常用的方法,
? 结点 0执行一个发送操作向结点 1
发送一个 m字节的消息，后者执行
一个接收操作收到此消息
? 结点 1立即发送相同消息给结点 0
哈尔滨工业大学计算机科学与技术学院 18
?例题：测量时延的乒乓方案,
for(i=0； i<Runs； i++)
? if(my_node_id==0){ /*发送方 */
? Tmp=Second()；
? start_time=Second()；
? 向结点 1发送一个 m字节消息；
? 从结点 1接收一个 m字节消息；
? end_time=Second()；
哈尔滨工业大学计算机科学与技术学院 19
?timer_overhead=start_time-tmp；
?total_time=end_time-start_time-
timer_overhead；
?communication_time[i]=total_time
／ 2；
?}else if(my_node_id==1){ /*接收
方 */
? 从结点 0接收一个 m字节消息；
? 向结点 0发送一个 m字节消息；
?}}
哈尔滨工业大学计算机科学与技术学院 20
② 热土豆 (hot_potato)方法 (也称
为救火队方法 )。
? 该方法面向 n个结点；
? 方法是个循环的发送接收。
哈尔滨工业大学计算机科学与技术学院 21
③ 集合通信
? 条件：设分布式存储器多计算机
中 n个结点中的每一个均执行以下
的 SPMD程序 。
? 使用路障来同步测量进程中的 异
步操作 。
哈尔滨工业大学计算机科学与技术学院 22
? for(i=0； i<Runs； i++ ){
? Barrier synchronization；
? Tmp=Second()；
? start_time=Second()；
? for(j=0； j<Iterations； j++)
The_collective_routine_being_meas
ured；
? End_time=Second()；
哈尔滨工业大学计算机科学与技术学院 23
?Timer_overhead=start_time-tmp；
?Total_time=end_time-start_time
–timer_overhead；
?Local_ time=total_time/
Iterations；
?Communication_time[i]=maxim
um Of all n local time values；
?}
哈尔滨工业大学计算机科学与技术学院 24
? 改用集合操作的通用化乒乓方法,
? for(i=0； i<Runs； i++){
? if(my_node_id==0){
? tmp=Second()；
? start_time=Second();
? 结点 0向所有 n个结点广播一个空消
息；
? For(j=0； i<Iterations； j++)
哈尔滨工业大学计算机科学与技术学院 25
? the collective_routine_ being_
measured；
? 所有结点向结点 0完成一个空归约；
if(my_node_id=0){
?end_time=Second()；
?timer_overhead=start_time-tmp；
?Communication_time[i]=end_time-
start_time- timer_overhead
?}
哈尔滨工业大学计算机科学与技术学院 26
4.开销表达式
? 经测量获得开销数据，有 3种表
示方法,
① 用表格来表示数据。
例如，下表给出了在 SP2上运行
专有 MPL通信库所测得的点对点
通信的定时结果。
哈尔滨工业大学计算机科学与技术学院 27
哈尔滨工业大学计算机科学与技术学院 28
② 以曲线来表示数据
? 如下图所示。
? 其优点是曲线可示出通信开
销增长趋向。
哈尔滨工业大学计算机科学与技术学院 29
哈尔滨工业大学计算机科学与技术学院 30
③ 表达式表示
? 例如，将所测得的定时数据用最小
二乘法适当地加以拟合。就可将 SP2
上的点对点通信开销表示成消息长
度的线性函数,
t=46+0.035mμ s
? 如果加以拟合，它与曲线之间的误
差是很小的，如上图所表明的那样。
哈尔滨工业大学计算机科学与技术学院 31
5.点对点通信表达式
?Hockney提出操作通信时间 (以 μ s
表示 )特征的 1个模型,
?其中的通信开销 t(m)是消息长度
m(以字节表示 )的线性函数,
t(m)=t0+m／ r∞
?式中 t0是以 μ s表示的启动时间，
而 r∞ 是渐近带宽，单位 MB／ s。
哈尔滨工业大学计算机科学与技术学院 32
? Hockney还引入了两个附加的参
数。
① 半峰值长度记为 m1/2字节，是达
到半渐近带宽所需的消息长度。
② 特殊性能，记为 ?0MB／ s，用来
表明短消息带宽。
哈尔滨工业大学计算机科学与技术学院 33
?4个参数 t0, r∞, m1/2, ?0
MB中的两个是独立的。
?另两个可用以下关系推得,
?t0 = m1/2 ／ r∞ =1/ ?0
?其中 m1/2是表示系统支持短消息
通信好坏程序的参数。
哈尔滨工业大学计算机科学与技术学院 34
?例如,
?SP2的 t(m)=46+0.035m。
?启动开销为 t0=46μ s；
?渐近带宽为,
r∞ =1／ 0.035=28.57MB／ s,
?以及半峰值消息长度为,
m1/2 = t0 × r∞ =1314字节。
哈尔滨工业大学计算机科学与技术学院 35
6.集合通信
?将式 Hockney表达式扩展成如下,
?通信开销 T(m,n)现改为是 m和 n两者的
函数。但启动时延仍只依赖于 n。
?渐近带宽变为 r∞ (n) 。
T(m,n)=t0(n)+m/r∞ (n)
哈尔滨工业大学计算机科学与技术学院 36
?在将测得的定时数据与不同的 t0(n)
和 r∞ (n)形式拟合
?可推得如表中所示的 4个集合操作
的公式
哈尔滨工业大学计算机科学与技术学院 37
哈尔滨工业大学计算机科学与技术学院 38
7.集合计算
① 测量了 3种代表性的集合计算操作：
路障、归约和扫描。它们拟合曲线
开销表达式如下表所示。
② 注意当处理器数超过 256时，路障开
销为 762μ s，相当于执行
762x266=202,692 flop所需的时间。
③ 现在可以回答这样问题，是否应使
用同步算法?
哈尔滨工业大学计算机科学与技术学院 39
哈尔滨工业大学计算机科学与技术学院 40
④ 短消息和长消息全交换开销的方法
作了比较,
? 在下图中示出了当 mn2=16MB(例如，
m=1024字节和 n=128)时两种表示方
法的相对误差。
? 结论：如图
哈尔滨工业大学计算机科学与技术学院 41
哈尔滨工业大学计算机科学与技术学院 42
?在下图，比较了当 mn2=64KB (例
如,m=4字节及 n=128)时,
?所测得的开销与由两种方法推测
所得的开销。
哈尔滨工业大学计算机科学与技术学院 43
哈尔滨工业大学计算机科学与技术学院 44
?本节结束！
