南京大学：《并行处理技术——分布式与并行计算 Distributed and Parallel computing（并行计算——结构、算法、编程）》课程教学资源（课件讲稿）第三章 并行计算硬件结构基础（并行计算性能评测）

第三章并行计算性能评测 *31并行机的一些基本性能指标 米 32加速比性能定律 *3.2.1 Amdahl定律 *3.2.2 Gustafson定律 *3.2.3Sun和Ni定律 *33可扩放性评测标准 *331并行计算的可扩放性 *332等效率度量标准 333等速度度量标准 *33.4平均延迟度量标准 2 2011/9/13

 3.1 并行机的一些基本性能指标  3.2 加速比性能定律  3.2.1 Amdahl定律  3.2.2 Gustafson定律  3.2.3 Sun和Ni定律  3.3 可扩放性评测标准  3.3.1 并行计算的可扩放性  3.3.2 等效率度量标准  3.3.3 等速度度量标准  3.3.4 平均延迟度量标准 2 2011/9/13 第三章 并行计算性能评测

CPU的某些基本性能指标 *工作负载 *执行时间 *浮点运算数 *指令数目 *并行执行时间comput为计算时间，Tpao为并行开销时 间，T comm为相互通信时间 Tn=T comput+Tparo+Tcomm 3 2011/9/13

 工作负载  执行时间  浮点运算数  指令数目  并行执行时间 T comput 为计算时间，T paro为并行开销时 间，T comm为相互通信时间 T n = T comput + T paro+ T comm 3 2011/9/13 CPU的某些基本性能指标

存储器性能 1-100GB 远程 100-100K周期 存储器 1-300MB/S *存储器的层次结构(C,L,B) 1级 2级 寄存器 高速缓存 高速缓存 主存 磁盘 C<2KB 4-256KB 64KB-4MB 16MB-16GB 1-100GB L=0周期 0-2周期 2-10周期 10-100周期 100K-1M周期 B=1-32GB/S 1-16GB/S 1-4GB/S 0.4-2GB/S 1-16MB/S *估计存储器的带宽 米 RISC add r1,r2,r3 *字长8 bytes1 ooMHz *B=3*8*100*106B/S=2.4GB/s 4 2011/9/13

 存储器的层次结构(C,L,B)  估计存储器的带宽  RISC add r1,r2,r3  字长 8bytes 100MHz  B = 3*8*100*106 B/s= 2.4GB/s 4 2011/9/13 存储器性能 寄存器 1级 高速缓存 2级 高速缓存 主 存 磁 盘 远 程 存储器 C<2KB L=0周期 B=1-32GB/S 4-256KB 0-2周期 1-16GB/S 64KB-4MB 2-10周期 1-4GB/S 16MB-16GB 10-100周期 0.4-2GB/S 1-100GB 100K-1M周期 1-16MB/S 1-100GB 100-100K周期 1-300MB/S

并行与通信开销 *并行和通信开销：相对于计算很大。 *开销的测量： *乒-乓方法(Ping-Pong Scheme)：节，点o发送m个字节 给节，点1；节点1从节点0接收个字节后，立即将消息发 回节点0。总的时间除以2，即可得到，点到点通信时间， 也就是执行单一发送或接收操作的时间。 *可一般化为热土豆法(Hot-Potato),也称为救火队法 (Fire-Brigade):0-1-2-... —-n-1—0 2011/9/13

 并行和通信开销：相对于计算很大。  开销的测量：  乒‐‐乓方法（Ping‐Pong Scheme）：节点0发送m个字节 给节点1；节点1从节点0接收m个字节后，立即将消息发 回节点0。总的时间除以2，即可得到点到点通信时间， 也就是执行单一发送或接收操作的时间。  可一般化为热土豆法（Hot‐Potato），也称为救火队法 （Fire‐Brigade)： 0——1 —— 2 —— … —— ‐n‐1 —— 0 5 2011/9/13 并行与通信开销

Ping-Pong Scheme For i=o To Runs-1 do if(my node id=o)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 o send an m-byte message to node o 米 endif endif 米 endfor 6 2011/9/13

 For i=o To Runs‐1 do  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  endif  endfor 6 2011/9/13 Ping‐Pong Scheme

并行开销的表达式：点到点通信 *通信开销t(m)=t。+mr *通信启动时间t。 *渐近带宽「，：传送无限长的消息时的通信速率 *半峰值长度m2：达到一半渐近带宽所要的消息长度 *特定性能兀。：表示短消息带宽 t。=mh/ro=1/mo 7 2011/9/13

 通信开销 t(m) = t0 + m/ r∞  通信启动时间 t0  渐近带宽r∞ ：传送无限长的消息时的通信速率  半峰值长度m1/2：达到一半渐近带宽所要的消息长度  特定性能π0：表示短消息带宽 t0 = m1/2 /r∞ = 1 /π0 7 2011/9/13 并行开销的表达式：点到点通信

并行开销的表达式：整体通信 典型的整体通信有： *广播(Broadcasting):处理器0发送m个字节给所有的n 个处理器 *收集(Gather):处理o接收所有n个处理器发来在消息， 所以处理器0最终接收了mn个字节； *散射(Scatter):处理器o发送了m个字节的不同消息给 所有n个处理器，因此处理器o最终发送了mn个字节； *全交换(Total Exchange)：每个处理器均彼此相互发送m 个字节的不同消息给对方，所以总通信量为m2个字节； 米 循环移位(Circular--shift):处理器i发送m个字节给处理器 i+1,处理器-1发送m个字节给处理器0，所以通信量为mn 个字节。 2011/9/13

 典型的整体通信有：  广播（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 个字节。 8 2011/9/13 并行开销的表达式：整体通信

机器的成本、价格与性/价比 *机器的成本与价格 *机器的性能/价格比Performance/Cost Ratio:系指用单 位代价（通常以百万美元表示）所获取的性能（通常以 MIPS或MFLOPS表示) *利用率(Utilization):可达到的速度与峰值速度之比 9 2011/9/13

 机器的成本与价格  机器的性能/价格比 Performance/Cost Ratio ：系指用单 位代价（通常以百万美元表示）所获取的性能（通常以 MIPS或MFLOPS表示）  利用率（Utilization）：可达到的速度与峰值速度之比 9 2011/9/13 机器的成本、价格与性/价比

算法级性能评测 加速比性能定律 * 并行系统的加速比是指对于一个给定的应用，并行算 法（或并行程序）的执行速度相对于串行算法（或串 行程序)的执行速度加快了多少倍。 *Amdahl定律（适用于固定计算负载) *Gustafson定律（适用于可扩放问题） *Sun Ni定律（受限于存储器） *可扩放性评测标准 *等效率度量标准 *等速度度量标准 *平均延迟度量标准 10 2011/9/13

 加速比性能定律  并行系统的加速比是指对于一个给定的应用，并行算 法（或并行程序）的执行速度相对于串行算法（或串 行程序）的执行速度加快了多少倍。  Amdahl 定律（适用于固定计算负载）  Gustafson定律（适用于可扩放问题）  Sun Ni定律（受限于存储器）  可扩放性评测标准  等效率度量标准  等速度度量标准  平均延迟度量标准 10 2011/9/13 算法级性能评测

Amdahl定律 P:处理器数) *W:问题规模（计算负载、工作负载，给定问题的总计算量)； *W,:应用程序中的串行分量，f是串行分量比例(f=WW, W=W); *W。:应用程序中可并行化部分，1f为并行分量比例； *Ws+W。=W; *T=T,:串行执行时间，T。:并行执行时间； *S:加速比，E:效率； *出发点： *固定不变的计算负载； *固定的计算负载分布在多个处理器上的， *增加处理器加快执行速度，从而达到了加速的目的。 11 2011/9/13

 P：处理器数；  W：问题规模（计算负载、工作负载，给定问题的总计算量）；  Ws：应用程序中的串行分量，f是串行分量比例（f = Ws/W， Ws=W1）；  WP：应用程序中可并行化部分，1‐f为并行分量比例；  Ws +W p =W；  Ts=T1：串行执行时间，T p：并行执行时间；  S：加速比，E：效率；  出发点：  固定不变的计算负载；  固定的计算负载分布在多个处理器上的，  增加处理器加快执行速度，从而达到了加速的目的。 11 2011/9/13 Amdahl 定律