并行计算复习

并行计算基本概念

• 什么是并行计算
  同时使⽤多种计算资源解决计算问题的过程, 是提⾼计算机系统计算速度和处理能⼒的⼀种有效⼿段.
• 为什么需要并行计算
  1. 为了满足不断增长的计算力的需求，比如天气预报等任务精度提高和大数据时代数据量的提升要求算力提高.
  2. 计算机硬件和网络技术的发展，导致多核处理器的广泛应用，使得程序需要支持并行计算.
  3. 单核处理器性能提升有限，不能满足增长的算力需求.
  4. IO处理速度慢.
• 三种经典的并行化方法
  1. 域分解
     将数据划分成多个子数据, 将子数据分配给多个处理器同时运行。
  2. 任务分解
     将任务从功能角度分成多个子任务分配给处理器, 然后将数据分配到处理相应任务的处理器并行运行.
  3. 流水线
     一类特殊的任务分解方式, 将一个任务分解成多个子任务同时进行, 在多个不同数据执行相同任务时性能提升较为明显.

并行计算的性能测评

并行计算的性能

性能指标

• performance: 通常是指机器的速度, 它是程序执行时间的倒数
• 程序执行时间：是指用户的响应时间(包括访问磁盘和访问存储器的时间, CPU时间, I/O时间以及操作系统的开销)
• CPU时间：它表示CPU的工作时间, 不包括I/O等待时间和运行其它任务的时间.
• 加速比: 串行执行时间与并行执行时间之比
  S(n) = $\frac{Executiontime(one processor system)}{Executiontime(multiprocessor system)}$ = $\frac{t_{s}}{t_{p}}$
• 计算/通信比:
  $\frac{Computation Time}{Communication Time}$ = $\frac{t_{comp}}{t_{comm}}$
• 开销:
  • 部分处理器的空闲
  • 并行版本中所需的顺序计算中不会出现的额外计算
  • 发送消息所需的通信时间
• 效率:
  E = $\frac{t_{s}}{t_{p} * n}$ = $\frac{S(n)}{n}$

内存对性能的影响

内存系统的性能包括延迟和带宽两个方面:

• 延迟指处理器向内存发起访问直至获取数据所需要的时间
• 带宽指内存系统向处理器传输数据的速率。

处理器执行指令时，由于CPU速度远快于IO存取（即延迟），导致指令执行的时间取决于延迟的大小。为了减小延迟，可以采用高速缓存.
带宽决定了单位时间内可以读取数据的大小，带宽增加可以减少读取数据的次数，可以提升峰值的速度，但对延迟大小没有影响.

加速比定律

定义以下参数:

• P: 处理器数
• W: 问题规模(计算负载, 工作负载, 给定问题的总计算量):
  • $W_{s}$: 应用程序中的串行分量, f是串行分量比例(f = $\frac{W_{s}}{W}$).
  • $W_{p}$: 应用程序中可并行化部分, 1-f为并行分量比例.
  • $W_{s}$ + $W_{p}$ = W.
• $T_{s}$: 串行执行时间, $T_{p}$ : 并行执行时间.
• S: 加速比, E:效率.
• 代价cost:
  代价 = 执行时间$t_{p}$ * 所使用的处理器整数n.
  • 对于串行计算:
    • 代价 = 执行时间$t_{s}$.
  • 对于并行计算:
    • $t_{p} = \frac{t_{s}}{S(n)}$.
    • 代价 = $t_{p} * n = \frac{t_{s}}{S(n)} = \frac{t_{s}}{E}$.

Amdahl 定律

• 出发点:
  • 固定不变的计算负载.
  • 固定的计算负载分布在多个处理器上的.
  • 增加处理器加快执行速度，从而达到加速的目的.
• 公式:
  
• 结论:
  给定一个应用，不断增加并行计算机和处理器数目，不可能无限制的提升加速比.

Gustafson 定律

• 出发点:
  • 大型计算中要求高精度, 同时计算时间不变, 所以需要相应地增多处理器数.
  • 增多处理器必须相应地增大问题规模才有实际意义.
• 公式:
  
• 结论:
  给定一个应用，不断增加并行计算机和处理器数目，可以无限制的提升加速比.

Sun and Ni 定律

Sun-Ni定律是对前两个定律的总括和扩展.

• 出发点:
  • 只要存储空间允许, 应当尽量增大问题规模以产生更好和更精确的解.
  • 假定在单节点上使用了全部存储容量M并在相应于W的时间内求解之，此时工作负载W = fW + (1 - f)W.
  • 设置因子G(p)表示存储容量增加到p倍时并行工作负载的增加量, 所以扩大后的工作负载W = fW + (1-f)G(p)W.
• 存储受限的加速公式:
  $S^{"} = \frac{fW + (1 - f)G(p)W}{fW + \frac{(1 - f)G(p)W}{p}} = \frac{f + (1 - f)G(p)}{f + \frac{(1 - f)G(p)}{p}}$
• 并行开销:
  $S^{'} = \frac{fW + (1 - f)G(p)W}{fW + \frac{(1 - f)G(p)W}{p} + W_{O}} = \frac{f + (1 - f)G(p)}{f + \frac{(1 - f)G(p)}{p} + \frac{W_{O}}{W}}$

可扩放性评测

• 可扩放性(Scalability)
  计算机系统(或算法或程序等)性能随处理器数的增加而按比例提高的能力, 反映并行算法能否有效利用可扩充PE数的能力.
• 影响加速比的因素：处理器数与问题规模
  • 求解问题中的串行分量
  • 并行处理所引起的额外开销（通信、等待、竞争、冗余操作和同步等）
  • 加大的处理器数超过了算法中的并发程度
• 增加规模有利于提高加速比的因素：
  • 较大的问题规模可以提高较高的并发度
  • 额外开销的增加可能慢于有效计算的增加
  • 算法中的串行分量比例不是固定不变的(因问题规模增加而缩小)

MPI编程和Mapreduce编程

考试都考完了, 这一部分和其他没总结好的部分就鸽了(逃).

并行算法的一般设计策略

串行算法的直接并行化

• 方法: 发掘和利用现有并行算法的并行性,直接将串行算法改造为并行算法.
• 特点:
  • 由串行算法直接并行化的方法是并行算法设计的最常用方法之一.
  • 不是所有的串行算法都可以直接并行化.
  • 一个好的串行算法未必能并行化为一个好的并行算法.
  • 许多数值串行算法可以并行化为有效的数值并行算法.

积分算法的直接并行化–π的计算

排序

• 枚举排序
• 冒泡排序并行化–奇偶排序

矩阵转置, 点乘与数乘

从问题描述开始设计并行算法

• 方法: 从问题本身描述出发，不考虑相应的串行算法，设计一个全新的并
  行算法.
• 特点:
  • 挖扼问题的固有特性与并行的关东.
  • 设计全新的并行算法是一个挑战性和创造性的工作.

求前缀和

年年必考填空.

借用已有算法求解新问题

• 方法: 找出求解问题和禁个已解决问题之间的联系, 改造或利用已知算法应用列求解问题上.
• 特点:
  • 这是一项创造性的工作(好水的一句词…).

碎碎念

很遗憾直到考试结束也没有把并行计算的内容复习完, 好几道题都没有背会, 最后得了85分…
据老哥们说这课给分不高来着, 好像蛮多70+的, 不过就我在家的复习状态高不高的也就认了.