并行算法基本概念

本文主要包含如下内容：

• 并行算法基本概念
  • 并行算法的分类
  • 并行算法的特征
  • 并行算法的速度和效率

并行算法的分类

Task parallelism and Data parallelism　任务并行和数据并行

  

Task parallelism

：对任务进行并行化处理，每个核进行不同的操作。

  

Data parallelism

：对数据进行并行化处理，每个核对不同数据进行类似的操作。

Shared-memory and Distributed-memory 共享内存与分离式内存

  

Shared-memory

：内核可以共享计算机的内存

  

Distributed-memory

：内核只能够访问自己的私有内存

并行算法的特征

Communication　通信

  每个内核需要对该核的算法输入数据和计算结果的数据进行通信、传输。

Load balancing 负载均衡

  为了加快运算速度，希望每个核完成运算时间基本一致，因此希望达到负载均衡。

Synchronization　同步

  因为每个内核之间存在数据通信，所以需要等待所需数据的计算结果。

并行算法的速度和效率

Speedup

  p= Number of cores （内核数目）

  T serial = Serial run-time （串行运行时间）

  T parallel = Parallel run-time （并行运行时间）

Tparallel=TserialP 

S=TserialTparallel 

Efficiency

E=SP=TserialTparallelP=TserialP∗Tparallel

Tparallel=TserialP+Toverhead

  许多并行程序是通过将进程/线程之间的串行程序的工作分开，并添加必要的“并行开销”，例如互斥或通信来开发的。此外，随着问题大小的增加，T_overhead通常比T_serial慢得多。 进程/线程有更多的工作要做，因此协调进程/线程工作的相对时间应该更少。