Tell me more ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.
up vote 13 down vote favorite
5

I was just wondering if there were some "standard" examples that everyone uses as a basis for explaining the nature of parallel problems. What are some well-known problems out there that can see great benefits from scalability (and multi-threaded programming)?

*EDIT: also, a little background or explanation as to why it's parallelizable in nature would be of help! Thanks

share|improve this question
2  
how is this not constructive? – Paul Nathan Nov 21 '11 at 21:41
it somehow managed to earn the "Nice Question" badge lol – Dark Templar Nov 22 '11 at 6:01

We're looking for long answers that provide some explanation and context. Don't just give a one-line answer: please explain why you're recommending it as a solution. Answers that don't explain anything will be deleted. See Good Subjective, Bad Subjective for more information.

13 Answers

up vote 12 down vote

Raytracing. Each pixel of the image can be computed independently of all others.

It seems odd that despite the complexity of the scene (reflections, cloud effects, etc.), every pixel is computed by following what would be the paths of photons emerging from the light sources. The paths are independent of each other and can be computed separately. (Some ray tracers work backwards, following the rays of light from the camera to the light sources, but the effect is the same.)

share|improve this answer
3  
I think the only way to make ray tracing efficient and parallelizable is to make the rays travel 'backwards'. – dan_waterworth Nov 21 '11 at 8:25
2  
Efficient, perhaps, but forward raytracing is certainly embarrassingly parallel. – MSalters Nov 21 '11 at 10:31
1  
+1 because this answer would be good for demonstration purposes (e.g. you could adjust the colour of each pixel based on the thread used to render it). – George Duckett Nov 21 '11 at 11:00
up vote 10 down vote

Monte Carlo simulations.

You simulate some stochastic process repeatedly. Since you have to do it many times, you can easily run the different iterations in parallel.

share|improve this answer
and each iteration doesn't depend on another? – Dark Templar Nov 21 '11 at 5:15
1  
@DarkTemplar, its monte carlo, so no.The whole point is that each iteration is a run of a stochastic process so you can emperical measure the probability distribution. – Winston Ewert Nov 21 '11 at 5:39
up vote 9 down vote

Matrix Multiplication is by far the most common use for Multi-Threaded programming. Graphics Cards often have several hundred cores running potentially thousands of threads doing matrix calculations. It's also the only simple way to get below O(n^3) time complexity. Such usage also shows up in Fast Fourier Transformations and the solving of Linear Systems.

share|improve this answer
3  
hmm... graphics cards aren't really doing threads are they? Sure they are parallel, but not threads. – Winston Ewert Nov 21 '11 at 5:38
2  
If they are using CUDA they are using threads for sure. – World Engineer♦ Nov 21 '11 at 5:40
3  
If a thread implies a separate control flow, it's difficult to justify saying that GPUs use lots of threads. – dan_waterworth Nov 21 '11 at 8:23
3  
+1. Regardless of the precise solution (threads or not), matrix multiplication certainly is a valid example of a parallelizable problem. – MSalters Nov 21 '11 at 10:32
3  
Get below O(n^3) ? This doesn't make any sense, parallelism doesn't change the complexity, it just allow you to better use the resources available on he hardware. – deadalnix Nov 21 '11 at 10:55
show 4 more comments
up vote 6 down vote

In general anything where independant calculations only depend on a few nearby local values and of course where you have enough sets of inputs for it to be worth the effort.

A lot of image processing where you only need to read a small region of pixels for example - this is also an area were you have a lot of inputs (ie pixels) and you are normally under a time pressure.

Any algorithm where you work on local sets of data independantly and merge the results at the end - such as Quicksort.

share|improve this answer
up vote 6 down vote

Everything that is embarrassingly parallel, meaning problems that by their very nature tend to fall apart into small independent problems that then can be solved in parallel.

Some of the practical ones would be:

  • A web server that is answering small requests (like static files). Have a worker process each request.
  • A web crawler that is following all links on a website, spin off a thread for each link
  • Batch processing images
share|improve this answer
up vote 5 down vote

MapReduce. Highly scalable across hundreds or thousands of processors. The problem is divided up into small, bite-size pieces and sent to the mapping processors. Each does a bit of work and sends the results back to a central store. The central store then divvies out the results to the reduction processors which also send back their results to the store.

share|improve this answer
6  
In all fairness, MapReduce isn't a problem. It's a parallel programming technique you'd use when you have a parallelizable problem. – MSalters Nov 21 '11 at 10:34
up vote 4 down vote

Every local* operation in image processing can be parallelized.

* A local operation is one where every output pixel depends on a small "neighborhood" of input pixels. E.g. recoloring, scaling, sharpening, etc.

share|improve this answer
up vote 3 down vote

There are a few good answers already (and I suspect this should be community-wikied and have one post which collects all of them together).

Another classic one which I'm surprised no-one has mentioned so far is breaking encryption. Either password cracking (each task consists of hashing a candidate password and checking the hash against the value extracted from the victim's database or /etc/shadow) or key cracking (each task consists of applying a candidate key to the ciphertext and then applying some statistical analysis to see whether the resulting plaintext is plausible).

share|improve this answer
up vote 3 down vote

Make is an example of something that usually is quite parallelizable. Compiling a list of files into object files is sequence invariant and just have to finish for all files before linking.

share|improve this answer
Yes, but don't some files depend on variables declared in others?? – Dark Templar Nov 25 '11 at 22:09
up vote 3 down vote

How about rendering Fractals; that's embarrassingly parallel.

share|improve this answer
?? How is this embarrassingly parallel? – Dark Templar Nov 25 '11 at 22:08
Each pixel has its value calculated independently of the others. – George Duckett Nov 26 '11 at 9:32
Hmmm then wouldn't that apply to image processing in general? why Fractals specifically though? – Dark Templar Nov 26 '11 at 21:58
It could come under image processing in the same way that raytracing can. I think it's a big enough topic to appear separately. Also, it's not quite image processing as, like ray tracing, you produce an image but don't start with one. – George Duckett Nov 26 '11 at 22:54
up vote 2 down vote

Virtually any procedure that involves trying alternatives, where most fail and one succeeds. For example, to find a test word in a hyphenation dictionary, you could spin off one thread for each word in the dictionary. The thread that matches goes "HEY! I FOUND IT!" and all the other threads just quietly die. A more realistic example would be finding the prime factors of a large number - spin off a separate thread for each prime number and do the divides in parallel.

share|improve this answer
up vote 2 down vote

Parallel processing is used in ETL (Extract, Transform and Load) application. For example, ETL tools such as IBM InfoSphere DataStage and AB Inito use parallelism to provide significant improvements during batch job processing.

share|improve this answer
up vote 2 down vote

Quick sort is a nice little problem that can be made parallel with great ease. Same thing goes for the Tower of Hanoi. In fact, any recurring algorithm can be made parallel.

share|improve this answer
1  
Hmmm... Thanks, Sardathrion. But I don't understand how this is true. A recurring algorithm receives information from the recurrence immediately before it, no? Then recurrent algorithms are essentially sequential! – Dark Templar Nov 25 '11 at 22:10
Look at the trivial quick sort example and extrapolate from there. – Sardathrion Nov 27 '11 at 17:42

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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