English subtitles

← List Ranking Part1 - Intro to Parallel Programming

Get Embed Code
2 Languages

Showing Revision 4 created 05/25/2016 by Udacity Robot.

  1. So let's try a slightly harder algorithm called list ranking.
  2. In list ranking, each node has the index of its successor in the list,
  3. and we know the first element in the output.
  4. What we want to be able to do is put the nodes in order.
  5. This has a number of uses, and in our lab, we've used it to decompress data
  6. that's been compressed with B sub 2, so let's take a look at an example.
  7. As an example we've got 10 nodes here.
  8. We know that the output is going to begin with node 0
  9. and the successor to node 0, so one farther in the chain is node 5.
  10. The successor to node 5 is node 2.
  11. The successor to node 2 is node 7 and so on.
  12. So this is our input--this array of 5, 6, 7, 9, 2, 3, 0, 1.
  13. What's our output going to be?
  14. It's going to be the chain 0, 5, 2, 7, 4, 9, 1, 6, 3, 8.
  15. So here's our input, and here's the output.
  16. Now, you can note that the array is actually circular,
  17. so it's necessary to actually designate the starting point,
  18. and in this case we're saying that node number 0 is the starting point.
  19. Of course, a serial processor could do this N steps.
  20. The question is, how can we make it work with parallel hardware
  21. with a smaller number of steps?