User Tools

Site Tools


cs415:design_intuition

Narrative: designing parallel algorithms

How might we design a parallel algorithm for unshuffling a deck of cards?

Let's start with a sequential algorithm. If I give Andy a shuffled deck of cards, how might he unshuffle it? My idea: deal cards into four piles, one per suit, then sort each pile Ace → King. Finally, put all piles together.

Here, 1 pile == 1 array.

Is it easy to turn this into a parallel algorithm? Yes and No. Our first idea might be to divide the suits up first, then give each processor a suit to sort, then put them all together. This is pretty good, but brings up some gotchas:

  • according to our model, dividing the deck into suits is all done on one processor, so MUST be sequential
  • since the computer is using an array to hold the deck, we have to tell each processor which region of the array they'll be working on. How do we do that?
  • While it seems like each processor should be able to sort in the same amount of time, there are good reasons not to assume this. Therefore we need to know about barriers.

So, write out each step of the algorithm and label with S any step that must be sequential, P any step that can be parallel, and a separator (optionally labeled B) for barriers.

Consider these questions:

  • What if we only have two cores available (and why might that be)?
  • Can we get around having a single process divide the deck into suits?
  • Do we even really have to divide the deck into suits?

Key Points:

  • This approach works well because each process is working with its own region of the array. Things get complicated if more than one process accesses/modifies the same array
  • We use processes/threads to abstract away from knowing about physical processors. Point out this could be done on two processors, each juggling 2 threads. Does throwing more than 4 processors/cores help us out at all?
  • Point out that there is a limit to “how parallel” a problem can be. We'd like embarrassingly parallel problems, but the world is not often that nice
  • Master/slave is now Supervisor/worker or Supervisor/peer (use text terminology)
cs415/design_intuition.txt · Last modified: 2017/09/28 13:18 by scarl