## ← Scan Recap - Intro to Parallel Programming

• 4 Followers
• 19 Lines

### Get Embed Code x Embed video Use the following code to embed this video. See our usage guide for more details on embedding. Paste this in your document somewhere (closest to the closing body tag is preferable): ```<script type="text/javascript" src='https://amara.org/embedder-iframe'></script> ``` Paste this inside your HTML body, where you want to include the widget: ```<div class="amara-embed" data-url="http://www.youtube.com/watch?v=ApFfM2Hfhx0" data-team="udacity"></div> ``` 2 Languages

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

1. All right, welcome to Unit 4. Today we're going to talk about fundamental GPU algorithms, part 2.
2. We're going to start with scan, which we talked about last week, and look at specific applications of scan.
3. And then we're going to turn to looking at how to sort on a GPU.
4. So in the last unit we learned about fundamental GPU algorithms.
5. And the last one, and the most important one for this lecture, was scan.
6. Scan is an efficient way to paralyze a certain class of
7. parallel problems that otherwise seem difficult to paralyze.
8. We usually refer to these as recurrence relationships.
9. One of the use cases for scan is for problems that keep
10. some sort of running total, such as a running sum.
11. We can also use other binary associative operators like Max, Min and Most Logical operations.
12. So, as a quiz, let's recall 2 of the important properties of scan.
13. So we're looking at a scan of n elements.
14. And so, in the best GPU scan implementations,
15. what is the amount of work to do the scan, and what is the number of steps to do the scan?
16. Your choices are proportional to log n, proportional to n,
17. proportional to n log n, and proportional to n squared.
18. So we'd like you to check the box that corresponds to what the work complexity of the algorithm is
19. and what the step complexity of the algorithm is.