Good motivation for parallel data structures and algorithms [closed]

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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:

http://youtu.be/jNgIdTUmzEQ?t=10m13s

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.