## ← Merrills Linear-Complexity BFS on GPUs Part2 - Intro to Parallel Programming

• 4 Followers
• 36 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=MAEnPtS8ZnA" data-team="udacity"></div> ``` 2 Languages

• English [en] original
• Chinese, Simplified [zh-cn]

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

1. Way back in Unit 1, when we talked about step in work complexity, we said that
2. we would love to find algorithms that have the same work complexity as the serial
3. algorithm but have a smaller step complexity.
4. Reduce would be a good example here, or scan.
5. But if we said we can't do that, sometimes we would be willing
6. to accept more work if it gets us fewer steps.
7. And that's what we are going to do here. But how?
8. This is not intuitive, or more at least it isn't for most people,
9. and it certainly wasn't for me when I learned this material.
10. Hills and Steele first expressed skepticism they could improve on quadratic work,
11. but then concluded--and I am quoting from their paper--essentially we overlooked
12. the power of having many processors working on the problem at once.
13. So at a high level, here's what we are going to do.
14. On every node, we start by knowing the node that's 1 hop away. That's the next pointer, in blue.
15. So on the next iteration, we can visit our next pointer's next pointer, and get 2 hops away.
16. And then, on the next iteration, we can get to 3 hops away, and so on.
17. So that's what I am showing here when I say straight forward approach.
18. As we increase the number of iterations, we are also increasing the number of hops away.
19. But that's the wrong way to think about it.
20. If we just did it that way, we'd be repeating a lot of work that the nodes down the chain are doing,
21. and we would have quadratic complexity work.
22. Instead, after the first iteration, we have each node knowing the node that is 2 hops away.
23. So let's say we're interested in this node and we know that we are pointing to node x here.
24. Well normally what we'd do is we'd take the red pointer here,
25. and then change our red pointer to be red pointer plus blue pointer.
26. So, we'd be moving from knowing the node 2 hops away to the node knowing 3 hops away.
27. But look, x also knows the node that is 2 hops away.
28. So, I know the node that's 2 hops away, x knows the node that's 2 hops away.
29. So, on the second iteration we can leverage the work that x already did
30. on it's first iteration to get a pointer that is now 4 hops away.
31. So we can go red, then red to set our new red pointer here, to be the chum of the chum.
32. Now we are going to have a pointer to a node that is 4 hops away,
33. which also has a pointer to a node that is 4 hops away.
34. So the next iteration will have a pointer that is 8 hops away and so on.
35. So now, instead of going 1, 2, 3, 4, we're now going 1, 2, 4, 8.
36. So for N iterations, as a function of N, how many steps is this going to take?