Home | | **Multicore Application Programming For Windows, Linux, and Oracle Solaris** | | **Multi - Core Architectures and Programming** | How Parallelism Can Change the Choice of Algorithms

Algorithms have characteristics that make them more or less appropriate for a multi-threaded implementation.

**How
Parallelism Can Change the Choice of Algorithms**

Algorithms
have characteristics that make them more or less appropriate for a
multi-threaded implementation. For example, suppose you have a deck of playing
cards that are in a random order but you would like to sort them in order. One
way to do this would be to hold the unsorted cards in one hand and place each
card into its appropriate place in the other hand. There are N cards, and a
binary search is needed to locate each card into its proper place. So, going
back to the earlier discussion on algorithmic complexity, this is an O(n∗log(n)) algorithm.

However,
suppose you have someone to help, and you each decide to sort half the pack. If
you did that, you would end up with two piles of sorted cards, which you would
then have to combine. To combine them, you could each start with a pile of
cards, and then whoever had the next card could place it onto the single sorted
stack. The com-plexity of the sort part of this algorithm would be O(n∗log(n)) (for a value of n that was half the
original), and the combination would be O(n). So although we have increased the
number of “threads,” we do not guarantee a doubling of performance.

An
alternative way of doing this would be to take advantage of the fact that
playing cards have an existing and easily discernible order. If instead of
sorting the cards, you just place them at the correct place on a grid. The grid
could have the “value” of the card as the x-axis and the “suit” of the card as
the y-axis. This would be an O(n) operation since the time it takes to place a
single card does not depend on the number of cards that are present in the
deck. This method is likely to be slightly slower than keeping the cards in
your hands because you will have to physically reach to place the cards into
the appropriate places in the grid. However, if you have the benefit of
another person helping, then the deck can again be split into two, and each
person would have to sort only half the cards. Assuming you don’t obstruct each
other, you should be able to attain a near doubling of performance. So, comparing
the two algorithms, using the grid method might be slower for a single person
but would scale better with multiple people.

The point
here is to demonstrate that the best algorithm for a single thread may not
necessarily correspond to the best parallel algorithm. Further, the best
parallel algorithm may be slower in the serial case than the best serial
algorithm.

Proving
the complexity of a parallel algorithm is hard in the general case and is
typi-cally handled using approximations. The most common approximation to
parallel performance is Amdahl’s law.

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

**Related Topics **

Copyright © 2018-2020 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.