03 并行计算性能评测.ppt

并行计算——结构•算法•编程
第一篇并行计算的基础
第一章并行计算机系统及其结构模型
第二章当代并行机系统:SMP、MPP和Cluster
第三章并行计算性能评测
2017/11/10
1
现代密码学理论与实践之五
第三章并行计算性能评测
并行机的一些基本性能指标
加速比性能定律
Amdahl定律
Gustafson定律
Sun和Ni定律
可扩放性评测标准
并行计算的可扩放性
等效率度量标准
等速度度量标准
平均延迟度量标准
2017/11/10
2
现代密码学理论与实践之五
CPU的某些基本性能指标
工作负载
执行时间
浮点运算数
指令数目
并行执行时间 put 为计算时间,T paro 为并行开销时间,m为相互通信时间
T n = put + T paro+ m
例:估计APRAM模型下执行时间
2017/11/10
3
现代密码学理论与实践之五
存储器性能
存储器的层次结构(C,L,B)
估计存储器的带宽
RISC add r1,r2,r3 r 8bytes 100MHz
B = 3*8*100*106 B/s=
2017/11/10
4
现代密码学理论与实践之五
并行与通信开销
并行和通信开销:相对于计算很大。
PowerPC (每个周期 15ns 执行4flops;
可执行372000flops)
开销的测量:乒--乓方法(Ping-Pong Scheme)节点0发送m个字节给节点1;节点1从节点0接收m个字节后,立即将消息发回节点0。总的时间除以2,即可得到点到点通信时间,也就是执行单一发送或接收操作的时间。
可一般化为热土豆法(Hot-Potato),也称为救火队法(Fire-Brigade) 0——1 —— 2 ——…——-n-1 —— 0
2017/11/10
5
现代密码学理论与实践之五
Ping-Pong Scheme
if (my _node _id =0) then /*发送者*/
start _time =second( )
send an m-byte message to node 1
receive an m-byte message from node 1
end_time = second( )
total_time = end_time – start_time
communication_time[i] = total_time/2
else if (my_node_id = 1) then /*接收者*/
receive an m-byte message from node 0
send an m-byte message to node 0
endif
2017/11/10
6
现代密码学理论与实践之五
并行开销的表达式:点到点通信
通信开销 t(m) = t0 + m/ r∞
通信启动时间 t0
渐近带宽r∞:传送无限长的消息时的通信速率
半峰值长度m1/2 :达到一半渐近带宽所要的消息长度
特定性能π0:表示短消息带宽
t0 = m1/2 / r∞= 1 /π0
2017/11/10
7
现代密码学理论与实践之五
并行开销的表达式:整体通信
典型的整体通信有:
播送(Broadcasting):处理器0发送m个字节给所有的n个处理器
收集(Gather):处理0接收所有n个处理器发来在消息,所以处理器0最终接收了m n个字节;
散射(Scatter):处理器0发送了m个字节的不同消息给所有n个处理器,因此处理器0最终发送了m n个字节;
全交换(Total Exchange):每个处理器均彼此相互发送m个字节的不同消息给对方,所以总通信量为mn2个字节;
循环移位(Circular-shift):处理器i发送m个字节给处理器i+1,处理器n-1发送m个字节给处理器0,所以通信量为m n个字节。
2017/11/10
8
现代密码学理论与实践之五
机器的成本、价格与性/价比
机器的成本与价格
机器的性能/价格比 Performance/Cost Ratio :系指用单位代价(通常以百万美元表示)所获取的性能(通常以MIPS或MFLOPS表示)
利用率(Utilization):可达到的速度与峰值速度之比
2017/11/10
9
现代密码学理论与实践之五
算法级性能评测
加速比性能定律
并行系统的加速比是指对于一个给定的应用,并行算法(或并行程序)的执行速度相对于串行算法(或串行程序)的执行速度加快