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

1. Title:
   CUB Programming Exercise - Intro to Parallel Programming
2. Description:

3. 0 0:00 - 0:04
   So when I run all of these, this one is slightly the fastest of all of these on the diagonal--
4. 4421 0:04 - 0:10
   64 threads per block operating on 16 items each.
5. 9965 0:10 - 0:14
   And so the thing to notice is that throughput is generally increasing
6. 13889 0:14 - 0:17
   as the granularity per thread increases, right?
7. 17159 0:17 - 0:22
   So having threads do more and more serial work is generally a good thing.
8. 21758 0:22 - 0:24
   On the other hand, if you've got a fixed tile size--
9. 24168 0:24 - 0:29
   in other words, the tile here is the total number of items that we're scanning over--
10. 28763 0:29 - 0:33
    for a fixed tile size there's diminishing returns.
11. 33366 0:33 - 0:38
    The improvements get smaller and smaller as you approach this sweet spot
12. 37780 0:38 - 0:43
    because you're trading off increased granularity per thread for decreased parallelilsm.
13. 43226 0:43 - 0:46
    And then it starts to go up again, and in my measurements on Fermi,
14. 46104 0:46 - 0:50
    which is the same GPU that you'll be using on the Udacity IDE,
15. 50151 0:50 - 0:56
    I get 32x32 being slightly slower than 64 threads with 16 items each.
16. 56349 0:56 - 1:03
    And at some point, you get to the point where you can no longer fit a problem size
17. 62821 1:03 - 1:07
    in a single thread's registers, and then performance falls of a cliff again.
18. 67235 1:07 - 1:13
    And for me on Fermi, 64 items per thread running at only 16 threads
19. 72749 1:13 - 1:16
    really starts to get pretty bad performance again.
20. 76390 1:16 - 1:20
    I encourage you to play around, experiment a little bit more
21. 79545 1:20 - 1:22
    to see what the rest of this matrix looks like.
22. 82222 1:22 - 1:30
    And if you're interested, go check out the CUB homepage and see what else you can do.
23. 89634 1:30 - 1:32
    There's different varieties of block scan, for example.
24. 92320 1:32 - 1:37
    There's work-efficient and step-efficient varieties of block scan,
25. 96507 1:37 - 1:42
    and so experiment a little bit and see how fast you can get this scan throughput,
26. 101525 1:42 - 1:45
    how few clocks you can spend per element scanned.
27. 105187 1:45 - 1:47
    And what I've found is that with the right balance,
28. 107220 1:47 - 1:51
    you can have a computational overhead of less than 1 clock cycle per item scanned.
29. 111056 1:51 - 1:53
    That is really pretty remarkable.
30. 113118 1:53 - 1:56
    Think about running this code on a CPU.
31. 115568 1:56 - 1:59
    You couldn't really achieve less than 1 clock per item scanned.