English subtitles

← Recap of the Algorithm - Intro to Parallel Programming

Get Embed Code
2 Languages

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

  1. Finally, we initialize the algorithm by setting the starting nodes depth to 0
  2. and the initial frontier to that node's neighbor list.
  3. So let's recap the big idea here.
  4. The basic step is a sparse copy.
  5. We start with a frontier, we look up the adjacency lists for the vertices in that frontier,
  6. and then we copy them into a contiguous block to make the next frontier, and then repeat.
  7. The result is a really fast breadth first search, one that runs in linear work
  8. and achieves on the order of 3.3 billion vertices per second on a GPU.
  9. This is conservatively 4 times faster than a optimized CPU implementation.