Concurrency/Parallel

你吃饭吃到一半，电话来了，你一直到吃完了以后才去接，这就说明你不支持并发也不支持并行。两个任务互不干扰。

你吃饭吃到一半，电话来了，你停了下来接了电话，接完后继续吃饭，这说明你支持并发。两个任务可以相互干扰。

你吃饭吃到一半，电话来了，你一边打电话一边吃饭，这说明你支持并行。两个任务互不干扰，但同时进行。

并发的关键是你有处理多个任务的能力，不一定要同时。

并行的关键是你有同时处理多个任务的能力。

I/O 密集型可以使用 多线程 提高效率，如 socket, crawler 等。

计算密集型可以使用 多进程 充分利用多核资源，如数据分析。

并行计算的内存架构

对于每一个“ CPU 时钟”， CPU 按照下面的顺序执行：

  1. Fetch: CPU 从一片内存区域中（寄存器）获得数据和指令
  2. Decode: CPU 对指令进行解码
  3. Execute: 该执行在数据上执行，将结果保存在另一个寄存器中

SISD

1 个 CPU ，1 个数据流。所有运行在这上面的算法都是顺序执行的，不存在任何并行。

MISD

n 个 CPU 每一个都有自己的控制单元（n 个指令流），共享同一个内存单元（1 个数据流）。例如数据加密。

SIMD

n 个 CPU ，每一个都有自己的局部内存，可以用来存储数据。所有的处理器都在单一指令流下工作；具体说，就是有n个数据流，每个处理器处理一个。

MIMD

n个处理器，n个指令流，n个数据流。在 MIMD 中，架构是通过线程或进程层面的并行来实现的，这也意味着处理器一般是异步工作的。这种类型的计算机通常用来解决那些没有统一结构、无法用 SIMD 来解决的问题。

并行编程模型

  • 共享内存模型
  • 多线程模型
  • 分布式内存/消息传递模型
  • 数据并行模型

设计并行程序

  1. Task decomposition
    • Domain decomposition
    • Functional decomposition
  2. Task assignment
  3. Agglomeration
  4. Mapping
    • Dynamic Mapping
      • Manager/worker
      • Hierarchical manager/worker
      • Decentralize

评估并行性能

加速比：单个处理器解决问题需要的时间为 TS ，使用 P 个处理器解决这个问题的时间为 TP ，那么加速比 S = TS/TP 。 当 TS 为最佳串行算法的执行时间，加速比是绝对的，而当 TS 为并行算法在单个处理器上的执行时间，则加速比是相对的。 S = P 为线性加速比，也是理想加速比 S < P 为真实加速比 S > P 为超线性加速比

效率：假设效率为 E ，E = S/P = TS/PTP 。 E = 1 为线性加速比 E < 1 为真实情况 E << 1 有问题的低效并行算法

伸缩性：伸缩性用于度量并行机器高效运行的能力，代表跟处理器数量成比例的计算能力 （执行速度）。如果问题的规模和处理器的数量同时增加，性能不会下降。在依靠各种因素叠加的可伸缩系统中，可以保持相同的效率或者有更高的效率。

阿姆德尔定律(Ahmdal’s law)：阿姆德尔定律广泛使用于处理器设计和并行算法设计。它指出程序能达到的最大加速比被程序的串行部分限制。 S = 1/(1-p) 中 1-p 指程序的串行部分。它的意思是，例如一个程序 90% 的代码都是并行的，但仍存在 10% 的串行代码，那么系统中即使由无限个处理器能达到的最大加速比仍为9。

古斯塔夫森定律(Gustafson’s law)：古斯塔夫森定律在考虑下面的情况之后得出的：

  • 当问题的规模增大时，程序的串行部分保持不变。
  • 当增加处理器的数量时，每个处理器执行的任务仍然相同。

古斯塔夫森定律指出了加速比 S(P) = P-a(P-1) ， P 为处理器的数量， S 为加速比，alpha 是并行处理器中的非并行的部分。作为对比，阿姆德尔定律将单个处理器的执行时间作为定量跟并行执行时间相比。因此阿姆德尔定律是基于固定的问题规模提出的，它假设程序的整体工作量不会随着机器规模（也就是处理器数量）而改变。古斯塔夫森定律补充了阿姆德尔定律没有考虑解决问题所需的资源总量的不足。古斯塔夫森定律解决了这个问题，它表明设定并行解决方案所允许耗费的时间的最佳方式是考虑所有的计算资源和基于这类信息。

Reference

  1. Python Parallel Programming
湘ICP备19014083号-1