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

19/19基于mapreduce的稀疏矩阵乘法算法 组长：吴建堃 组员：白野 朵宝宝目录一、课题研究目的二、稀疏矩阵介绍（1） 稀疏矩阵乘法介绍（三元组） 2 （2） Mapreduce介绍 4 （3） 实验环境配置 7 （4） 创建代码（来自网络的代码) 10（5） 组员总结 16 一、课题研究目的。 矩阵乘法运算是一种基本运算。而扩大矩阵乘法的运算规模并降低其运算时间,将有利于满足机器学习算法处理大规模数据的要求。将MapReduce并行框架用于分块矩阵乘法,实现一种用于大规模矩阵乘法运算的方法。理论分析和实验结果表明该方法在处理大规模矩阵乘法上具有极大的潜能,并且随着计算节点的增加从而获得较好的加速比。 二、稀疏矩阵介绍。 人们无法给出稀疏矩阵的确切定义，一般都只是凭个人的直觉来理解这个概念，即矩阵中非零元素的个数远远小于矩阵元素的总数，并且非零元素没有分布规律。 对于那些零元素数目远远多于非零元素数目，并且非零元素的分布没有规律的矩阵称为稀疏矩阵 （6） 稀疏矩阵乘法介绍（三元组）当矩阵M、N是稀疏矩阵时，我们可以采用三元组表的表示形式来实现矩阵的乘。 采用三元组表的方法来实现时，因为三元组只对矩阵的非零元素做存储所以可以采用固定三元组表a中的元素（i，k，Mik）（1im1，1kn1），在三元组表b中找所有行号为k的的对应元素（k，j， Nkj）（1km2，1jn2）进行相乘、 累加，从而得到Qij，即以三元组表a中的元素为基准， 依次求出其与三元组表b的有效乘积。 算法中附设两个向量num 、first ，其中numrow表示三元组表b中第row行非零元素个数（1rowm2）， firstrow表示三元组表b中第row行第一个非零元素所在的位置。显然，firstrow+1-1指向三元组表b中第row行最后一个非零元素的位置。 first1=1； firstrow=firstrow-1+numrow-1， 2rowm2+1。 这里，firstm2+1-1表示最后一行最后一个非零元素的存储位置。当三元组表a中第i行非零元素的列号等于三元组表b中非零元素的行号时，则元素相乘并将结果累加。 （7） Mapreduce介绍1、MapReduce是一种编程模型，用于大规模数据集（大于1TB）的并行运算。 2、特点：具有接口简单，健壮容错的特点。 3、关于map函数和reduce函数 MapReduce 的整体架构主要由map 和reduce 这两个函数组。其含义是：Map（映射）和Reduce（化简）。图 1 Mapreduce模式工作过程 用户输入一组键/值对，首先由map函数生成一批中间的键/值对，然后由reduce 函数将具有相同键的中间值合并，产生最后的结果。在这一过程中，由于MapReduce的数据本地化特性，计算都是在本地节点完成。用户在使MapReduce 开发时，只需要关注于应用本身，而不必关心底层的任务分发、并发控制、资源管理、容错等复杂细节。极大地方便了编程人员在不会分布式并行编程的情况下，将自己的程序运行在分布式系统上。因此，可以有效地将大规模矩阵乘法运算引入到MapReduce 并行框架中。4、 MapReduce 与传统并行编程模型的比较： 在传统并行编程过程中，程序员必须花大量的精力去处理进程间通信。WordCount被用来统计输入数据中各单词出现的次数。以WordCount 为例，MPI 的一种实现方式为：在各个MPI 进程完成各自的统计任务后，将结果汇总给某一个进程，然后由该进程进行最终统计。该实现方式很容易在完成最终统计任务的进程处形成通信瓶颈，而最终统计任务是以顺序方式完成，会导致统计效率低下。采用并行分类统计能提升效率，即收集各个进程获得的关于某个相同单词的局部统计信息，并将这些信息汇总给某个进程处进行分类统计。然而由于这种实现方式仅确定能产生某个单词统计信息的进程范围，因此会增加编程复杂度。 图 2 Mapreduce下WordCount运行过程 在 MapReduce 模型下，完成单词统计的具体步骤为：(1)用户编写Map 程序对出现的单词word 产生中间结果key/value 偶对，如。(2)这些分布产生的中间结果将按key 值的不同进行汇总处理，产生key(word)相同的value 列表，如，并作为Reduce 阶段的输入，这个阶段的工作将MapReduce策略，把对全局(或阶段性)计算结果有影响且有关联的value采用相同key 标志。由于这种策略的简单抽象，因此用户可以较容易地把握局部和全局关系，从而确保问题求解并行实现的正确性，并进一步降低并行分布式编程的难度。（8） 实验环境配置。（10分） 1、作为一个成熟的MapReduce 应用，Hadoop 被选为我们的实验平台，算法在Java JDK 1.7.0_09 上运行。 2、Hadoop和MapReduce的关系： hadoop是一种分布式系统的平台，通过它可以很轻松的搭建一个高效、高质量的分布系统，而且它还有许多其它的相关子项目，也就是对它的功能的极大扩充，包括Zookeeper,Hive,Hbase等。 MapReduce是hadoop的核心组件之一，hadoop要分布式包括两部分，一是分布式文件系统hdfs,一部是分布式计算框，就是mapreduce,缺一不可，也就是说，可以通过mapreduce很容易在hadoop平台上进行分布式的计算编程。3、如下实现环境配置：所用Linux版本：ubuntu-10.10Unbuntu介绍：以桌面应用为主题的Linux操作系统。支持x86、x64和ppc架构。使用unbuntu的原因免费 redhat主要还是服务器方面，而且收费。Ubuntu是完全免费的。界面非常友好界面友好表现在更适合初学者使用，功能查找比较简单。对硬件的支持非常全面最适合做桌面系统的Linux发行版本毋庸置疑，我们最熟悉的操作系统是Windows。所以希望选择一个跟Windows相似的操作系统。U图形界面的思想已经根深蒂固。Unbuntu的桌面系统做的比Redhat更成熟，容易上手,适合初学者作为一个初学者，之前没有接触过Windows以外的操作系统。所以我组选取的操作系统是unbuntu10-10.我组也安装了Redhat，但是在安装JDK的时候出现了无法获取权限的问题。因此放弃Redhat。从安装JDK的过程中，按照下面的安装步骤进行，没有出现任何问题。buntu下配置JDK: 先去 Oracle下载Linux下的JDK压缩包，我下载的是jdk-7u9-linux-i586.tar.gz文件，下好后直接解压 解压命令： sudo tar zxvf ./jdk-7u9-linux-i586.tar.gz 创建文件夹： sudo mkdir /usr/lib/jvm Step1: # 将解压好的jdk1.7.0_09文件夹用最高权限复制到/usr/lib/jvm目录里 sudo cp -r /jdk1.7.0_09/ /usr/lib/jvm/ Step2: # 配置环境变量 sudo gedit /.profile 在末尾加上: export JAVA_HOME=/usr/lib/jvm/jdk1.7.0_09 export CLASSPATH=.:$JAVA_HOME/lib:$JAVA_HOME/jre/lib export PATH=$JAVA_HOME/bin:$PATH 然后保存关闭，使用source更新下 source /.profile 使用env命令察看JAVA_HOME的值 env 如果JAVA_HOME=/usr/lib/jvm/jdk1.7.0_09，说明配置成功。 Step3: # 将系统默认的jdk修改过来 $ sudo update-alternatives -install /usr/bin/java java /usr/lib/jvm/jdk1.7.0_09/bin/java 300 输入sun jdk前的数字就好了 $ sudo update-alternatives -install /usr/bin/javac javac /usr/lib/jvm/jdk1.7.0_09/bin/javac 300 $ sudo update-alternatives -config java $ sudo update-alternatives -config javac Step4: 然后再输入java -version,看到如下信息，就说明改成sun的jdk了: java version 1.7.0_09 OpenJDK Runtime Environment (IcedTea7 2.3.3) (7u9-2.3.3-0ubuntu112.10.1) OpenJDK Server VM (build 23.2-b09, mixed mode) 配置hadoop:没有配置成功,所以没有自己编写代码。（9） 创建代码（来自网络的代码)。 稀疏矩阵的乘法只有在第一个矩阵的列数(column)和第二个矩阵的行数(row)相同时才有定义。一般单指矩阵乘积时，指的便是一般矩阵乘积。若A为ir矩阵，B为rj矩阵，则他们的乘积AB(有时记做A B)会是一个ij矩阵。其乘积矩阵的元素如下面式子得出: 对矩阵乘法的MapReduce实现方法是： Map函数：对于矩阵M的每个元素Mi,j，产生一系列的键值对(i,k)-(M,j, Mi,j),其中k=1,2，直到矩阵N的列数。同样，对于矩阵N的每个元素Nj,k，产生一系列的键值对(i，k)-(N,j,Nj,k),其中i=1,2，直到矩阵M的行数。 Reduce函数：根据MR的原理，相同键i,k的数据会发送个同一个 reduce。如果M为2*2矩阵，N为23矩阵，reduce函数需要处理的数据为：（1,1）-(M,1, M1,1)、(M,2, M1,2)、(N,1, N1,1)、(N,2, N2,1)，（1,2）-(M,1, M1,1)、(M,2, M1,2)、(N,1, N1,2)、(N,2, N2,2)，（1,3）-(M,1, M1,1)、(M,2, M1,2)、(N,1, N1,3)、(N,2, N2,3),（2,1）-(M,1, M2,1)、(M,2, M2,2)、(N,1, N1,1)、(N,2, N2,1)，（2,2）-(M,1, M2,1)、(M,2, M2,2)、(N,1, N1,2)、(N,2, N2,2)，（2,3）-(M,1, M2,1)、(M,2, M2,2)、(N,1, N1,3)、(N,2, N2,3)。 这样只要将所有(M,j, Mi,j)和(N,j, Nj,k)分别按照j值排序并放在不同的两个列表里面。将这个列表的第j个元素Mi,j个Nj,k相乘，然后将这些积相加，最后积的和与键(i,k)组对作为reduce函数的输出。对于上面的例子reduce的输出就是：（1,1）-（M1,1* N1,1+ M1,2* N2,1）（1,2）-（M1,1* N1,2+ M1,2* N2,2）（1,3）-（M1,1* N1,3+ M1,2* N2,3）（2,1）-（M2,1* N2,1+ M2,2* N2,1）（2,2）-（M2,1* N1,2+ M2,2* N2,2）（2,3）-（M2,1* N1,3+ M2,2* N2,3） 下面是MapReduce的实现步骤：(1).构造矩阵M：300*150；矩阵N：150*500。两矩阵的值放在一个M.data文件中，每行的格式为：文件标识#行坐标#列坐标#坐标值。 (2).基于上面的方法编写Map函数和Reduce函数。代码详见： importjava.io.IOException;importorg.apache.hadoop.conf.Configuration;importorg.apache.hadoop.fs.Path;importorg.apache.hadoop.io.Text;importorg.apache.hadoop.mapreduce.Job;importorg.apache.hadoop.mapreduce.Mapper;importorg.apache.hadoop.mapreduce.Reducer;importorg.apache.hadoop.mapreduce.lib.input.FileInputFormat;importorg.apache.hadoop.mapreduce.lib.output.FileOutputFormat;importorg.apache.hadoop.util.GenericOptionsParser;Public class MartrixMultiplication public static class MartrixMapper extends Mapper private Text map_key = new Text(); private Text map_value = new Text(); int rNumber = 300; int cNumber = 500; String fileTarget; String i, j, k, ij, jk; public void map(Object key, Text value, Context context) throws IOException, InterruptedException String eachterm = value.toString().split(#); fileTarget = eachterm0; if(fileTarget.equals(M) i = eachterm1; j = eachterm2; ij = eachterm3; for(int c = 1; c=cNumber; c+) map_key.set(i + # + String.valueOf(c); map_value.set(M + # + j + # + ij); context.write(map_key, map_value); else if(fileTarget.equals(N) j = eachterm1; k = eachterm2; jk = eachterm3; for(int r = 1; r=rNumber; r+) map_key.set(String.valueOf(r) + # +k); map_value.set(N + # + j + # + jk); context.write(map_key, map_value); public static class MartrixReducer extends Reducer private Text reduce_value = new Text(); int jNumber = 150; int M_ij = new intjNumber+1; int N_jk = new intjNumber+1; int j, ij, jk; String fileTarget; int jsum = 0; public void reduce(Text key, Iterable values, Context context) throws IOException, InterruptedException jsum = 0; for (Text val : values) String eachterm = val.toString().split(#); fileTarget = eachterm0; j = Integer.parseInt(eachterm1); if(fileTarget.equals(M) ij = Integer.parseInt(eachterm2); M_ijj = ij; else if(fileTarget.equals(N) jk = Integer.parseInt(eachterm2); N_jkj = jk; for(int d = 1; d=jNumber; d+) jsum += M_ijd * N_jkd; reduce_value.set(String.valueOf(jsum); context.write(key, reduce_value); public static void main(String args) throws Exception Configuration conf = new Configuration(); String otherArgs = new GenericOptionsParser(conf, args).getRemainingArgs(); if (otherArgs.length != 2) System.err.println(Usage: MartrixMultiplication );System.exit(2); Job job = new Job(conf, martrixmultiplication); job.setJarByClass(MartrixMultiplication.class); job.setMapperClass(MartrixMapper.class); job.setReducerClass(MartrixReducer.class); job.setOutputKeyClass(Text.class); job.setOutputValueClass(Text.class); FileInputFormat.addInputPath(job, new Path(otherArgs0); FileOutputFormat.setOutputPath(job, new Path(otherArgs1); System.exit(job.waitForCompletion(true) ? 0 : 1); (3).将运行的结果文件copy到本地,并使用check.py对结果中元素10,95的正确性进行验证。 运行结果：没有运行。 组员总结姓名：吴建堃我是本组组长，我给每个人的分工是,白野负责稀疏矩阵三元组实现矩阵乘法。朵宝宝负责的是Mapreduce思想的理解上，比如运行程序的工作原理。我主要负责使用虚拟机方面。在安装虚拟机，安装Linux和配置JDK上，花费的时间比较大。也不是很成功。但是我觉得我的收获是我了解了unbuntu。它拥有比较友好的界面，方便查找功能。而且安装也是比较简单。用VirtualBox虚拟机安装，只要按部就班就可以成功。在安装redhat上，我觉得步骤比复杂。首先是第一次运行需要安装。安装过程比较简单，但是在也出现了空间不足的情况，然后就修改内存大小。而且过程中有些选项理解比较模糊，就是一般按默认进行。然后配置JDK上出现了权限无法获取的问题。具体原因可能是开始没有卸载成功。包括改成可执行权限也没有成功。因为进度的关系，所以放弃redhat。然后使用ubuntu10-10.我认为这个系统更适合初学者，因为操作起来比较简单。包括可以再终端下解压缩，在终端下为profile文件增加代码。然后根据上面的步骤配置很成功。但是利用网络上的教程配置hadoop的过程中。前面都很顺利，该显示的都已经显示。但是却没有运行成功。没有出现： 具体原因应该是的hdfs文件系统没有格式化成功。但是在进度上没有时间再往下做。所以本实验终结在了这里。姓名：朵宝宝我们的网络工程项目是基于mapreduce的稀疏矩阵乘法算法。我们从最开始的不了解，我们的网络工程项目是基于mapreduce的稀疏矩阵乘法算法。通过图书馆和网上查到资料弄清了一些关于mapreduce的稀疏矩阵乘法算法，值到最后把这个项目课题基本做完。我们先对mapreduce 进行了了解。之后安装了虚拟机Linux，并分析了源代码。我们一个组共同努力，不同分工，在网上查阅了资料，整理资料。在这其中，我负责查阅了mapreduce思想的部分。其中遇到了很多困难，通过组长和其他同学的帮助，解决了不少的问题。