并行算法基本概念

本文主要包含如下内容：

并行算法的分类

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 （并行运行时间）

T p a r a l l e l = T s e r i a l P

S = T s e r i a l T p a r a l l e l

Efficiency

E = S P = T s e r i a l T p a r a l l e l P = T s e r i a l P * T p a r a l l e l

T p a r a l l e l = T s e r i a l P + T o v e r h e a d

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