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

1. Title:
   Reduction Using Global and Shared Memory - Intro to Parallel Programming
2. Description:

3. 0 0:00 - 0:03
   So now we've done all the preliminaries, so let's turn to some actual code.
4. 3015 0:03 - 0:07
   We're going to implement this twice with a similar strategy each time.
5. 6837 0:07 - 0:12
   In both we're going to implement a sum of a million--actually 2^20 elements,
6. 11659 0:12 - 0:14
   and we're going to do this in 2 stages.
7. 13963 0:14 - 0:18
   In the 1st stage we're going to launch 1024 blocks,
8. 17706 0:18 - 0:24
   each one of which will use 1024 threads to reduce 1024 elements.
9. 23833 0:24 - 0:28
   Each of those will produce 1 single item.
10. 28082 0:28 - 0:31
    So we're going to have 1024 items left when we're done.
11. 31210 0:31 - 0:37
    And we're going to launch 1 block to reduce the final 1024 elements into 1 single element.
12. 37327 0:37 - 0:41
    So I'll post all the code, of course. But the CPU side code is straightforward.
13. 41055 0:41 - 0:45
    Instead we're just going to take a look at the kernel. Let's see how that works.
14. 44867 0:45 - 0:50
    So each block is going to be responsible for a 1024 element chunk of floats,
15. 50164 0:50 - 0:54
    and we're going to run this loop within the kernel.
16. 53630 0:54 - 0:59
    On each iteration of this loop we're going to divide the active region in half.
17. 59003 0:59 - 1:03
    So on the 1st iteration, where we start with 1024 elements,
18. 62678 1:03 - 1:07
    we're going to have two 512-element regions.
19. 66544 1:07 - 1:13
    Then each of 512 threads will add its element in the 2nd half to its element in the 1st half,
20. 73209 1:13 - 1:16
    writing back to the 1st half.
21. 75561 1:16 - 1:19
    Now we're going to synchronize all threads, this syncthreads call right here,
22. 79407 1:19 - 1:21
    to make sure every one is done.
23. 81231 1:21 - 1:24
    We've got 512 elements remaining,
24. 84015 1:24 - 1:28
    and so we're going to loop again on this resulting region of 512 elements.
25. 87798 1:28 - 1:34
    Now we'll divide it into two 256-element chunks using 256 threads
26. 93613 1:34 - 1:38
    to sum these 256 items to these 256 items.
27. 97971 1:38 - 1:42
    And we're going to continue this loop, cutting it in half every time,
28. 101819 1:42 - 1:47
    until we have 1 element remaining at the very end of 10 iterations.
29. 106967 1:47 - 1:51
    And then we'll write that back out to global memory. So this works.
30. 110659 1:51 - 1:53
    We can run it on a computer in our lab.
31. 112784 1:53 - 1:59
    So we're doing that now, and we notice that it finishes in 0.65 milliseconds.
32. 118933 1:59 - 2:04
    Less than a millisecond. That's pretty great, but it's not as efficient as we might like.
33. 124082 2:04 - 2:07
    Specifically, if we take a look at the code again,
34. 126786 2:07 - 2:10
    we're going to global memory more often than we'd like.
35. 130441 2:10 - 2:16
    On each iteration of the loop, we read n items from global memory and we write back n/2 items.
36. 136117 2:16 - 2:20
    Then we read those n/2 items back from global memory and so on.
37. 140479 2:20 - 2:28
    In an ideal world, we'd do an original read where we read all of the 1024 items into the thread block,
38. 147778 2:28 - 2:31
    do all the reduction internally, and then write back the final value.
39. 151286 2:31 - 2:36
    And this should be faster because we would incur less memory traffic overall.
40. 155700 2:36 - 2:38
    The CUDA feature we use to do this is called shared memory
41. 158387 2:38 - 2:43
    and will store all intermediate values in shared memory where all threads can access them.
42. 162651 2:43 - 2:46
    Shared memory is considerably faster than global memory.
43. 165645 2:46 - 2:49
    So let's take a look at the kernel. It's going to look very similar.
44. 169332 2:49 - 2:53
    And in this kernel we're going to have the exact same loop structure.
45. 173117 2:53 - 2:56
    What's going to be different, though, is this little part right here.
46. 176389 2:56 - 3:01
    We have to 1st copy all the values from global memory into shared memory
47. 181134 3:01 - 3:03
    and that's done with this little block.
48. 183387 3:03 - 3:07
    And then all the further accesses here are from shared memory--
49. 186932 3:07 - 3:11
    this s data--as opposed to from global memory, which we did last time.
50. 191203 3:11 - 3:15
    And when we're done, we have to write this final value back to global memory again.
51. 195260 3:15 - 3:20
    The only other interesting part of this code is how we declare the amount of shared memory we need.
52. 199879 3:20 - 3:21
    And we do that here.
53. 201481 3:21 - 3:26
    We're declaring that we're going to have an externally defined amount of shared data.
54. 206447 3:26 - 3:29
    Now, we haven't actually said how much we do,
55. 208559 3:29 - 3:32
    so to do that, we're going to have to go down to where we actually call the kernel.
56. 212058 3:32 - 3:35
    So when we're calling the reduce kernel using the shared memory,
57. 215372 3:35 - 3:41
    we call it with now 3 arguments inside the triple chevrons, the normal blocks and the threads,
58. 220606 3:41 - 3:45
    but then we say how many bytes we need allocated in shared memory.
59. 225180 3:45 - 3:51
    In this case, every thread is going to ask for 1 float stored in shared memory.
60. 230899 3:51 - 3:55
    So the advantage of the shared memory version is that it saves global memory bandwidth.
61. 235414 3:55 - 3:59
    It's a good exercise to figure out how much memory bandwidth you'll save.
62. 238679 3:59 - 4:00
    So I'll ask that as a quiz.
63. 240421 4:00 - 4:03
    The global memory version uses how many times as much memory bandwidth
64. 243389 4:03 - 4:05
    as the shared memory version?
65. 245023 4:05 - 4:07
    Round to the nearest integer.