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

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.

• Binary search can not be sped up (significantly, i.e. by a factor), even when considering memory hierarchy.
– Raphael
Feb 16 '12 at 6:46
• Gram Schmidt algorithm: en.wikipedia.org/wiki/Gram%E2%80%93Schmidt_process
– Anycorn
Feb 16 '12 at 6:57
• @Anycorn No, left-looking classical Gram-Schmidt and right-looking modified Gram-Schmidt work well in parallel. There are many other parallel QR algorithms including the recently popularized TSQR. Feb 22 '12 at 22:23
• @Raphael: I think ist is possible to speed up binary search by the factor log(n), n=#processors. Instead o dividing the search interval in to parts and checking where to continue, divide the interval in n parts. Perhaps there are more efficient ways, i don know. Feb 25 '12 at 19:35

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.

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).

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.

• The "branching free example" you gave is the prefix-sum, which actually has a good parallel algorithm: http.developer.nvidia.com/GPUGems3/gpugems3_ch39.html Calculating the number of zeros should be efficient for similar reasons. There is no way around arithmetic intensity, though... Jan 10 '14 at 18:57
• Cool. I stand corrected on that one. Jan 14 '14 at 23:00

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.)

• Nice example, but I do not believe your claimed lower bound. In particular, multigrid methods can be used to solve the eikonal equation. As with multigrid for high frequency Helmholtz, the challenges are mainly in designing suitable coarse spaces. In the case of a labyrinth, a graph aggregation strategy should be effective, with the coarse representation determined by solving local (thus independent) problems for segments of the labyrinth. Feb 26 '12 at 21:46
• In general when multigrid methods do well, it means that the granularity of the problem is lower than the descritization, and a disproportional "amount of correct answer" is coming from the course solve step. Just an observation, but the lower bound on that sort of thing is tricky! Feb 27 '12 at 3:13
• @JedBrown From a practical perspective, multigrid for high frequency Helmholtz is quite challenging, contrary to what your comment seems to imply. And using multigrid for the eikonal equation is "uncommon", to say the least. But I see your "theoretical" objection against the suggested lower bound: Time offsets from various points inside the labyrinth can be computed before the time to reach these points is known, and added in parallel after the missing information becomes available. But in practice, general purpose parallel eikonal solvers are happy if they actually come close to the bound. Feb 27 '12 at 15:45
• I didn't mean to imply that it was easy, the wave-ray coarse spaces are indeed very technical. But, I think we agree that there is already opportunity for parallelism in open regions, while in narrow "labyrinths" (which expose very little parallelism with standard methods), the upscaling problem is more tractable. Feb 27 '12 at 21:19
• @JedBrown Slide 39 of www2.ts.ctw.utwente.nl/venner/PRESENTATIONS/MSc_Verburg.pdf (from 2010) says things like "Extend the solver from 2D to 3D" and "Adapt method to problems with strongly varying wavenumbers". So wave-ray multigrid may be promising, but "not yet mature" seems to be more appropriate than "very technical" for describing its current issues. And it is not really a high frequency Helmholtz solver (because it is a "full wave" solver). There are others "sufficiently mature" multigrid Helmholtz solvers ("full wave" solvers), but even these are still "active research". Feb 28 '12 at 14:33

Another class of problems that are hard to parallelize in practice are problems sensitive to rounding errors, where numerical stability is achieved by serialization.

Consider for example the Gram–Schmidt process and its serial modification. The algorithm works with vectors, so you might use parallel vector operations, but that does not scale well. If the number of vectors is large and the vector size is small, using parallel classical Gram–Schmidt and reorthogonalization might be stable and faster than single modified Gram–Schmidt, although it involves doing several times more work.