# Largest reported speedup for a parallel computation?

A parallel implementation of a computation is usually compared to a sequential version of the same computation. The ratio of the time taken by the sequential version to the time taken by the parallel version is called the speedup. So if 8 cores run their smaller parts of the computation in 2 time units, and one core runs the whole computation in 8 time units, then the speedup is 4.

What is the largest speedup reported for a real computation?

It is possible to reach essentially infinite speedup in a search problem, since one of the parallel pieces of the search space may lead to a fast solution by that parallel instance, while the sequential solution has to work through the entire search space to get to that point. More generally, I want to exclude any problem where one of the parallel processes can reach a shortcut. So I am only interested in computations where the amount of work done by the parallel processes is the same as done by the sequential process. This is common in solving PDEs by grid methods, or in discrete event simulation. So with $n$ processors, one should never get more than $n$ speedup for these kinds of problems.

I would also like to exclude embarrassingly parallel problems like parallel rendering, since there one really has a vast number of independent tiny problems. I am interested in problems where it is not possible to partition the computation into strictly disjoint pieces.

For a large speedup, one has to have many processors. Given the restrictions on scope that I have conveniently labelled as "real computations", this question is then essentially about how efficiently the very large processor arrays that exist have been programmed.

I am aware of reported speedups of ~500 using arrays of GPUs, but surely larger speedups exist.

Edit: To address some of the comments, I dug up some further motivation, which will hopefully be precise enough for the tastes of those more mathematically inclined. This is quite different in style from the above, so I append it here as a postscript.

For $n$ iid random variables $X_1, X_2,\dots, X_n$ with mean $\mu$, denote their maximum by $X_{(n)}$ and their sum by $S_n$. O'Brien has shown that $X_{(n)}/S_n \to 0$ almost surely as $n \to \infty$ iff $\mu < \infty$.

Letting $X_i$ be the time taken by the $i$-th processor to complete its task, and assuming that there is a timeout/recompute mechanism to ensure that $\mu$ is finite, this hints that the inverse of the speedup should be essentially unbounded. (This is not necessarily the case: the techniques used may not carry over to the inverse, so I have to leave this a bit vague.)

This is a nice theoretical prediction, and the question arises: is this prediction borne out in practice? Or do implicit dependencies or diverging behaviours of the different processors (i.e. a breakdown in the iid assumption) tend to curtail this supposedly unbounded increase?

The iid case corresponds to the embarrassingly parallel case. Where the processors have to synchronize, independence breaks down.

My question can therefore also be rephrased as: how badly does non-negligible dependence between parts of a computation as seen in practice affect the large-scale speedups that have been demonstrated? Given that the bounds for expectation of the maximum in the non-independent case are quite weak, some pointers to empirical data would be useful.

• Are you interested in raw numbers, or relative speedup (speedup divided by number of cores)? In particular, figures for GPUs I have seen typically use many more cores than the obtained speedup while CPUs seem to support better relative speedup, but we have fewer of them. – Raphael Jun 22 '13 at 11:33
• I want the absolute speedup -- just how far can one go by using parallel processing, as opposed to how efficiently one uses available resources. – András Salamon Jun 22 '13 at 11:35
• It is not clear if the LINPACK benchmark used for the Top 500 Supercomputer list would be considered not embarrassingly parallel--it has extremely limited communication requirements. If it is an acceptable benchmark, then the top list result could be used to generate a speedup ratio based on performance of a single core. Of course, defining the best result for a single core might be challenging--an FPGA programmed as a single vector processor core might beat even the best Intel processor core. – Paul A. Clayton Jun 22 '13 at 13:05
• I'm strongly tempted to close this as NARQ. The set of valid problems is unclear, and as Raphael alludes to, achieved speedup is highly sensitive to architectural details that vary along lots of axes. This question could be a better fit if it asked about factors influencing speedup, i.e., why not all problems are embarrassingly parallel and why these may not even always scale perfectly to kinds of architectures. – Patrick87 Jun 22 '13 at 19:45
• @Patrick87: I am quite familiar with the things that affect speedup (one of these is what my MSc was about). What I didn't know was precisely what I was asking about: how large a speedup has actually been achieved. I got a nice answer, so I am happy. – András Salamon Jun 22 '13 at 20:26