中科大多核并行计算课件5734627.ppt

现代密码学理论与实践之五 多核并行计算Multicore Parallel Computing 主讲人 徐 云 并行计算——结构?算法?编程 第一篇 并行计算的基础 第一章 并行计算机系统及其结构模型 第二章 当代并行机系统：SMP、MPP和Cluster 第三章 并行计算性能评测 第三章 并行计算性能评测 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 平均延迟度量标准 CPU的某些基本性能指标 工作负载 执行时间 浮点运算数: Flops 指令数目: MIPS 无重叠的假定下：并行执行时间包括 T comput 计算时间，T paro 并行开销时间，T comm相互通信时间 T n = T comput + T paro+ T comm T paro : 进程管理（如进程生成、结束和切换等），组操作（如进程组的生成与消亡等），进程查询（如询问进程的标志、等级、组标志和组大小等） T comm :同步（如路障、锁、临界区、事件等），通讯（如点到点通信、整体通信），聚合操作（如规约、前缀运算等） 存储器性能 存储器的层次结构(容量C,延迟L,带宽B) 估计存储器的带宽 RISC的加法可在单拍内完成，假定字长8bytes，时钟频率100MHz，则 带宽B = 3*8*100*106 B/s= 2.4GB/s 并行与通信开销 并行和通信开销：相对于计算很大。 PowerPC (每个周期 15ns 执行4flops; 创建一个进程1.4ms 可执行372000flops) 开销的测量：乒--乓方法（Ping-Pong Scheme）节点0发送m个字节给节点1；节点1从节点0接收m个字节后，立即将消息发回节点0。总的时间除以2，即可得到点到点通信时间，也就是执行单一发送或接收操作的时间。 可一般化为热土豆法（Hot-Potato），也称为救火队法（Fire-Brigade) 0——1 —— 2 —— … —— n-1 —— 0 并行开销的表达式：整体通信 典型的整体通信有： 播送（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个字节。 机器的成本、价格与性/价比 机器的成本与价格 机器的性能/价格比 Performance/Cost Ratio ：系指用单位代价（通常以百万美元表示）所获取的性能（通常以MIPS或MFLOPS表示） 利用率（Utilization）：可达到的速度与峰值速度之比 第三章 并行计算性能评测 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 平均延迟度量标准 算法级性能评测 加速比性能定律 并行系统的加速比是指对于一个给定的应用，并行算法（或并行程序）的执行速度相对于串行算法（或串行程序）的执行速度加快了多少倍。 Amdahl 定律 Gustafson定律 Sun Ni定律 Amdahl 定律（1） P：处理器数； W：问题规模（计算负载、工作负载，给定问题的总计算量）； Ws：应用程序中的串行分量，f是串行分量比例（f = Ws/W， Ws=W1）； WP：应用程序中可并行化部分，1-f为并行分量比例； Ws +W p =W； Ts=T1 ：串行执行时间，T p ：并行执行时间； S：加速比，E：效率； 出发点：Base on Fixed Problem Size 固定不变的计算负载； 固定的计算负载分布在多个处理器上的， 增加处理器加快执行速度，从而达到了加速的目的。 Amdahl