Thread: Applications that cannot be parallelized

  1. #1
    Eager young mind
    Join Date
    Jun 2006
    Posts
    342

    Applications that cannot be parallelized

    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?
    In the middle of difficulty, lies opportunity

  2. #2
    Registered User
    Join Date
    May 2007
    Posts
    147
    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.

  3. #3
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072
    Quote Originally Posted by JVene View Post
    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.
    Hmm, so you mean quicksort? After the initial partitioning, you have two independent sets that can be sorted simulataneously.

    A good example of an algorithm which is very hard to parallelize is alpha-beta searching in AI.
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

  4. #4
    Eager young mind
    Join Date
    Jun 2006
    Posts
    342
    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.
    In the middle of difficulty, lies opportunity

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Get Installed applications list and applications activity
    By arunarora in forum C++ Programming
    Replies: 5
    Last Post: 05-25-2009, 09:41 AM
  2. First MFC app - Not listed in Task Manager Applications
    By Dino in forum Windows Programming
    Replies: 3
    Last Post: 03-08-2008, 11:06 AM
  3. A question about windows programming
    By Hussain Hani in forum Windows Programming
    Replies: 16
    Last Post: 05-23-2007, 07:38 AM
  4. Creating real applications?
    By OdyTHeBear in forum C++ Programming
    Replies: 7
    Last Post: 12-13-2002, 07:54 PM