Are there any famous problems/algorithms in scientific computing that cannot be sped up by parallelisation

Question

Are there any famous problems/algorithms in scientific computing that cannot be sped up by parallelisation? It seems to me whilst reading books on CUDA that most things can be.

Answer 1

The central issue is the length of the critical path $C$ relative to the total amount of computation $T$. If $C$ is proportional to $T$, then parallelism offers at best a constant speed-up. If $C$ is asymptotically smaller than $T$, there is room for more parallelism as the problem size increases. For algorithms in which $T$ is polynomial in the input size $N$, the best case is $C \sim \log T$ because very few useful quantities can be computed in less than logarithmic time.

Examples

• $C = T$ for a tridiagonal solve using the standard algorithm. Every operation is dependent on the previous operation completing, so there is no opportunity for parallelism. Tridiagonal problems can be solved in logarithmic time on a parallel computer using a nested dissection direct solve, multilevel domain decomposition, or multigrid with basis functions constructed using harmonic extension (these three algorithms are distinct in multiple dimensions, but can exactly coincide in 1D).
• A dense lower-triangular solve with an $m\times m$ matrix has $T = N = \mathcal O(m^2)$, but the critical path is only $C = m = \sqrt T$, so some parallelism can be beneficial.
• Multigrid and FMM both have $T = N$, with a critical path of length $C = \log T$.
• Explicit wave propagation for a time $\tau$ on a regular mesh of the domain $(0,1)^d$ requires $k = \tau / \Delta t \sim \tau N^{1/d}$ time steps (for stability), therefore the critical path is at least $C = k$. The total amount of work is $T = k N = \tau N^{(d+1)/d}$. The maximum useful number of processors is $P = T/C = N$, the remaining factor $N^{1/d}$ cannot be recovered by increased parallelism.

Formal complexity

The NC complexity class characterizes those problems that can be solved efficiently in parallel (i.e., in polylogarithmic time). It is unknown whether $NC = P$, but it is widely hypothesized to be false. If this is indeed the case, then P-complete characterizes those problems that are "inherently sequential" and cannot be sped up significantly by parallelism.

Answer 2

To give a theoretical aspect to this, $NC$ is defined as the complexity class that is solvable in $O(log^c n)$ time on a system with $O(n^k)$ parallel processors. It is still unknown whether $P=NC$ (although most people suspect it's not) where $P$ is the set of problems solvable in polynomial time. The "hardest" problems to parallelize are known as $P$-complete problems in the sense that every problem in $P$ can be reduced to a $P$-complete problem via $NC$ reductions. If you show that a single $P$-complete problem is in $NC$, you prove that $P=NC$ (although that's probably false as mentioned above).

So any problem that is $P$-complete would intuitively be hard to parallelize (although big speedups are still possible). A $P$-complete problem for which we don't have even very good constant factor speedups is Linear Programming (see this comment on OR-exchange).

Answer 3

Start by grocking Amdahl's Law. Basically anything with a large number of serial steps will benefit insignificantly from parallelism. A few examples include parsing, regex, and most high-ratio compression.

Aside from that, the key issue is often a bottleneck in memory bandwidth. In particular with most GPU's your theoretical flops vastly outstrip the amount of floating point numbers you can get to your ALU's, as such algorithms with low arithmetic intensity (flops / cache-miss) will spend a vast majority of time waiting on RAM.

Lastly, any time that a piece of code requires branching, it is unlikely to get good performance, as ALU's typically outnumber logic.

In conclusion, a really simple example of something that would be hard to get a speed gain from a GPU is simply counting the number of zeros in a array of integers, as you may have to branch often, at most perform 1 operation (increment by one) in the case that you find a zero, and make at least one memory fetch per operation.

An example free of the branching problem is to compute a vector which is the cumulative sum of another vector. ( [1,2,1] -> [1,3,4] )

I don't know if these count as "famous" but there is certainly a large number of problems that parallel computing will not help you with.

Answer 4

The (famous) fast marching method for solving the Eikonal equation cannot be sped up by parallelization. There are other methods (for example fast sweeping methods) for solving the Eikonal equation that are more amenable to parallelization, but even here the potential for (parallel) speedup is limited.

The problem with the Eikonal equation is that the flow of information depends on the solution itself. Loosely speaking, the information flows along the characteristics (i.e. light rays in optics), but the characteristics depend on the solution itself. And the flow of information for the discretized Eikonal equation is even worse, requiring additional approximations (like implicitly present in fast sweeping methods) if any parallel speedup is desired.

To see the difficulties for parallelization, imagine a nice labyrinth like in some of the examples on Sethian's webpage. The number of cells on the shortest path through the labyrinth (probably) is a lower bound for the minimal number of steps/iterations of any (parallel) algorithm solving the corresponding problem.

(I write "(probably) is", because lower bounds are notoriously difficult to prove, and often require some reasonable assumptions on the operations used by an algorithm.)