基于mapreduce的稀疏矩阵乘法算法.docVIP

基于mapreduce的稀疏矩阵乘法算法 组长：吴建堃 组员：白野 朵宝宝 目录 一、课题研究目的 二、稀疏矩阵介绍 稀疏矩阵乘法介绍（三元组）……………………… 2 Mapreduce介绍 …………………………………4 实验环境配置 …………………………………7 创建代码（来自网络的代码) ………………………10 组员总结 ……………………………………………16 一、课题研究目的。 矩阵乘法运算是一种基本运算。而扩大矩阵乘法的运算规模并降低其运算时间,将有利于满足机器学习算法处理大规模数据的要求。将MapReduce并行框架用于分块矩阵乘法,实现一种用于大规模矩阵乘法运算的方法。理论分析和实验结果表明该方法在处理大规模矩阵乘法上具有极大的潜能,并且随着计算节点的增加从而获得较好的加速比。 二、稀疏矩阵介绍。 人们无法给出稀疏矩阵的确切定义，一般都只是凭个人的直觉来理解这个概念，即矩阵中非零元素的个数远远小于矩阵元素的总数，并且非零元素没有分布规律。 对于那些零元素数目远远多于非零元素数目，并且非零元素的分布没有规律的矩阵称为稀疏矩阵 稀疏矩阵乘法介绍（三元组） 当矩阵M、N是稀疏矩阵时，我们可以采用三元组表的表示形式来实现矩阵的乘。 采用三元组表的方法来实现时，因为三元组只对矩阵的非零元素做存储所以可以采用固定三元组表a中的元素（i，k，Mik）（1≤i≤m1，1≤k≤n1），在三元组表b中找所有行号为k的的对应元素（k，j， Nkj）（1≤k≤m2，1≤j≤n2）进行相乘、 累加，从而得到Q［i］［j］，即以三元组表a中的元素为基准， 依次求出其与三元组表b的有效乘积。 算法中附设两个向量num［ ］、first［ ］，其中num［row］表示三元组表b中第row行非零元素个数（1≤row≤m2）， first［row］表示三元组表b中第row行第一个非零元素所在的位置。显然，first［row+1］-1指向三元组表b中第row行最后一个非零元素的位置。 first［1］=1； first［row］=first［row-1］+num［row-1］， 2≤row≤m2+1。 这里，first［m2+1］-1表示最后一行最后一个非零元素的存储位置。当三元组表a中第i行非零元素的列号等于三元组表b中非零元素的行号时，则元素相乘并将结果累加。 Mapreduce介绍 1、MapReduce是一种编程模型，用于大规模数据集（大于1TB）的并行运算。 2、特点：具有接口简单，健壮容错的特点。 3、关于map函数和reduce函数 MapReduce 的整体架构主要由map 和reduce 这两个函数组。其含义是：Map（映射）和Reduce（化简）。 图 1 Mapreduce模式工作过程 用户输入一组键/值对，首先由map函数生成一批中间的键/值对，然后由reduce 函数将具有相同键的中间值合并，产生最后的结果。在这一过程中，由于MapReduce的数据本地化特性，计算都是在本地节点完成。用户在使MapReduce 开发时，只需要关注于应用本身，而不必关心底层的任务分发、并发控制、资源管理、容错等复杂细节。极大地方便了编程人员在不会分布式并行编程的情况下，将自己的程序运行在分布式系统上。因此，可以有效地将大规模矩阵乘法运算引入到MapReduce 并行框架中。 MapReduce 与传统并行编程模型的比较： 在传统并行编程过程中，程序员必须花大量的精力去处理进程间通信。WordCount被用来统计输入数据中各单词出现的次数。以WordCount 为例，MPI 的一种实现方式为：在各个MPI 进程完成各自的统计任务后，将结果汇总给某一个进程，然后由该进程进行最终统计。该实现方式很容易在完成最终统计任务的进程处形成通信瓶颈，而最终统计任务是以顺序方式完成，会导致统计效率低下。采用并行分类统计能提升效率，即收集各个进程获得的关于某个相同单词的局部统计信息，并将这些信息汇总给某个进程处进行分类统计。然而由于这种实现方式仅确定能产生某个单词统计信息的进程范围，因此会增加编程复杂度。 图 2 Mapreduce下WordCount运行过程 在 MapReduce 模型下，完成单词统计的具体步骤为