Hot answers tagged implicit-parallelism
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 ...
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.
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.
Because with a few exceptions (Haskell) there is no way that the compiler can unwrap a loop. The problem is that each iteration through the loop can modify global state. So doing it in a different order may cause things to break. In haskell you can count on a function being pure, which is to say it does not read or change global state, so they can be ...
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 ...
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 ...
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.
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.
Most of the programming languages which we are using now came at the time where single threaded programming and single user interaction is the most used for many applications(ex: stand alone desktop applications). With the raise of web applications, cloud computing and multi user applications now we need more of multi threaded applications. The legacy ...
How about rendering Fractals; that's embarrassingly parallel.
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.
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 ...
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 ...
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.
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.
I can't answer directly that question, regarding parallelism or concurrency, but, the Dragon Book was written some decades ago, with some updates, maybe, and Compiler Techniques have change a lot. I have read some compilers docs, on the internet, and some of them use different ideas. Besides, there are other books & (online) publications about ...
I don't have any first-hand experience with it, nor do I know whether the techniques used are in the Dragon Book to the letter, but the Sun Studio C and C++ compilers can do automatic parallellization of for loops.
Transactions must be ACID, so, programmer mainly tends to think about one thread. Languages and platforms must protect programmer from concurrency as much as they can afford And concurrency is not as easy to test as funcionality itself, so programmers tends to leave besides these issues and, even, not thinking about commit concurrency handling, what is a ...
Only top voted, non community-wiki answers of a minimum length are eligible