I just thought of a few simple mathematical situations where we cannot really apply parallel programming. But, does any one know of some standard/famous applications that have been traditionally considered to belong to such this category?
Printable View
I just thought of a few simple mathematical situations where we cannot really apply parallel programming. But, does any one know of some standard/famous applications that have been traditionally considered to belong to such this category?
Research is ongoing, and a recent reported breakthrough regarding a highly parallel development system promises to open areas previously thought to be too difficult to implement in parallel.
Qsort, for example, doesn't lend itself to parallel implementation, even in non-recursive forms, because each step of the algorithm is dependent on the previous step. Dividing the population to sort can occasionally be of some benefit, if the results can be accepted this way, but it's rare.
For years, 3D graphics engines (for games typically) have been argued both for and against parallel implementations. Tiling, for example, does return considerable benefit, but so far most game designs (for the game logic itself) are written in an animation cycle that hasn't lent itself to threaded design will. The typical animation loop is somewhat dependent on a controlled, single thread cycle. Still, research has shown many ways to gain benefit by reconsidering the design principles. Certainly spinning off obvious sections of work, like audio, help.
There are times, too, when parallel implementation just doesn't return much gain, when the problem is RAM bound (in current systems). If the division of the workload can't be separated into widely spaced RAM locations, for example, there can be collision in RAM access at the hardware level, such that little nor no gain is returned.
Hmm, so you mean quicksort? After the initial partitioning, you have two independent sets that can be sorted simulataneously.Quote:
Originally Posted by JVene
A good example of an algorithm which is very hard to parallelize is alpha-beta searching in AI.
I have come across a decent parallel algorithm for Quicksort . I will try to find the link or I will write down the code myself later in the day.
@Sang-drax :
Thanks for that, Will try to disinter more info on that class of algos.