什么是并行算法？

确定性与非确定性-只有确定性算法可以在真实机器上实现。我们的研究仅限于具有多项式时间复杂度的确定性算法

计算粒度-粒度决定了计算中使用的数据项和程序模块的大小。从这个意义上说，我们还将算法分为细粒度、中粒度或粗粒度。

Parallelismprofile-算法中并行度的分布揭示了并行处理的机会。这通常会影响并行算法的有效性。

通信模式和同步要求-通信模式解决内存访问和处理器间通信。取决于算法，模式可以是静态的或动态的。静态算法更适合SIMD或流水线机器，而动态算法则适合MIMD机器。同步频率通常会影响算法的效率。

操作的一致性-这是指要执行的基本操作的类型。如果跨数据集的操作是统一的，则可能更需要SIMD处理或流水线。换句话说，随机结构的算法更适合于MIMD处理。其他相关问题包括所需的数据类型和精度。

内存需求和数据结构-在解决大规模问题时，数据集可能需要巨大的内存空间。内存效率受算法中选择的数据结构和数据移动模式的影响。时间和空间复杂度都是并行算法粒度的关键度量。