并行计算课件.ppt

* * * * * * * * * * * * * * * * * * * * * * 胖树更象真实的树，其向树根方向的枝杈变得越来越粗。 使用传统的二叉树的主要问题之一就是通向根节点的瓶颈问题，这是因为根部的交通最忙。胖树的提出使问题得到了缓解。 * * * * * * * * * * * * * * * * * * SIMD系统也称为数据并行机 * SIMD系统也称为数据并行机 * * Array Computer 阵列(计算)机、向量计算机 ：把若干台处理机排列某种规则结构的阵列，实现并行运算的计算机。 阵列计算机用于向量运算时 现用的阵列计算机有两种主要类型： 1.松耦合型（） 各处理器分别拥有自己的局部内存和局部程序，处理器之间通过消息传递来互通信息。这样的系统中各处理器之间耦合较松消息传递速度慢，但一个系统中可以容纳数万个处理器，因而可实现大规模并行计算。 2.紧耦合型（） 所有处理器共享系统内存，通常是将多个存储体通过互连网络与多个处理器相连，处理器之间耦合紧密，运行效率高，但由于互连网络的复杂性所限，实际上允许包含的处理器个数不能太多，因而并行程度有限。 * * * * * * * * * * * * * * * * * * * * * * * * * * 重力加速度的发现就是早期科学研究方法的最好体现。 火箭发射的数字模拟就是现代科学研究方法的一个体现。 计算科学的引入是因为： 1。计算机的发展，使我们有了这样的工具 2。有些科学实验是费用巨大 3。有些科学实验是不道德的 4。有些科学实验在现实世界是不可能进行的 * 重力加速度的发现就是早期科学研究方法的最好体现。 火箭发射的数字模拟就是现代科学研究方法的一个体现。 计算科学的引入是因为： 1。计算机的发展，使我们有了这样的工具 2。有些科学实验是费用巨大 3。有些科学实验是不道德的 4。有些科学实验在现实世界是不可能进行的 * * 随着对预报的精度的要求不断提高其计算机的速度增加实际上比上述的还要高。 * 随着对预报的精度的要求不断提高其计算机的速度增加实际上比上述的还要高。 * * * * * * * * * * * * * 当 N =106 时，其串行算法要完成： 1. 对质数倍数标记的次数为 2,122,048 2. 需要输出 78,498 个质数 假设标记质数的倍数一次和输出一个质数的时间均为1个单位时间，则串行算法的执行时间为： 2,122,048 + 78,498=2,200,546 f = 78,498 / 2,200,546 = 0.0357 在具有 p 个处理器的并行机上可能获得的最大加速比为: 1 0.0357 +0.9643 /p 加 速 比 16 12 8 4 1 4 8 12 16 20 24 28 32 处理器个数 1 4 8 12 处理机个数 时间 计算时间 I/O时间 S = S(p) = 1 f +(1-f) /p 当 p 无限增加时，加速比趋于 1 / f。 从刚才的例子中看出：f = 0.0357，那么可获得的最大加速比不会超过1 / 0.0357 ≈ 28，它与处理机的个数无关。即当处理机的个数超过一定数量后，加速比不会随着其增加而增加。 Amdahl定律曾经给并行计算理论的研究带来了很大的负面影响。 适用于扩展问题的Gustsfson定律 Amdahl 定律的一个主要缺点：固定负载妨碍了并行机性能可扩展性的开发。 有些计算任务要求在给定的时间内希望提高计算精度，即在给定的时间内增加处理器的数量使计算量提高，如我们希望数值天气预报的数据采样模型的单位更小。 在精度占主导位置的应用领域中，我们希望象在小机器上解小问题一样，在大机器上能解规模大的问题，并使二者所花费的时间大体相同。 适用于扩展问题的Gustsfson定律 Gustafson定律 (1988)：对于一台并行计算机，当问题中可并行部分扩大 p 倍时，其加速比也随之增长： S= f + (1-f) p = Ws + pWp Ws + Wp S = Ws + pWp Ws + pWp/p 若我们用 f 来表示，可将上式变为： S = fW + p(1-f)W fW + p(1-f)W/p = f + p(1-f) f + (1-f) 1 2 3 4 5 6 7 8 处理机个数 W 工作负载 Ws Ws Ws Ws Ws Ws Ws Ws Wp Wp Wp Wp Wp Wp