YouTube

Got a YouTube account?

New: enable viewer-created translations and captions on your YouTube channel!

English subtitles

← Reduce Part 2 - Intro to Parallel Programming

Get Embed Code
2 Languages

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

  1. So we're going to start with the mathematical definition of reduce.
  2. Reduce has 2 inputs.
  3. The 1st input is a set of elements, and we're going to assume they're in an array.
  4. The 2nd input is a reduction operator that will operate on the elements in this array.
  5. For example, we have a list of numbers here,
  6. and we have a reduction operator of plus,
  7. and the reduction operator will sum them all up.
  8. Let's be a little more precise in terms of what operators we're going to support
  9. with our parallel implementation.
  10. Our operators need to have the following 2 characteristics.
  11. The 1st is that the operators are binary.
  12. The operator must operate on 2 inputs and create 1 output.
  13. Plus is a binary operator, for instance.
  14. Two, associative.
  15. Associativity means that if we have 2 or more operations in a row,
  16. a op b op c, the order of operations doesn't matter
  17. as long as the order of the operands aren't changed.
  18. To put it simply, a op b, take the result and op it with c,
  19. needs to give you the same answer as b op c,
  20. and then you op the result with a.
  21. You should convince yourself that plus is an associative operator but minus is not.
  22. Now, it's not immediately clear why we need this property
  23. but we're going to see why in a few minutes.