基于hadoop大矩阵乘法处理方法

《基于hadoop大矩阵乘法处理方法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、基于Hadoop大矩阵乘法处理方法　　摘要：目前的矩阵乘法算法无法处理大规模和超大规模的矩阵，而随着MapReduce编程框架的提出，并行处理矩阵乘法成为解决大矩阵运算的主要手段。总结了矩阵乘法在MapReduce编程模型上的并行实现方法，并提出了实现高性能大矩阵乘法的策略——折中单个工作节点的计算量和需要网络传输的数据量。实验证明，并行实现算法在大矩阵上明显优于传统的单机算法，而且随着集群中节点数目的增多，并行算法会表现出更好的性能。关键词：大矩阵；矩阵乘法；矩阵运算；MapReduce；Hadoop；并行计算；海量数据中

2、图分类号：TP391；TP311文献标志码：A0引言随着数据规模的爆炸性增长，我们希望数据挖掘算法能够适应当前不断增长的数据处理要求。19矩阵乘法算法广泛应用于图像处理、推荐系统、数据降维等数据挖掘领域，然而，传统的技术架构和仅靠单台计算机基于串行的方式越来越不适应当前海量数据处理的要求。因此，扩大矩阵乘法的运算规模并降低其运算时间，将有利于满足矩阵分解算法处理大规模数据的要求。然而，矩阵乘法具有较高的时间复杂度，因此利用并行方法降低矩阵乘法的运算时间得到了广泛的研究与应用。随着技术的发展，单机的性能有了突飞猛进的提升，尤其

3、是内存和处理器等硬件的性能，但是硬件技术的发展在理论上总是有限度的，如果说硬件性能的提升在纵向上提高了系统处理数据的能力，那么并行技术的发展就是从横向上拓展了系统的性能。但是，目前许多并行技术依赖于分布式文件系统[1]，当要处理的文件规模很大时，连接分布式文件系统网络的带宽，便成了制约系统性能的瓶颈。MapReduce[2]是由Google公司推出的一个用于处理大规模数据集并行运算的软件框架，该架构能够在大量普通配置的计算机上实现并行化处理。根据MapReduce框架，Apache基金会开发了开源项目Hadoop[3]，因其

4、在处理海量数据时所表现出的显著性能以及编程模型的简易性吸引了业界人士的广泛关注。Hadoop中基于GFS（GoogleFileSystem）[4]原理的模块Hadoop分布式文件系统（HadoopDistributeFileSystem，HDFS）有效地利用数据的本地特性，很好地解决了网络带宽的瓶颈问题。一些基于MapReduce并行框架的机器学习算法如K均值和K近邻等算法都已经在Hadoop上实现，并获得了良好的算法性能[5-6]。所以本文选择在Hadoop平台上实现矩阵乘法的分布式算法。19传统矩阵乘法通过求左矩阵行与右

5、矩阵列的内积来求解矩阵的乘积。这种算法可以实现为分布式算法，但是其性能不容乐观。对于矩阵乘法的另外一种形式是将左矩阵的列和右矩阵相应的行进行外积运算，从而得到结果矩阵的部分结果，最后对各个部分结果求和。虽然在并行化方面，这种算法与传统算法相比在效率有了很大提升，但也存在一定的瓶颈：当矩阵规模非常大，大到单个机器的内存不能存放左矩阵的一行和右矩阵的一列时，便不能计算。解决这一瓶颈的另一种方法，就是将相乘的两个矩阵分块[7]，计算小块的乘积，从而可以实现无限大的矩阵乘法，当然这样需要很多的额外处理，但是当分布式集群中的计算节点达

6、到一定数量时，损失的时间可以用节约的计算时间弥补。本文在Hadoop框架上讨论矩阵乘法的各种实现方法，并实验对比各种方法的适用情形。1矩阵乘法相关研究矩阵运算在数据挖掘领域有着广泛的应用，比如图像处理、文本挖掘[8]、推荐系统和生物信息学等。矩阵乘法是矩阵运算中的一项重要运算。在矩阵分解方法并行化处理中，矩阵乘法在总计算量中占据很大比重[9-11]。目前研究学者已经提出了很多矩阵乘法的算法并对这些算法进行了优化，但这些算法大都基于单机运行。19传统矩阵乘法的时间复杂度是O（n3），1969年Strassen利用分治算法，将时

7、间复杂度降至O（n2.8074），Strassen算法的这一优化在现实实践中得到了广泛的应用[12]。后面虽然仍在改进，但时间复杂度降低很小。针对这些算法现在已经开发了一些包，比如Jampack[13]和JAMA[14]。这些软件包没有采用并行技术，不能解决我们当前面临的海量数据问题。由于矩阵运算在各领域的广泛应用，这一问题能够得到有效解决将是一件非常有意义的事。因此，有许多学者将注意力转向矩阵运算的并行处理，经过不断的努力，提出了很多基于多核的高性能单机算法，并开发出了很多成熟的算法库，比如PSBLAS[15]。虽然性能上

8、有一定提升，但是这些并行技术是基于多线程的，它们利用线程之间共享资源的轻量性；而分布式集群中的数据共享和通信不是轻量的，多线程并行算法的实现都需要将数据读入到计算机的内存当中，因此，当处理的数据量增大时，单机内存容量便成为算法处理数据的瓶颈。随着信息爆炸时代的到来，大部分研究学者逐渐将注意