基于Hadoop的大矩阵乘法处理方法文作者孙远帅报告人.pptVIP

下面探讨分块算法的扩展性。本组实验通过不断增加集群中工作节点数量进行实验，从集群中4个工作节点开始依次递增1个工作节点，直到增加到7个工作节点。从实验结果可以看出，随着集群中工作节点的增多，集群计算能力不断提高，从而使得运行时间逐渐缩小。 * 基于Hadoop的大矩阵乘法处理方法 论文作者：孙远帅 报告人：李培 * * 1 3 4 MapReduce编程模型 研究意义 本文工作 主要内容 2 矩阵乘法发展 * * 1 研究意义 * * 从优化单机算法角度很难有提升； 通过改进硬件的性能； 从技术手段来计算大矩阵乘法； 2 矩阵乘法发展 * * 3 MapReduce编程模型 MapReduce编程模型 * * 4 本文工作 a11 a12 a13 a21 a22 a23 a31 a32 a33 a41 a42 a43 左矩阵A b11 b12 b13 b14 b21 b22 b23 b24 b31 b32 b33 b34 右矩阵B 内积法 外积法 分块矩阵乘法 c11 c12 c13 c14 c21 c22 c23 c24 c31 c32 c33 c34 c41 c42 c43 c44 结果矩阵C C = AB 介绍矩阵的分布式乘法时，假设： 左矩阵A是m×s 右矩阵B是s×n 结果矩阵C是m×n * * 4 本文工作 …. …. 内积法 * * 4 本文工作 内积法数据流程图 内积法中Reduce任务与数据的对应关系 注：R_i_j表示Reduce任务的编号 并发粒度：m×n×s 中间shuffle数据量： n个A矩阵，m个B矩阵，即2s个C矩阵 * * 4 本文工作 + + = 外积法 * * 4 本文工作 外积法数据流程图 外积法中Reduce任务与数据的对应关系 注：R_i_j表示Reduce任务的编号 并发粒度：s 中间数据量： Job1的shuffle 数据量：一个A矩阵和一个B矩阵 Job1到Job2的IO数据量：s个C矩阵 Job2的shuffle数据量：远小于s个C矩阵 * * 4 本文工作 把左矩阵划分为m1×s1等大小的矩阵，右矩阵划分为s1×n1的等大小矩阵，则有： M = (m - 1)/m1 + 1 S = (s - 1)/s1 + 1 N = (n - 1)/n1 + 1 并发粒度：M×N×S 中间数据量：N个A矩阵和M个B矩阵 * * 实验平台和环境 所有实验均在一个由7台机器组成的集群中完成。集群采用Hadoop 1.0版本，由1个NameNode和7个DataNode构成。每个节点CPU为i5-2300 2.8G，4核8线程，内存容量为32G，操作系统使用Ubuntu 12.04。 * * 4 本文工作 4 本文工作 矩阵规模与运行时间的关系 * * 4 本文工作 矩阵稀疏度与运行时间的关系 * * 4 本文工作 分块策略与运行时间的关系 分块策略与中间数据量的大小关系 * * 4 本文工作 工作节点数量与运行时间的关系 * * * * 论文作者：孙远帅 电子邮箱：sys@stu.xmu.edu.cn 联系电话欢迎批评指正 * 主要从以下四个方面来论述本文工作 本论文的研究意义； 矩阵乘法发展现状； Hadoop相关技术； 本文工作。 大数据时代已经到来，对传统的各个领域的数据挖掘方法提出了很大的挑战，生物信息学，文本挖掘，电子商务，图像处理。各种数据挖掘方法都有涉及到矩阵运算，矩阵乘法是一项重要的矩阵运算，如果能顺利解决大矩阵相乘问题，很多问题都能迎刃而解。这就好比一个大金矿，解决了大矩阵乘法之后，就好比手里掌握了开采金矿的利器。下面说下，解决大矩阵乘法的历程。 传统矩阵乘法的时间复杂度是O(n3)，1969年Strassen利用分治算法，将时间复杂度降至O(n2.8074)，Strassen算法的这一优化在现实实践中得到了广泛的应用。后面虽然仍在改进，但时间复杂度降低很小。 随着技术的发展，单机的性能有了突飞猛进的提升，尤其是内存和处理器等硬件的性能，但是硬件技术的发展在理论上总是有限度的。 通过技术手段，多线程技术。虽然性能上有一定提升，但是受限于单机内存，不能处理较大规模的的数据。而有些学者尝试使用分布式算法，来解决这一问题，但是目前许多并行技术都受限于分布式文件系统网络的带宽。而Hadoop框架有效地利用数据的本地特性，很好地解决了网络带宽的瓶颈问题。下面我们介绍下Hadoop相关技术。 Hadoop是Apache基金会基于MapReduce编程模型开发。 MapReduce的执行流程是，首先用户程序调用Master节点和worker节点，Master节点对原始数据进行分片，形成输入文件分片；然后Master节点根据每个worker