MPI, MapReduce 应用比较分析

http://redtreewood.blogspot.com/2009/10/openmp-mpi-mapreduce.html

OpenMP:

OpenMp是线程级别的，共享是存储，只适应用于共享总线与内存，单一操作系统映像的SMP机器和DSM机器。可扩展性比较差，对机器的要求比较高。一般双核的机器（很多CPU共享内存条）适合用OpenMP，可以提高一定的运行速度。这个在科学计算方面应用比较多一些。

MPI:
MPI是进程级的并行粒度，分布式存储，数据分配方式是显示的，具有很好的扩展性。适合于各种机器，但其编程模型比较复杂：
1、需要分析计划分计算任务，并将任务映射到分布式进程集合中去计算。由于MPI是基于消息的，至于是基于任务划分还是数据划分，没有任何限制。具有很强的划分灵活性，这也就引起了复杂性，灵活也意味着复杂呀。简约的灵活才是硬道理。
2、由于是进程级别的，就需要解决通信延迟和负载不平衡问题。要不效率也会大大折扣了。
3、另外就是程序调试起来比较费劲。
4、可靠性比较差。一个进程挂了，整个程序都错了。

OpenMP+MPI的组合也是一个应用研究方向。

MapReduce:
MapReduce是通过把对数据集的大规模操作分散到网络节点上实现可靠性；每个节点会周期性的巴完成的工作和状态的更新报告回来。如果一个节点保持沉默超过一个预设的时间间隔，主节点记录下这个节点状态为死亡状态。然后把分配给这个节点的任务发到别的节点上。
从上可见，Mapreduce是完全基于数据划分的角度来构建并行计算模型的。具有很好的容错能力，也很容易学习。可用于分布排序，web日志分析，构建索引，文档聚类，给予统计的机器学习（Mahout）等等了。

Hadoop是一个基于JAVA实现了MapReduce计算模型的分布式并行编程框架。

转自:http://www.cnblogs.com/LeftNotEasy/archive/2010/11/27/1889598.html

版权说明：

本文由 LeftNotEasy 原创，联系方式[e-mail]

本文可以被任意的转载，请保留完整的文章（含版权说明）。如果商用，请联系原作者。

发布于http://leftnoteasy.cnblogs.com/

前言：

云计算以及很多误解

云计算这个概念被炒作得非常的火热，只要跟互联网沾边的公司，都喜欢用上云计算这个词。云计算其实不是一个那样广义的概念，云计算的定义并不是若干台机器用某种方式管理起来，然后用于存储或者计算这么简单，包括很多的云杀毒、云安全、云存储等等，都不一定是真正的云计算。

上wikipedia可以看看相对来说比较完备的云计算定义，云计算一个很重要的特性是跟虚拟化相关的，像水、电一样为用户提供计算的资源。另外在key features这个章节上说明了很多云计算的特性，如果某一个系统只具备了里面的一个或者很少的几个特性，那称其为云计算就有点那么勉强了。

云计算一些很重要的特性包括

1）可扩展性，用户能够方便的增加、减少计算和存储的能力，而且有着足够的扩展性。按这个定义、一堆GPU或者CPU组成的网格可能就很难称为云计算了，这种超级计算机有着非常好的计算能力，但是对存储的支持相对较差，据内部人士透露，天河的存储能力就相当的差，做做计算还不错，但是数据大了就只有傻眼了）

2）成本相对低廉，云计算对终端用户而言，消费相对较低，对于公司而言，也能减少管理成本。按这个定义，某些很“高级”的服务器组成的集群就很难称为云计算了，之前听说广东公安局的身份证处理电脑的硬盘是单机320T的磁盘阵列，硬盘这种东西就是，买起来很便宜，但是硬盘架非常的贵，想在单机组成一个大的磁盘阵列，那可能就非常的高了。而且云计算的集群管理成本也不高。以一个极端的例子来说，一般一个大一点（100-200台电脑）的网吧都要配2-3个网管。但是我所在的公司几万台服务器，管理服务器的人就在20个人左右，相对管理成本很低。

3）稳定性，至少在程序运行的时候，错误处理能够做好，比如说N个节点计算，某个节点死机了，那程序是不是一定得重新运行？或者集群中某台电脑的硬盘坏掉了，那这些数据会不会就丢失了？按这个定义，普通的多点存储（简单的将数据备份到2块或者多块硬盘中去），以及那些某个节点出错了，计算任务就需要完全重跑的计算方式可能就不算云计算了（比如说MPI，这儿本章后面将会更详细一点提到）

由此看出，云计算是一个很庞大的系统，并非一般的开源项目（大的开源项目还是可以的，比如说Hadoop）可以完成的。就算能完成，也会有这样那样的问题，比如Hadoop集群就没有实现Service的常驻运行（只能跑job，也就是跑完就结束的那种）

分布式的数据挖掘

另一方面，数据挖掘也是一个很有意思、被很多人看重，也在很多领域上发挥大作用的一门学科，从个人而言，我对数据挖掘的兴趣非常的大。传统的计算机想要用数据挖掘，玩玩简单的算法可以，但是在工业界看来，总体来说是一个玩具。比如说weka，学习算法用它还行，但是想要对大规模的数据进行处理，是不太可能的。为了进行大规模的数据处理，分布式计算就很必要了。

分布式计算分类：

一般来说，现在比较常见的并行计算有下面的方式：OpenMP, CUDA，MPI，MapReduce。

OpenMP：

是对于多核的条件下，也就是一些超级计算机可以使用的方式，一个很重要的特性是共享存储，多个instance的关系是线程与线程的关系，也就限制了OpenMP主要是在单机（可能是超级计算机）中进行科学计算的任务。

CUDA:

这个概念是最近几年的事情，似乎ATI最近也搞了一个通用计算的内容，主要是用GPU并联起来进行计算，由于GPU的架构和CPU不太一样，采用这种方式可以对某些计算为主的任务加速几个数量级。对这一块我不太了解，也不太清楚现在CUDA计算、存储能力，还有稳定性等等做到什么样的程度了。这里就不加以评论

Map-Reduce：

发扬光大从Google的论文-MapReduce: Simplified data processing on large clusters开始的。Map-Reduce将程序的运行分成了Map和Reduce两个步骤，Map是一个读取、处理原始数据的过程，而Reduce是根据Map处理的内容，进行整合、再处理。Reduce可以认为又是一个Map，为下一级的Reduce过程作准备，这样数据的处理可以按这种方式进行迭代。

Map-Reduce的重点在下面的几处：

1）运行程序的方式，Map-Reduce一般是在以GFS（Google文件系统），或者HDFS等类似的系统上面进行的，这个系统一般有诸多的如磁盘负载平衡，数据冗余（replica），数据迁移（比如说集群中的某台硬盘坏了，这个硬盘里面的数据会用某种方式备份到其他的硬盘中去，而且保证每块硬盘的数据量都大致平衡）。不过这里先不谈数据的存储，主要谈谈任务的调度。

一般像这样的集群里面都有一百台以上的电脑，按每个电脑8个核计算，至少会有几百上千个CPU的资源。在运行每一个Map-Reduce的时候，用户会先填写需要多少的资源（CPU与内存），然后集群的负责人（可能被称为JobMaster），会去查看当前集群中的计算资源情况，看看能否成功的运行这个作业。如果不行的话，会排队。举一个Map-Reduce的例子：

对于一个很大的文件（由一堆的浮点数组成的），计算这个文件中Top1000的数是什么。那么程序的运行可能是下面的过程。

a. 先在N个CPU（可能在不同的电脑中的）上运行程序，每个CPU会负责数据的一部分，计算出Top1000的数值，将结果写入一个文件（共N份数据）

b. 在M = N/16个CPU上运行程序，每个CPU会负责上面步骤的16个结果文件，计算出这些文件中Top1000的数值，然后将结果写入一个文件（共N / 16份数据）

c. 在O = M/16个CPU上运行程序，同样每个CPU负责上面的16个结果文件。（共N / 256份数据）

..

按照这种方式迭代，直到求出真正的Top1000数值。

所以说，Map-Reduce的数据按每次迭代，是一个减少的过程，如果数据处理的时候有这样的特性，那就非常适合于用Map-Reduce去解决。

2）多个进程间的数据传递，对Map-Reduce而言，没有办法进行传统方式的进程间通信（比如说socket通信），进程间的通信纯粹是用文件去联系的，对于一个Map-Reduce任务，是多级组成的，每一级会起若干的进程，每个进程做的事情就是去读取上一级进程生成的数据，然后处理后写入磁盘让下一级进程进行读取。

这个特性使得Map-Reduce有着良好的容错性，当某一级的某一个进程出错了（比如说机器死机了，程序出异常了等等），JobMaster会重新调度这个进程到另外一个机器上，重新运行，如果是由于外部的问题（比如说机器死机了），一般这样的错误不会使得整个任务重复运行。不过真正如果是写程序出的逻辑问题，那程序也不能正常运行的，JobMaster会试着将失败的进程调度几次，如果都失败了，则任务就失败了。

但是用文件来同步机器间的通讯这个特性也有一个坏处，就是每当Map-Reduce的某一个步骤运行完后，需要重新调度下一级任务。如果是程序是一个重复迭代，直至收敛的过程，比如说KMeans算法、矩阵奇异值分解（SVD），则由于调度产生的开销会非常的大，网络传输不仅仅是发送需要的数据，还有一个读取文件、写入文件的磁盘IO过程，在迭代次数很多的时候（在大规模的SVD分解的时候，迭代的次数可能会达到上万次），这样的方式可能是无法忍受的。

目前Map-Reduce已经被很多的公司实现，Map-Reduce并不是一套标准，而是一种编程的方式，所以每个公司提供的API都有很大的区别，这会使得不能让程序比较通用。一般来说，如果想学Map-Reduce，可以在单机配置一个Hadoop。这算是一个非常标准的Map-Reduce过程。

MPI:

全称是Message Passing Interface，也就是定义了一系列的消息传递接口，可以看看MPI的Wikipedia，里面的内容从了解MPI来说比较好，这里说说重点，就不粘程序了。

MPI其实是一套标准，对C，C++，Fortran，Java，Python等都规定了一系列的接口，MPI的内部有一系列的函数，比如获取当前有多少进程MPI_Comm_size, 进程间同步MPI_Barrier等函数。对每种支持的语言，MPI都定了一个函数接口，也保证了不同的实现下，MPI的程序写出来都是一样的。MPI是一个在学术界和工业界都应用非常广泛的一套接口，目前MPI的实现非常多，开源的有OpenMPI和MPICH比较好，有些MPI实现来自一些大学的实验室，有些MPI的实现来自一流的公司（比如Microsoft就有自己的一套实现，还弄了一个C#版本的）。

MPI相对MapReduce来说，开发、调试也更接近单机，MPI的部署可以在单机上完成，调用的时候也可以制定多线程运行程序，如果有兴趣，可以下载一个OpenMPI或者MPICH，在自己的linux机器上进行部署，写写简单的代码是足够了。在单机保证逻辑正确的情况下，再上集群上面跑，就容易多了。

MPI的优点是，程序的调度是一次性的，就是比如开始申请了50个进程，那这50个进程就会一起跑，同生同死，在程序中指定的同步等操作，也会让这些进程进行同步，也可以在互相之间发送数据，通过MPI的封装，让发数据更操作变得非常的方便（MPI有100多个函数）。也就是从程序开始到结束，每个进程只会调度一次，如果有迭代的操作，就用下面的语句，加上必要的同步就行了：while (condition) { … }。对于需要迭代次数比较多的程序，MPI的运行时间普遍来说会比MapReduce强很多。

MPI相对MapReduce也有很多的缺点，开源的MPI或者一些商业的MPI都没有提供一个GFS系统，这个让大文件的存放，读取都成了一个问题，如果底层有一个GFS，再在上面搭一个MPI的系统，使用起来会非常的舒服。而且MPI的容错性一般不容易做，因为程序是同生同死的，某一个进程挂了，整个任务就挂了，除非在程序运行的时候，经常往磁盘中dump数据，不然容错性是完全没法保证的。

MPI据说还有一个缺点，不过现在也拿不到资料去证实，就是MPI的集群规模一般没法做大，如果做到几千台，进行数据传输、同步的开销就大了，而MapReduce的集群规模做到几万台电脑理论也是没有什么问题的。

分布式计算的学习：

分布式计算的学习主要可以参考一下下面的一些资料，首先是Google的几篇重量级的文章：MapReduce: Simplified data processing on large clusters，也是上文提到过的，还有一篇Google File System。然后就是wikipedia，用map-reduce，clound-computing等关键字搜索一下，可以看到很多有意思的内容。至于国内的教材，我也没有看太多，不太好评价，从我看到的一些来说，感觉讲得还是不太清楚的。

另外如上面提到的，分布式计算的两个最主要的分支：MapReduce和MPI，MapReduce复杂的地方来自底层的文件系统，想搞清楚这个文件系统很痛苦的，而MPI复杂的地方来自众多的函数，到目前为止，我熟练使用的函数就十来个，不过也可以实现很多基本的功能了。

另外学习MapReduce看Hadoop，学习MPI看OpenMPI和MPICH都可以，其他开源的SDK都很难和上面这几个相比。

从国内的公司而言，MPI和MapReduce的应用也很广，比如百度就是同时使用的Hadoop与MPI，学好了这两个东西，找个好工作还是比较容易的：）

OpenMP和MPI是并行编程的两个手段，对比如下：

• OpenMP:线程级（并行粒度）；共享存储；隐式（数据分配方式）；可扩展性差；
• MPI：进程级；分布式存储；显式；可扩展性好。

OpenMP采用共享存储，意味着它只适应于SMP,DSM机器，不适合于集群。MPI虽适合于各种机器，但它的编程模型复杂：

• 需要分析及划分应用程序问题，并将问题映射到分布式进程集合；
• 需要解决通信延迟大和负载不平衡两个主要问题；
• 调试MPI程序麻烦；
• MPI程序可靠性差，一个进程出问题，整个程序将错误；

其中第2个问题感受深刻。每次听我们部门并行组的人做报告，总是听到他们在攻克通信延迟大和负载不平衡的问题。一种并行算法的好坏就看它有没有很好的解决这两个问题。

与OpenMP，MPI相比，MapReduce的优势何在呢？

• 自动并行；
• 容错；
• MapReduce学习门槛低。

附：

• SMP(Symmetric multi-processing)，共享总线与内存，单一操作系统映象。在软件上是可扩展的，而硬件上不能。
• DSM（distributed shared memory），SMP的扩展。物理上分布存储；单一内存地址空间；非一致内存访问；单一操作系统映象。
  OpenMP在科学计算方面居于统治地位，对于多线程方面（包括多核）有很大的优势。
  OpenMP+MPI的组合方式在集群方面有很成熟的案例。
  
  MapReducesh是Google的人研究出来的一个模型，开发的一个针对大规模群组中的海量数据处理的分布式编程模型。

（fromhttp://www.javaeye.com/wiki/topic/86305）