核心问题是关键路径相对于总计算量的长度。如果成正比，那么并行性充其量只能提供恒定的加速。如果渐近小于，则随着问题大小的增加，还有更多并行空间。对于其中在输入大小中是多项式的算法，最好的情况是，因为可以在不到对数时间内计算出非常少的有用量。$C$$T$$C$$T$$C$$T$$T$$N$$C \sim \log T$

例子

• $C = T$用于使用标准算法的三对角求解。每个操作都依赖于前一个操作的完成，因此没有机会进行并行。三对角问题可以在并行计算机上使用嵌套剖分直接求解、多级域分解或具有使用谐波扩展构造的基函数的多重网格在对数时间内求解（这三种算法在多个维度上是不同的，但在一维中可以完全重合）。
• 矩阵的密集下三角求解，但关键路径只有，因此一些并行性可能是有益的。$m\times m$$T = N = \mathcal O(m^2)$$C = m = \sqrt T$
• Multigrid 和 FMM 都有，关键路径长度为。$T = N$$C = \log T$
• 在域的规则网格上的时间的显式波传播需要时间步（为了稳定性），因此关键路径至少是。总工作量为。最大可用处理器数为，剩余因子无法通过增加并行度来恢复。$\tau$$(0,1)^d$$k = \tau / \Delta t \sim \tau N^{1/d}$$C = k$$T = k N = \tau N^{(d+1)/d}$$P = T/C = N$$N^{1/d}$

形式复杂性

NC 复杂度类描述了可以并行有效解决的那些问题（即，在多对数时间内）。是否未知，但人们普遍认为它是错误的。如果情况确实如此，那么P-complete描述了那些“本质上是连续的”并且不能通过并行性显着加速的问题。$NC = P$

从理论上讲，并行处理器时间内求解的复杂度类。是否（尽管大多数人怀疑不是）仍然未知，其中是多项式时间内可解决的问题集。并行化的“最难”问题被称为中的每个问题都可以通过完全问题。如果你证明一个单一的$NC$$O(log^c n)$$O(n^k)$$P=NC$$P$$P$$P$$P$$NC$$P$- 完整的问题在$NC$, 你证明$P=NC$（尽管如上所述这可能是错误的）。

所以任何问题$P$-complete 直观上很难并行化（尽管仍然有可能实现大幅加速）。一个$P$- 我们甚至没有非常好的常数因子加速的完整问题是线性规划（参见OR-exchange的评论）。

从 grocking Amdahl 定律开始。基本上任何具有大量串行步骤的东西都不会从并行性中受益。一些示例包括解析、正则表达式和大多数高比率压缩。

除此之外，关键问题通常是内存带宽的瓶颈。特别是对于大多数 GPU，您的理论 flops 大大超过了您可以获得 ALU 的浮点数数量，因为具有低算术强度（flops / cache-miss）的算法将花费大量时间在 RAM 上等待。

最后，任何时候一段代码需要分支，它都不太可能获得良好的性能，因为 ALU 的数量通常超过逻辑。

总之，一个很难从 GPU 获得速度增益的非常简单的例子是简单地计算整数数组中零的数量，因为您可能需要经常分支，最多执行 1 次操作（增量一）在您找到零的情况下，并且每次操作至少获取一次内存。

一个没有分支问题的例子是计算一个向量，该向量是另一个向量的累积和。（ [1,2,1] -> [1,3,4] ）

我不知道这些算不算“著名”，但肯定有很多问题是并行计算无法帮助您解决的。

求解 Eikonal 方程的（著名的）快速行进方法无法通过并行化来加速。还有其他求解 Eikonal 方程的方法（例如快速扫描方法）更适合并行化，但即使在这里（并行）加速的潜力也是有限的。

Eikonal 方程的问题在于信息流取决于解本身。松散地说，信息沿着特性（即光学中的光线）流动，但特性取决于解决方案本身。离散化 Eikonal 方程的信息流更糟糕，如果需要任何并行加速，则需要额外的近似值（如快速扫描方法中隐含的）。

要了解并行化的困难，请想象一个漂亮的迷宫，就像Sethian 网页上的一些示例一样。通过迷宫的最短路径上的单元数（可能）是解决相应问题的任何（并行）算法的最小步数/迭代数的下限。

（我写“（可能）是”，因为众所周知，下界很难证明，并且通常需要对算法使用的操作进行一些合理的假设。）