article20201101

大数据 | 大数据基础--算法之并行计算算法：基本问题（二）

亲爱的读者朋友大家晚上好，上次我们简单介绍了并行算法以及有关矩阵乘法的几个基本问题。

简介

上次提到我们主要分析用Map Reduce框架来设计问题的并行计算方法，先简单回顾一下框架的内容。

MapReduce

使用MR模型进行计算有几个要点：

• 计算分轮次进行，每一轮的输入和输出的数据都是形如\(<key,value>\)的
• 每一轮分为：Map、Shuffle、Reduce
• Map：每个数据被map函数处理，输出一个新的数据集合，也就是改变了\(<key,value>\)
• Shuffle：对编程人员透明，所有在Map中输出的数据，被按照key分组，具备相同key 的数据被分配到相同的reducer
• Reduce：输入\(<k,v_1,v_2,...>\)，输出新的数据集合
• 针对这样的计算框架，我们的设计目标为：更少的轮数、更少的内存、更大的并行度

问题实例：矩阵乘法

就是简单的矩阵乘法，我们知道，普通的矩阵乘法的时间复杂度是\(O(m\cdot n \cdot d)\)，对于一个\(m\cdot d\)和\(d \cdot n\)的矩阵相乘。通过并行计算框架我们极大加速这个过程的执行，具体的两个方法如下面所示（ps：实现的方法有很多，这里只是给出两个例子供大家参考）：

矩阵乘法1

定义：矩阵\(A\)和矩阵\(B\)，\((A,i,j)\)指向矩阵\(A\)的第\(i\)行\(j\)列的元素，但并不是真实的这个元素，而是表示一种索引，\(a_{ij}\)表示的则是这个元素。

• Map：
  • \(((A,i,j),a_{ij}) \rightarrow (j,(A,i,a_{ij}))\)
  • \(((B,j,k),b_{jk}) \rightarrow (j,(B,k,b_{jk}))\)
• Reduce：\((j,(A,i,a_{ij})),(j,(B,k,b_{jk})) \rightarrow ((i,k),a_{ij} * b_{jk})\)
• Map：nothing（identity）
• Reduce：\(((i,k),(v_1,v_2,\dots)) \rightarrow ((i,k),\sum v_i)\)

思路剖析：目标矩阵上的每个元素都是由\(d\)个中间元素（\(a_{ij} * b_{jk}\)）累加得到的，我们先统把这样的所有的元素求出来，然后累加起来即可。对于目标矩阵上的每个元素都是如此。

矩阵乘法2

• Map函数：
  • \(((A,i,j),a_{ij}) \rightarrow ((i,x),(A,j,a_{ij}))\ for \ all \ x \in [1,n]\)
  • \(((B,j,k),b_{jk}) \rightarrow ((y,k),(B,j,b_{jk}))\ for \ all \ y \in [1,m]\)
• Reduce函数：\(((i,k),(A,j,a_{ij}))\wedge((i,k),(B,j,b_{jk})) \rightarrow ((i,k),\sum a_{ij} * b_{jk})\)

思路剖析：相对于第一个方法，方法2先不把中间元素求出来，而是把求解每个目标矩阵上要用到的\(2d\)个基本元素都放到一起，然后进行点积操作。

总结

以上就是利用并行计算解决矩阵乘法的两个简要思路，下次我们会继续应用这个计算框架解决排序问题，敬请期待。