I have a more general question for you. I'm working in Parallel Data Structures and Parallel Algorithms. That is a nice topic with a lot of interesting challenges. However, I have some problem to argue for why is necessary use parallel solutions. The most common justification is "We need to take advantage of the current architectures", "Parallel alternatives speed up sequential alternatives", but it isn't enough. Some people can think: OK, I believe you, but I don't have any problem waiting 10 minutes for my efficient sequential algorithm instead of 2 minutes for your parallel algorithm. That reflects a weak spot of parallel solutions: they are, in general, difficult to program and need more time to debugging.

So, now I'm trying to find a better motivation for parallel solutions. I have this motivation now: There are problems that don't have efficient solutions in sequential, and parallel solutions appear like the best alternative for those kind of problems. My question now for you is: How characterize this kind of problems?. I thought in problems with a lot of computation, like some graph problems, but I would like to know other view points.

  • 2
    $\begingroup$ Why argue about performance with people that don't care about performance? I don't think there is any other motivation than that. (At any given point in time, the computational power of any one machine is limited. Exploiting multiple machines is the only way to break this barrier, barring algorithmic improvements.) 10min vs 2min is not at all spectacular, but when you have the option of running something for weeks on your desktop machine or over night on the universities server farm, things suddenly look more interesting. $\endgroup$ – Raphael Jan 30 '14 at 15:26
  • 1
    $\begingroup$ That said, I don't think this question is well-suited for the SE platform as answers are bound to be subjective. $\endgroup$ – Raphael Jan 30 '14 at 15:27
  • $\begingroup$ You are essentially asking: what class of problems are the parallelisable ones? We don't have a good answer for this even after decades of effort; the complexity classes NC or LogCFL might be reasonable candidates, and P-complete problems are probably not "nicely" parallelisable. But a characterization seems out of reach for now. $\endgroup$ – András Salamon Jan 31 '14 at 16:46

The quintessential example is large-scale physics simulations, say "electronic" wind tunnel or protein folding (i.e. "finding new medicines"). Both are hugely expensive in terms of computation cost, but yield themselves well to parallelization.

Another area in which parallelization is important is "big data", say search engines. When dealing with big data you need to divide the work among many processors. However often in these cases, most of the work is done in an "embarrassingly parallel" fashion, in which each processor does its share of work, and everything is combined in the end; you could (but don't have to) argue that this is not an interesting example for parallel algorithms.

Yet another example is computer animation, say for the movie industry. This example probably has the same shortcoming as the previous one.

What is common to all three examples is that computation is very costly, and cannot be executed sequentially within a reasonable span of time. Hence the need to distribute the work among several computers (or processors, or cores).

Another possible use case is when you want answers really fast. Here an example could be real-time cryptanalysis during a war: you want your answers in one hour rather than one day, and it makes a big difference. A similar example is real-time TV studios, which probably benefit from distributed computing as well. Chess-playing machines and the like also belong to this category. Big data also shows up in this category – when interactively exploring data, you would like queries to run in reasonable time.


There are two main reasons for parallel computing. The first, and obvious one, is time. It's our desire to minimize the time required for a solution that leads naturally to parallel computing. But, in some cases, this is not just a desire, but a necessity. Besides the examples already given by @YuvalFilmus, think about, for instance, weather forecasts. We need today a forecast for tomorrow, otherwise the forecast is useless, so we use parallel computing. In general, parallel computing, with regard to this point of view, is useful since it makes unfeasible problems feasible, and helps reduce design time, and therefore allows gaining a competitive advantage in industry. So, your example (10 versus 2 minutes) is not really the realm of parallel computing. Think about Boeing designing a new airplane using parallel computers saving years of design time instead.

The second reason is mainly scientific. For the majority of the problems, many scientists are willing to wait for the same amount of time to solve larger problems or to solve a problem of the same size but with greater accuracy (better, more complicated models) or with improved numerical precision. For instance, scientists usually don't care too much if climate change parallel simulations run for 6 months on a parallel supercomputer. If they spent 6 months last year, this year they are still willing to wait for 6 months, but they are now interested on getting better, high-quality answers, so they use a new , more complicated model (adding a lot of non-linear partial differential equations etc).

Finally, sequential problems that are difficult to parallelize are technically called $P-Complete$ problems, i.e. they are complete for the complexity class $P$. However, even though parallel computing helps, you can not expect to obtain optimal parallel solutions: these problems are thought to be $intrinsically$ sequential.

  • $\begingroup$ There's a third reason, which is power efficiency. $\endgroup$ – jmite Jan 31 '14 at 7:01
  • $\begingroup$ @jmite, I am afraid that, right now, power efficiency of parallel supercomputers is not really good. Here is my personal example. Our parallel supercomputers cost about 1 million of euros per year; using ordinary sequential workstations/servers would allow cutting this cost to about 50K euros per year, but then we would wait for results for years. $\endgroup$ – Massimo Cafaro Jan 31 '14 at 7:07
  • $\begingroup$ I guess power efficiency given a fixed amount of computing power. The idea being, it's more power efficient to have many slow nodes than few fast nodes. $\endgroup$ – jmite Jan 31 '14 at 7:20
  • $\begingroup$ Ah ok, that is a very different perspective, I fully agreed with you in this case. $\endgroup$ – Massimo Cafaro Jan 31 '14 at 7:24
  • $\begingroup$ Your last paragraph is dangerous. Not only is it unknown whether P-complete problems are indeed inherently sequential, it's also not clear that the complexity-theoretic definition of "parallelisable" holds any meaning in reality. $\endgroup$ – Raphael Jan 31 '14 at 8:25

In a talk about the new Mill CPU architecture, Ivan Godard makes a great point about why normal users might want faster bigger better CPUs:


He says that the reason games are full of zombies is because the AI is too dumb to do much else, and he posits it as a hardware limitation.

Newer game engines are multi-threaded, and even heterogeneous. But there is a lot more to be done to make them use all the cores and types of core in the next generation of hardware effectively.

Parallel data structures and algorithms are applicable to 'small data' and 'home user' problems as much as the big science and industry applications. People don't know it, but people want progress on parallel data structures and algorithms for their own selfish entertainment as much as for the improvement of mankind as a whole.

So ask these people if they think that games are too linear and the AI too dumb. Gaming resonates with people in a way abstract discussion about computational biology doesn't.


Not the answer you're looking for? Browse other questions tagged or ask your own question.