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

1. タイトル：
   Quick Sort - Intro to Parallel Programming
2. 概説：

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