什么是并行算法？

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

并行算法的特征

并行算法有以下几种特征：

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

Ginni

更新于： 2021年7月30日

940 次浏览

开启您的 职业生涯

通过完成课程获得认证

开始学习