1、中期检查报告中期检查报告云计算中并行计算模型的研究与应用云计算中并行计算模型的研究与应用 报告人：杨玲报告人：杨玲2010.6引言模型利用一个输入key/value对，来产生一个输出key/value对集。MapReduce库的用户用两个函数表达这个计算：map和reduce。1、用户自定义的map函数函数，接受一个输入对，然后产生一个中间key/value对集。2、MapReduce库把所有具有相同中间key I的中间value聚合在一起，然后把它们传递给reduce函数。3、用户自定义的reduce函数函数，接受一个中间key I和相关的一个value集。它合并这些value，形成一个比较
2、小的value集。云计算的核心技术之一是MapReduce，它为并行系统的数据处理提供了一个简单、优雅的解决方案。其主要目的目的是为了大型集群的系统能在大数据集上进行并行工作，并用于大规模数据的并行运算。研究内容1 云计算中并行计算模型云计算中并行计算模型MapReduce 模型的导入、来源、基本思想及原理2 MapReduce模型的实现模型的实现 对目前已有的实现进行分析，着重研究其开源并行编程平台Hadoop，分析HDFS和Hadoop MapReduce引擎3 MapReduce模型的应用模型的应用 利用MapReduce强大的计算能力，把MapReduce模型应用到图形算法BFS问题中
3、，最后利用Hadoop平台进行应用的实现4 模型应用的理论分析模型应用的理论分析 根据对实验结果进行对比分析，以及将其与Dijkstra算法和单机BFS问题进行比较，给出应用MapReduce模型的优缺点，并给出理论分析结果和应用前景分析。研究方法与技术路线（1）文献法、总结法1、阅读大量文献，并挑选出有用的部分资料（包括MapReduce相关知识及其几种实现方法）2、对挑选出的资料进行分析总结，确定最终的一种MapReduce实现作为自己的实验平台(Hadoop)，并对实验平台进行研究已完成研究方法与技术路线（2）个案研究法、实验法反复对Hadoop自带的实例wordcount进行揣测，不断
4、地进行改进调试及查看结果，目的在于解决自己问题中的难点，即MapReduce中(key,value)对的分割问题，最后再对自己的问题进行编程调试和实现。正在进行中研究方法与技术路线（3）测验法、实验法、总结法通过对已完成问题程序的输入数据进行更改，观察由于输入数据的变化所引起的不同的结果，最后对结果进行分析总结，给出模型应用的优缺点，并将与未进行模型应用的问题进行分析比较。待完成几种几种MapReduce模型的实现模型的实现HadoopMapReduce计算模型的开源实现 可以轻松地编写分布式并行程序，将其运行于计算机集群上，完成海量数据的计算 Mars在图形处理器(GPU)上的MapRedu
5、ce系统 利用众多的GPU线程来完成Map和Reduce很好的并发利用GPU的大量线程 phoenix在共享内存的体系结构上的MapReduce实现 在多核平台上，使程序执行得更高效，而且使程序员不必关心并发的管理 HPMR在多核集群上适于数值计算的MapReduce系统用多进程和多线程技术在多核集群上构造了一个分布式并行系统 本课题采用的是Hadoop平台Hadoop平台简介Hadoop 是一个开源分布式计算平台，也是一个能够分布式处理大规模海量数据的软件框架。它实现了 Map/Reduce 计算模型。借助于 Hadoop,程序员可以轻松地编写分布式并行程序，将其运行于计算机集群上，完成海量
6、数据的计算。Hadoop主要由以下两部分组成：1、HDFS（Hadoop Dsitributed File System）存储Hadoop集群中所有存储节点上的文件2、MapReduce引擎引擎（处于HDFS的上层）处理海量数据的分布式并行程序，并运行于大规模集群上。Hadoop基本架构图实验环境Windows XP+JDK+Cygwin+Hadoop五台实体机IP地址角色210.43.111.125Namenode,Jobtracker,Master210.43.111.59Datanode,Tasktracker,Slave210.43.111.121Datanode,Tasktracke
7、r,Slave210.43.111.93Datanode,Tasktracker,Slave210.43.111.90Datanode,Tasktracker,Slave210.43.111.125Datanode,Tasktracker,Slave其中，125节点既做master,也做slaveBFS（广度优先搜索）算法MapReduce在图形算法BFS上的应用 用文本文件存储图的整体结构，图的表示以邻接表邻接表的方式，每行代表图中的一个结点，格式如下：NodeidflagdistancePnodes and weight Nodeid:当前结点编号 Flag:处理标志，0表示未处理，1表示
8、现需处理，2表示完成处理，初始值为0。Distance:源点到当前结点的距离，初始值为。Pnodes and weight:当前结点可到达的后续结点及其权值的集合思路（图形表示）伪代码(Map)Class Mapper method Map(Nodeid n,info nv)for all nodeid madjacencylist do if(distance(n)+weight(n,m)n1.flag)set flag(n1)=nvi.flag;if(nvi.distance(nvi)file01 Echo“hello hadoop goodbye hadoop”file022、在hdfs中建立一个input目录：hadoop fs mkdir input3、将file01、file02拷贝到input目录：hadoop fs copyFromLocal file0*input4、执行wordcount hadoop jar hadoop-0.20.2-examples.jar wordcount input output5、查看结果 hadoop fs cat output/part-r-00000执行wordcount实例演示运行结果 File01:hello world bye world File02:hello hadoop goodbye hadoop
