Vector Multiplication with Map-Reduce

Vector Multiplication

• Task: multiply 2 arrays of N numbers

  A basic mathematical operation

  Let’s assume N is very large

  向量乘法问题描述：

  

  当N非常大时，如何使用map-reduce解决？

  所以，先回想一下map之前，是不是先要将文件spilt一下？

  

  但是问题来了，spilt之后，如何知道哪个跟哪个是对应的呢？因为这个切分后的文件里面都只有数值，并没有标号，也就是没有 <key,value> <script id="MathJax-Element-994" type="math/tex"> </script>中的key，只有value

  Hadoop提供解决方法：

  

  Map阶段对数据进行标记，以行号作为key，值作为value，mapper的主要作用是标记数据

  

  Shuffle阶段：

  

  Reduce阶段：

  我们已经知道每行对应的数值了，比如说(1,5),(1,2.7)对应的是A的第一行的5，和B的第一行的2.7，那么他们的乘积也就可得了，以此类推，得到的结果进行累加，即可得到A,B向量乘法的结果了

  

Computational Costs

• For Vector Multiplication

  How many <index,number> <script id="MathJax-Element-988" type="math/tex"> </script> are output from map()?

  2个向量，一个key，一个value，N行，显而易见，会输出2N个 <index,number> <script id="MathJax-Element-989" type="math/tex"> </script>

  

  How many <index> groups have to be shuffled?

  

  Can we reduce shuffling?

• Try: ‘combine’ map indices in mapper (works better for Wordcount)

  hadoop中的combine函数，本质上是一个本地的reducer。其设计初衷是在本地将需要reduce操作的数据就行合并，以减少不必要的通信代价，combine可以提高hadoop的运行性能。

  因为combine的输入是map的输出，combine的输出是reduce的输入， 而map的输出和reduce的输出是一致的，所以，我们需要确保combine的输入和输出是一样的， 另外还要考虑本地的reduce对最终的结果是否有影响，比如wordcount，他在本地做累加对最终的结果是没有影响，可以使用combine； 但是计算平均数就不行了，主要这个过程有信息的丢失。

• Or Try: use index ranges of length R

  

  将原先的N行数据，分为N/R行。

  

  比如说原先的第一行数据5，这时候由 <1,5> <script id="MathJax-Element-991" type="math/tex"><1,5></script>变为 <1,1,5> <script id="MathJax-Element-992" type="math/tex"><1,1,5></script>

  此时如何计算向量乘法呢？

  可以这样想，先通过index bin定位到具体的bin中，在具体的bin中，通过original-index定位到具体的行号，然后进行计算。

  此时的shuffling的花费取决于N/R个group

  

  平衡计算花费：