English 字幕

← Quick Sort - Intro to Parallel Programming


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

  1. The final sort algorithm we'll discuss is one of the most efficient ones for serial processors;
  2. this is quick sort. It is a more complex algorithm on GPUs
  3. because of the control complexity of the algorithm, so let's recap what the quick sort algorithm does.
  4. First, it chooses a pivot element, one particular element from within its input,
  5. then it compares all of the elements in its input to the pivot,
  6. and it uses that comparison to divide the input into 3 sub-arrays.
  7. Those that are less than the pivot, those that are equal to the pivot,
  8. and those that are greater than the pivot, and then it calls quick sort on each of these sub-arrays
  9. and continues until the entire input is sorted.
  10. As an example, let's look at a particular array and choose that the pivot is equal to 3.
  11. So what we're going to do here is compare each one of these elements to the pivot,
  12. and we're going to decide if they're equal to, greater than, or less than the pivot.
  13. Then we'll divide it into 3 arrays, those that are less than the pivot,
  14. those that are equal to the pivot, and those that are greater than the pivot,
  15. and we'll call quick sort on each of these arrays and do the same thing.
  16. So when we have 2 and 1, let's say we choose 2 as the pivot,
  17. then we'll divide this into smaller than the pivot and equal to the pivot.
  18. This doesn't need to be recursed because it only has a single element.
  19. And let's say we choose 4 as the pivot here, this is greater than the pivot, this is equal to the pivot,
  20. and now we have a completely sorted array.
  21. So this is a very challenging algorithm to implement on the GPU.
  22. The other algorithms that we've looked at are pretty simple to describe, and they don't recurse.
  23. This one is more complex, and until very recently GPUs didn't support recursion at all.
  24. Indeed, the GPUs we use in this class don't support recursion currently.
  25. So how can we take this seemingly recursive-only algorithm and map it to the GPU using the primitives that we've learned?
  26. So I'm bringing up this example for two reasons.
  27. The first is that you have already learned all the pieces that you need to implement quick sort on the GPU,
  28. and the second is to motivate the benefits of new GPU capabilities that do natively support recursion.
  29. So we can implement quick sort without recursion by using the idea of segments.
  30. Recall that segmented operations, like scans, only operate within a single segment;
  31. operations on one segment don't affect other segments.
  32. That sounds a little bit like recursion, and in fact it maps in a similar way.
  33. For quick sort, when we begin to process the initial array,
  34. we're going to use distributes, maps, and compacts to eventually divide it into 3 segments.
  35. We can use segmented scans to do all the necessary operations that we need to make this work,
  36. including distributing a pivot across a segment for comparisons and splitting a segment,
  37. which is similar to the way that we split on a particular bit in radix sort.
  38. Quick sort is interesting because it shows you how useful segments can be,
  39. that they can let you mirror the same approach you use in recursion, without actually using recursion.
  40. But, and I gotta be perfectly honest here,
  41. it's really a challenge to implement and equally challenging to make it fast.
  42. So it's very exciting that the newest in video GPUs support a more flexible programming model where kernels can actually call,
  43. can launch other kernels, which makes quick sort's recursive calls much more straightforward.
  44. We're not using this new capability in the class.
  45. The Amazon instances where our code is running don't have these new GPUs that support this capability at this time,
  46. but it's really exciting, and so when we get to unit 7,
  47. we'll see exactly what it looks like and how it applies to Quick sort.