English subtitles

← Scan - Intro to Parallel Programming

Get Embed Code
2 Languages

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

  1. We're going to introduce one of the most important parallel primitives--scan.
  2. Let me give you a very short example of a scan operation.
  3. The input to scan is a list of numbers, such as 1, 2, 3, 4,
  4. and an operation, such as add,
  5. and the output is the running sum of those numbers.
  6. So each output is the sum of all the numbers in the input up to that given point.
  7. 6 is the sum of 1, 2, and 3.
  8. Scan is important because it allows us to address a set of problems
  9. that seem difficult to parallelize.
  10. At first glance it might seem difficult to compute this output from this input in parallel
  11. because each element in the output depends on the previous element.
  12. So 1st we compute this, add 2 and get 3, add 3 and get 6, add 4 and get 10.
  13. That doesn't seem like a very parallel operation.
  14. But this style of operation turns out to be incredibly useful.
  15. It's also interesting because scan is just not a very useful operation in the serial world.
  16. It's really only useful when you're doing parallel computation.
  17. But once you know it and use it, you'll wonder what you ever did without it.
  18. There's lots of uses for scan, with compaction and allocation being 2 of the most popular.
  19. Later in this lecture we'll discuss histogram, which uses scan.
  20. And our research group has used scan for quick sort, for sparse matrix computation,
  21. and for data compression, among others. It's a very useful parallel primitive.
  22. But for this part of the lecture I'm only going to concentrate on what scan does
  23. and how it works rather than how it's useful.
  24. We'll learn about some more general scan applications in the next unit.