什么是并行算法？

并行算法是专门为并行计算机设计的算法。如果没有强加物理约束或通信开销，则理想化的并行算法是为 PRAM 模型编写的算法。在现实世界中，只有能够在物理机器上经济高效地实现算法，才被认为是有效的。从这个意义上说，所有机器可实现的算法都必须依赖于架构。这意味着不能忽略通信开销和架构约束的影响。

并行算法的特点

并行算法有多种特点，如下所示 -

确定性与非确定性- 只有确定性算法可以在真实机器上实现。我们的研究仅限于具有多项式时间复杂度的确定性算法
计算粒度- 粒度决定了计算中使用的数据项和程序模块的大小。从这个意义上说，我们还将算法分为细粒度、中粒度或粗粒度。
Parallelism profile - 算法中并行度的分布揭示了并行处理的机会。这通常会影响并行算法的有效性。
通信模式和同步要求- 通信模式解决内存访问和处理器间通信。取决于算法，模式可以是静态的或动态的。静态算法更适合 SIMD 或流水线机器，而动态算法则适合 MIMD 机器。同步频率通常会影响算法的效率。
操作的一致性- 这是指要执行的基本操作的类型。如果跨数据集的操作是统一的，则可能更需要 SIMD 处理或流水线。换句话说，随机结构的算法更适合于 MIMD 处理。其他相关问题包括所需的数据类型和精度。
内存需求和数据结构- 在解决大规模问题时，数据集可能需要巨大的内存空间。内存效率受算法中选择的数据结构和数据移动模式的影响。时间和空间复杂度都是并行算法粒度的关键度量。