精华内容
下载资源
问答
  • 【zt】三言两语谈并行编程模式

    千次阅读 2007-06-27 15:48:00
    三言两语谈并行编程模式作者: 陈兴 出处: CCW [ 2005-09-08 10:35 ]<!--a.zhy0815button_content { font-size: 12px; font-family: "宋体"; padding: 4px 8px; border-top: 1px solid white;
    三言两语谈并行编程模式
    作者: 陈兴
    出处: CCW
    [ 2005-09-08 10:35 ]
      并行编程模式主要有三种,那么三种模式的优劣又是怎样的呢?请看下文:

      并行编程模式主要有以下三种:

      共享地址空间模式:以OpenMP为代表,主要是利用添加并行化指令到顺序程序中,由编译器完成自动并行化。

      消息传递模式:以MPI为代表,PVM是消息传递模式的一个变种。

      数据并行模式:比较少见,但以其独特的处理方式受到特定用户群的喜欢。

      我可以这样打比方:作并行计算好比是盖楼房,你有了Beowulf和MPI就好比是有了砂石,水泥和钢材,你可以盖最美的房子,但你必须使用最原始状态的原材料,付出可观的智力劳动;你有了OpenMP就好比是有了预制板和各种预制件,可以非常快速地造房子,事半功倍;你有了数据并行环境,可以比作你有了包工头,很多事情您就可以完全依靠他了。也许我的比喻方式不是很恰当,但是三种编程模式的优劣、效率是很有差别的,可以不夸张地说OpenMP比MPI要容易很多倍。

      在现今流行的Beowulf集群上,MPI和PVM是可以实现的,不管使用千兆网,SCI,还是IB;但是,在这种集群上OpenMP是没有办法实现的。要实现OpenMP编程,至少要有4/8路处理器的SMP系统以及相应的编程环境;要实现数据并行编程模式,光有免费的Beowulf+OSCAR环境远远不够

    展开全文
  • 并行编程模式概览前面的5、6篇博文,都是和并行编程相关的基础知识,如果你一路看来,基本上也能够开始进行并行编程设计了,也可以和别人吹吹牛、聊聊天了。但“欲穷千里目,更上一层楼”,前面的毕竟都是基础知识,...

                                              并行编程模式概览

    前面的56篇博文,都是和并行编程相关的基础知识,如果你一路看来,基本上也能够开始进行并行编程设计了,也可以和别人吹吹牛、聊聊天了。

    但“欲穷千里目,更上一层楼”,前面的毕竟都是基础知识,拿来直接设计,虽然能够完成任务,但就像在茫茫大海中航行,没有灯塔,难免会走很多弯路、甚至绝路!

    所以我们要在这些基础知识之上,学习一套系统的分析问题、设计方案、应用实现的理论来指导我们作出正确的、优秀的分析、设计,以及实现。并行编程模式就是这样一座指导我们进行并行编程设计和实现的灯塔。

    当然,这个并行编程模式也是一个完整的体系,不是简单的几个模式堆杂在一起,所以我们要开始就把握住这个并行编程模式的体系的框架,高屋建瓴的从整体上对这套体系有一个清晰的了解,然后再开始深入的掌握每个部分。

     

    首先,我们从整体上看一下并行编程模式的体系结构,如下图:

    从图中可以看出,总共分为4大部分:Finding concurrencyAlgorithm structureSupport StructureImplementation Mechanisms。从英文本意来看比较难以理解,我仔细看了每章的介绍,按照如下方式翻译:并行性分析、算法结构、程序结构、实现结构。这几个部分实际上是按照设计的先后顺序进行分类的:首先要分析问题、然后再选择什么算法,再看程序如何设计,最后看具体实现。下面我们就逐一简单介绍这几部分。

    1.1        并行性分析

    顾名思义,这部分模式是用来分析并行性的,按照英文的字面意思就是“找到并行性”。

    如下图,并行性分析又分为三大类:分解、依赖分析、设计评估,共6个模式。

    1.2        算法结构

    经过并行性分析后,并行相关的任务、数据、依赖都已经基本分析完毕了(之所以说是基本,是因为分析和设计是一个迭代的过程,不是标准的流水线作业),这时就要看看如何将这些任务、数据组织起来来解决实际的问题。也就是说并行性分析是一个“分”的过程,而算法结构是一个“合”的过程

    如下图:算法结构模式部分分为三类:按任务组织、按数据分解组织、按数据流组织,6个模式。

    但细心的朋友可能就会问:在并行性分析之前就是一个已经“合”好的问题了,为什么这里还要再次合起来呢?

    关键就在于:算法结构的“合”是针对已经分解好的任务、数据和依赖,而并行性分析前的“合”只是一个问题的初始混沌状态(有的书中叫做problem mud)。算法结构中的“合”动作是看并行性分析后的结果合起来是否能够解决并行性分析前“合”的问题,其实道理很简单:分解得再好,合起来不能解决分之前的问题,那也是错误的。

     

    1.3        程序结构

    按照英文原意翻译,这部分叫做“支撑结构”,很难理解,我仔细看了这类模式包含的几个子模式,发现其实都是关于进程/线程结构、数据结构的,而这些都是具体程序设计的时候需要考虑的,因此我觉得翻译成“程序结构”更加容易理解。

    从下图可以看出,这类模式分为两类:Program Structure,这是关于如何组织进程或者线程的;Data structure,这是关于如何组织数据的

    上一章的算法结构中也有“按照数据组织”,这一章也有“数据结构”,两者是什么区别或者关系呢?

    区别就在于两个“数据”的地位不一样:算法结构中是按照数据来对任务进行“合”操作,不考虑对数据本身的管理(例如数据操作、数据互斥、数据同步),而程序结构中是考虑数据本身的管理,即如何保证数据满足多个任务的并行运行。

     

    1.4        实现结构

    实现结构作为并行编程模式有点“挂羊头卖狗肉”的意思,因为实际上这里面的内容都是和具体的语言或者平台相关的,作者在这部分主要讲了JavaOpenMPMPI三种语言的实现方法,并不是什么模式(模式应该是语言无关的吧)。

     

    认真的朋友看到“UE Management”、“Synchronization”、“Communications”可能有似曾相识的感觉,因为我在前面56篇博文里面重点就是讲解了WindowsLinux的多进程/多线程实现机制、进程间同步、进程间通信,这不正好对应这里所谓的“UE Management”、“Synchronization”、“Communications”么?:)

     

    展开全文
  • 并行编程的设计模式

    千次阅读 2014-12-04 10:06:20
    这篇文章是对这段时间学习并行编程中的设计模式的一个总结。有不当之处,希望得到大家的批评、指正。 首先,所谓“并行编程中的设计模式”(patterns in parallel programming)仍处于不断的被发现、发掘的阶段。...

    这篇文章是对这段时间学习并行编程中的设计模式的一个总结。有不当之处,希望得到大家的批评、指正。

    首先,所谓“并行编程中的设计模式”(patterns in parallel programming)仍处于不断的被发现、发掘的阶段。当前已经有各路人马对这一领域进行了研究,但远远没有达到统一认识的高度。也没有一套业界普遍 认同的体系或者描述。这就造成了当前这一领域的现状:从事研究的人有不同的背景,他们各自总结出的模式种类不尽相同。即使是同一个模式,不同的团队给它们 取得名字也可能不一样。不过这并不妨碍我们对“并行编程中的设计模式”进行一定的了解,并在实际的软件开发工作中有所借鉴。

    本文分两部分,第一部分会简单介绍这一领域的发展现状:首先是进行研究的主要团体及其代表人物,然后介绍一下他们各自总结的模式体系,最后着重介绍 一下加州大学伯克利分校的体系,A pattern language for parallel programming。第二部分则从该体系中挑出八个常用的设计模式作稍微详细一点的介绍。每个设计模式都附有实际的应用例子来帮助理解。我始终相信, 通过例子的学习是最容易理解的一种方式。

    1. 并行编程模式的发展现状

    在这一领域比较活跃的研究团体包括:

    1. 加州大学伯克利分校。其代表人物是Kurt Keutzer教授,他曾是Synopsys公司的CTO。

    2. Intel公司。代表人物是Tim Mattson,他是Intel的Principle Engineer和并行计算的布道师(evangelist),是“Patterns for Parallel Programming”一书的作者。

    3. 伊利诺伊大学。代表人物是Ralph Johnson教授。他是著名的设计模式“Gang of Four”中的一员。

    4. 其他团体:包括微软、麻省理工大学… 等等。

    他们总结出的并行编程模式体系不尽相同,互相之间又有着紧密的联系。主要有:

    1. 加州大学伯克利分校的 A Pattern Language for Parallel Programming ver2.0

    2. 伊利诺伊大学的 Parallel Programming Patterns

    3. Tim Mattson 的著作 Patterns for Parallel Programming

    这其中,我最为喜欢加州大学伯克利分校的体系:

    伯克利的研究人员认为,写出高质量并行软件的关键在于拥有好的软件设计:从软件的总体架构,一直到系统的底层实现。将这些“好的设计”以一种系统的 方式描述出来,并在各个不同的软件项目当中重用是解决构建高质量并行软件问题的关键。这远比各种具体的编程模型以及其支撑环境来得重要。因为拥有了一个好 的设计之后,我们可以很容易的在各种开发平台上编写源代码。

    伯克利的模式体系包含了几个不同的层次,上自软件架构,下至程序指令执行的策略。最上面的两块分别是“架构模式”(Structural patterns) 和“计算模式”(Computational patterns)。这两块并不单单包括并行软件,也包括传统的串行软件模式。用我们常用来表达系统架构的线框图打比方,“架构模式”指的就是那些箭头和 框框,它们表示的是程序总体的组织结构,以及各部分之间是怎么交互的。“计算模式”指的是框框里面的计算类型。例如,是基于图的算法,还是有限状态机,还 是线性代数运算,等等。程序设计师通常需要在这两大类模式之间翻来覆去的进行选择。例如,我们可能先选择了一种架构模式,然后考虑使用某些合适的计算模 式。但是选择的计算模式可能更适合于在另一种架构模式下运行,所以我们又得重新选择一种架构模式… …如此反复。上面这张图在“架构模式”和“计算模式”这两大块之间画了两个反复的箭头,表达的就是这个意思。

    这张图下方的三大块就专指并行编程当中的模式了。它们包括“算法模式”(Algorithm strategy patterns),“实现模式”(Implementation strategy patterns)和“并行执行模式”(Parallel execution patterns)。顾名思义,“算法模式”指的是程序算法层面的模式。它们表达的是,为了解决某一类实际问题,怎么样在较高的算法层面实现并行。“实现 模式”指的是我们在编写源代码的时候,利用什么样的一些程序控制结构和数据结构来实现并行。例如“parallel_for”,例如并行容器,等等。最后 一个“并行执行模式”指的是为了在计算机中有效的执行一个并行程序,我们应该采取哪些方法。这包括指令的执行模式,例如是MIMD还是SIMD,也包括一 些任务调度的策略。这三类模式是紧密联系在一起的。例如,为了解决一个问题,我们可能使用“recursive splitting”的算法模式。而为了实现这个算法,我们很有可能使用“fork-join”的实现模式。在执行层面,并行程序库则通常会用 “thread pool”的并行执行模式来支持“fork-join”的运行。

    由于我们在编写程序时,“并行执行模式”往往由编译器或并行程序库例如TBB的编写人员考虑,我们并不需要关心;“实现模式”和我们选择的具体并行 运算平台有关(OpenMP, TBB,MPI,…,,等等),不同的平台有不同的API;“计算模式”则和具体的问题域联接紧密。而且,看上去伯克利所总结的“计算模式”大部分和高性 能计算有关,普通的应用程序员并不熟悉。所以在本文,我将只挑选和并行计算密切相关的两个“架构模式”和六个常见的“算法模式”举例进行说明。

    2. 八个常用的并行编程模式

    2.1 Agent and Repository

    这是一个“架构模式”,它针对这样一类问题:我们有一组数据,它们会随机的被一些不同的对象进行修改。解决这一类问题的方案是,创建一个集中管理的 数据仓库(data repository),然后定义一组自治的agent来操作这些数据,可能还有一个manager来对agent的操作进行协调,并保证数据仓库中数据 的一致性。我们常见的源代码版本控制软件例如Perforce就是实现这种架构的典型代表:源代码都存放在一个统一的服务器中(或是一组服务器中,但对 client而言是透明的),不同的程序员们使用各自的客户端对源代码文件进行读,写,加,删的操作。由Perforce负责保证源代码数据的一致性。

    2.2 Map Reduce

    Map Reduce这个名词原来是函数式编程里面的一个概念,但是自从Google于2004年推出同名的并行计算程序库后,提到这个名词大家大多想到的是 Google的这个Framework。在这里,Map Reduce是一个“架构模式”的名称。当然,我们这里的Map Reduce指的就是类似Google Map Reduce工作原理的一类模式。

    那么什么是Map Reduce的模式呢?用较为简单的语言描述,它指的是这样一类问题的解决方案:我们可以分两步来解决这类问题。第一步,使用一个串行的Mapper函数 分别处理一组不同的数据,生成一个中间结果。第二步,将第一步的处理结果用一个Reducer函数进行处理(例如,归并操作),生成最后的结果。从使用 Google的Map Reduce程序库的角度而言,作为应用程序员,我们只需提供一组输入数据,和两个普通的串行函数(Mapper和Reducer),Google的 Map Reduce框架就会接管一切,保证输入数据有效的在一个分布式的计算机集群里面分配,然后Mapper和Reducer函数在其上有效的运行、处理,并 最后汇总生成我们想要的处理结果。所有一切的细节,例如并行化、数据的分配、不同机器之间的计算误差,通通被隐藏在程序库内。

    那么Map Reduce到底是什么样的一个过程呢?

    我们讲过,使用Map Reduce,程序员必须提供一组输入数据,以及一个Mapper和一个Reducer函数。在这里,输入数据必须是一个按(input_key,input_value)方式组织的列表。

    mapper函数的任务是处理输入列表中的某一个单元数据:mapper(input_key,input_value),并产生如下输出结果:

    接下来,把对所有单元数据的处理结果按照intermediate_key归类:同样的intermediate_key放在一起,它们的intermediate_value简单的串接起来,得到:

    Reducer函数的任务是对上述的中间结果进行处理:reducer(intermediate_key, intermediate_value_list),并产生如下最终输出结果:

    我们会举两个例子说明这一过程。第一个例子是一个简单的统计单词出现次数的小程序。第二个例子是Google曾经怎样使用Map Reduce FrameWork来计算Page Rank。

    第一个例子,假设我们要写一个小程序,来统计在几篇不同文章里所有出现过的单词各自总共出现的次数。我们应该怎么做呢?下面描述的利用Map Reduce的方法肯定不是大多数程序员第一感会想到的方法。但这种方法非常好的揭示了Map Reduce的基本思想。并且,这种方法很容易被扩展到处理上千万甚至是上亿的文件数据,并且能够在一个分布的计算机集群里面运行。这可不是传统的方法能 够轻易做到的。

    具体而言,假设我们有如下三个文本文件,a.txt, b.txt和c.txt:

    对于输入数据而言,input_key就是文件名,input_value就是一个大的string,包含的是文件内容。所以我们的输入数据看上去会是这样的:

    我们会写一个简单的串行的mapper(fileName, fileContent)函数。这个函数做的事情很简单,读入一个文本文件,把每一个遇到的单词当作一个新的intermediate_key,并赋其 intermediate_value为1。将mapper函数处理文件a,我们会得到如下结果:

    将所有三个文件的处理结果放在一起,我们得到:

    然后将中间结果按intermediate_key归类:

    最后,由reducer(intermediate_key, intermediate_value_list)对中间结果进行处理。它做的事也很简单,仅仅是把某intermediate_key对应的所有 intermediate_value相加。我们于是得到最终结果:

    第二个例子,怎样使用Map Reduce计算PageRank。什么是PageRank?可能大家都有所了解,这是Google用来量度一个网页的重要性的值。简单而言,有越多的其 它网页链接到这个网页,这个网页的PageRank越高。链接到这个网页的网页PageRank越高,这个网页的PageRank也越高。假设我们一共有 n个网页0, 1, …, n-1。对第j个网页我们给它赋一个PageRank值qj。所有的qj组合起来成为一个向量q = (q0,q1, …qn-1)。这个向量满足概率分布。即qj的值都在0和1之间,并且所有的qj加起来等于1。qj越大,网页的重要性越高。那么q是怎么计算出来的呢?答案是使用迭代的方法:

    我们从一个初始的PageRank向量分布P开始,乘以一个n*n的矩阵M,得到一个新的PageRank向量。把新的PageRank向量继续乘 以M得到下一步的PageRank… … 如此迭代有限步后,PageRank向量的值会趋于收敛,于是我们得到最终的PageRank。

    这里需要回答两个问题:1. 如何确定初始的PageRank,即迭代的起点?答案是任意选择一个概率分布就可以,无论你选择什么初始值,都不影响其收敛到最终的结果。我们通常使用均匀概率分布,即clip_image037。2. 如何定义M?这个问题稍显复杂,有兴趣的读者可以参见Michael Nielsen 的博文Using MapReduce to compute PageRank.了解更详细的内容。在这里,我们将其简化的定义为一个描述网页间互相链接结构的超大矩阵。假设网络里有n个网页,那么我们这个矩阵就是一个n*n的方阵。矩 阵的每一列代表一个网页对外的超链接情况。例如,我们定义#(j)为第j个网页对外的所有超链接的数量。那么对于矩阵M的第j列而言,如果网页j对网页k 没有超链接,那么第k行元素Mkj=0,否则Mkj=1/#(j)。这里隐含的意思是当一个读者在浏览网页j时,有1/#(j)的可能性跳转到网页k。

    那么如何使用Map Reduce来计算PageRank呢?虽然整个迭代的过程必须是串行的,迭代的每一步我们还是可以用Map Reduce来并行的计算的。这里也必须并行的计算因为这个矩阵和向量的规模是超大的(想象一下整个互联网的网页数量)。使用Map Reduce来计算迭代的一步实际上是用Map Reduce来计算矩阵和向量的乘法。假设我们要计算如下一个方阵和向量的乘法。其实质是将第i个向量元素的值pi乘以矩阵第i列的每一元素,然后放在矩阵元素原来的位置。最后,把矩阵第i行的所有元素相加,得到结果向量的第i个元素的值。

    类似的,我们可以得到用MapReduce计算PageRank的方法:

    第一步,输入的(input_key, input_value)。input_key是某个网页的编号,如j。input_value是一个列表,元素值是M矩阵的第j列元素,最后再加上一个pj,就是当前网页j的PageRank值。

    第二步,Map。Mapper(input_key, input_value)所做的事情很简单,就是把pj乘以列表元素的每一个值,然后输出一组(intermediate_key, intermediate_value)。intermediate_key就是矩阵的行号,k。intermediate_value就是pj列表元素的值,即pj乘以矩阵第k行第j列的元素的值。

    第三步,汇总。把所有intermediate_key相同的中间结果放到一起。即是把第k行所有的intermediate_value放在一个列表intermediate_value_list内。

    第四步,Reduce。Reducer(intermediate_key, intermediate_value_list)做的事也很简单,就是把intermediate_value_list内所有的值相加。最后形成的 (output_key, output_value)就是结果向量第k行的元素值。

    以上就是利用Map Reduce计算PageRank的简略过程。这个过程相当粗略和不精确,只是为了揭示Map Reduce的工作过程和Google曾经用来计算PageRank的大致方法。认真的读者应该查阅其它更严谨的著作。

    最后,和上述计算矩阵和向量乘法的例子相似,Map Reduce也可以用来计算两个向量的点乘。具体怎么做留给读者自己去思考,一个提示是我们所有的intermediate_key都是相同的,可以取同一个值例如1。

    2.3 Data Parallelism

    这是一个“算法模式”。事实上,把Data Parallelism和下节将要提到的Task Parallelism都称之为一种“算法模式”我觉得有过于笼统之嫌。到最后,哪一种并行算法不是被分解为并行执行的task呢(task parallelism)? 而并行执行的task不都是处理着各自的那份数据吗(data parallelism)?所以如果硬要把Data Parallelism和Task Parallelism称为两种算法模式,我只能说它们的地位要高于其它的算法模式。它们是其它算法模式的基础。只不过对于有些问题而言,比较明显的我们 可以把它看成是Data Parallelism的或是Task Parallelism的。也许Data Parallelism模式和Task Parallelism模式特指的就是这类比较明显的问题。

    那么什么是Data Parallelism? 顾名思义,就是这类问题可以表达为同样的一组操作被施加在不同的相互独立的数据上。

    一个比较典型的例子就是计算机图形学里面的Ray tracing算法。Ray tracing算法可以大致描述为从一个虚拟相机的光心射出一条射线,透过屏幕的某个像素点,投射在要渲染的几何模型上。找到射线和物体的交点后,再根据 该点的材料属性、光照条件等,算出该像素点的颜色值,赋给屏幕上的像素点。由于物体的几何模型很多个小的三角面片表示,算法的第一步就是要求出射线与哪个 三角面片有交点。射线与各个单独的三角面片求交显然是相互独立的,所以这可以看做是Data Parallelism的例子。

    2.4 Task Parallelism

    Task Parallelism的算法模式可以表述为,一组互相独立的Task各自处理自己的数据。和Data Parallelism不同,这里关注的重点不是数据的划分,而是Task的划分。

    如前所述,Task Parallelism和Data Parallelism是密不可分的。互相独立的Task肯定也是运行在互相独立的数据上。这主要是看我们以什么样的视角去看问题。例如,上一节 RayTracing的例子中,我们也可以把射线和一个独立的三角面片求交看作是一个独立的Task。这样就也可以当它做是Task Parallelism的例子。然而,咬文嚼字的去区分到底是Task Parallelism还是Data Parallelism不是我们的目的,我们关注的应该是问题本身。对于某一个具体问题,从Data Parallelism出发考虑方便还是从Task Parallelism出发考虑方便,完全取决于问题本身的应用场景以及设计人员自身的经验、背景。事实上,很多时候,不管你是从Task Parallelism出发还是从Data Parallelism出发,经过不断的优化,最终的解决方案可能是趋同的。

    下面一个矩阵乘法的例子很好的说明了这个问题。我们都知道矩阵乘法的定义:假如有n行k列的矩阵A乘以k行m列的矩阵B,那么我们可以得到一个n行m列的的矩阵C。矩阵C的第n行第m列的元素的值等于矩阵A的第n行和矩阵B的第m列的点乘。

    从Task Parallelism的角度出发,我们可能把计算C的每一个元素当做一个独立的Task。接下来,为了提高CPU的缓存利用率,我们可能把邻近几个单元 格的计算合并成一个大一点的Task。从Data Parallelism的角度出发,我们可能一开始把C按行分成不同的块。为了探索到底怎样的划分更加有效率,我们可能调整划分的方式和大小,最后,可能 发现,最有效率的做法是把A,B,C都分成几个不同的小块,进行分块矩阵的乘法。可以看到,这个结果实际上和从Task Parallelism出发考虑的方案是殊途同归的。

    2.5 Recursive Splitting

    Recursive Splitting指的是这样一种算法模式:为了解决一个大问题,把它分解为可以独立求解的小问题。分解出来的小问题,可能又可以进一步分解为更小的问 题。把问题分解到足够小的规模后,就可以直接求解了。最后,把各个小问题的解合并为原始的大问题的解。这实际上是我们传统的串行算法领域里面也有的 “divide and conquer”的思想。

    举两个例子。第一个是传统的归并排序。例如,要排序下面的8个元素的数组,我们不管三七二十一先把它一分为二。排序4个元素的数组还是显得太复杂 了,于是又一分为二。现在,排序2个元素的数组很简单,按照大小交换顺序就行。最后,把排好序的数组按序依次组合起来,就得到我们最终的输出结果。

    第二个例子稍微有趣一点,是一个如何用程序解“数独”游戏的例子。“数独”就是在一个9*9的大九宫格内有9个3*3的小九宫格。里面有些格子已经填入了数字,玩家必须在剩下的空格里也填入1到9的数字,使每个数字在每行、每列以及每个小九宫格内只出现一次。

    这里作为举例说明,我们考虑一个简单一点的情况:在一个4*4的格子里填入1~4的数字,使其在每行、每列以及每个2*2的格子里只出现一次。

    解“数独”游戏的算法可以有很多种。如果是人来解,大概会按照上图的次序依次填入1,2,3到相应的格子当中。每填入一个新数字,都会重新按规则评 估周围的空格,看能否按现有情况再填入一些数字。这个方法当然没错,不过看上去不太容易并行化。下面介绍一个按照“recursive splitting”的方法可以很容易做到并行化的解法。

    1) 首先,将二维的数独格子展开成一个一维的数组。已经有数字的地方是原来的数字,空格子的地方填上“0”。

    2) 接下来,从前到后对数组进行扫描。第一格是“3”,已经有数字了,跳过。移动搜索指针到下一格。

    3) 第二格是“0”,意味着我们需要填入一个新的数字。这个新的数字有4种可能性:1, 2, 3, 4。所以创建4个新的搜索分支:

    4) 接下来根据现有的数字信息检查各个搜索分支。明显,第三和第四个搜索分支是非法的。因为我们在同一行中已经有了数字“3”和“4”。所以忽略这两个分支。第一和第二条分支用现有的数字检查不出冲突,所以继续从这两个分支各派生出4条新的分支进行搜索… …

    这个思路像极了我们之前的归并排序的例子,都是在算法运行的过程中不断产生出新的任务。所以实际上这也是一个“Task Parallelism”的例子。

    2.6 Pipeline

    “Pipeline”也是一种比较常见的算法模式。通常,我们都会用汽车装配中的流水线、CPU中指令执行的流水线来类比的说明这一模式。它说的是 我们会对一批数据进行有序、分阶段的处理,前一阶段处理的输出作为下一阶段处理的输入。每一个阶段永远只重复自己这一阶段的任务,不停的接受新的数据进行 处理。用一个软件上的例子打比方,我们要打开一批文本文件,将里面每一个单词的字母全部改成大写,然后写到一批新的文件里面去,就可以创建一条有3个 stage的流水线:读文件,改大写,写文件。

    “Pipeline”模式的概念看上去很容易理解,可是也不是每一个人都能一下子理解的那么透彻的。例如有这样一个问题:我们有一个for循环,循 环体是一条有3个stage的pipeline,每个stage的运行时间分别是10, 40, 和10个CPU的时钟间隔。请问这个for循环执行N次大概需要多长时间(N是一个很大的数)?

    A. 60*N

    B. 10*N

    C. 60

    D. 40*N

    请仔细思考并选择一个答案。:-)

    答案是40*N。流水线总的执行时间是由它最慢的一个stage决定的。原因请见下图。

    2.7 Geometric decomposition

    接下来这两个算法模式看上去都显得比较特殊化,只针对某些特定的应用类型。“Geometric decomposition”说的是对于一些线性的数据结构(例如数组),我们可以把数据切分成几个连续的子集。因为这种切分模式看上去和把一块几何区域 切分成连续的几块很类似,我们就把它叫做”Geometric decomposition”。

    最常用的例子是分块矩阵的乘法。例如,为了计算两个矩阵A,B的乘法。我们可以把他们切分成各自可以相乘的小块。

    结果矩阵当然也是分块的:

    结果矩阵每一分块的计算按照如下公式进行:

    例如:

    最终的结果就是:

    下面这幅图显示了两个4*4的分块矩阵A,B进行乘法时,计算结果矩阵C的某一分块时,需要依次访问的A,B矩阵的分块。黑色矩阵分块代表要计算的C的分块,行方向上的灰色矩阵代表要访问的矩阵A的分块,列方向上的灰色分块代表要访问的矩阵B的分块。

    2.8 Non-work-efficient Parallelism

    这个模式的名字取得很怪异,也有其他人把它叫做“Recursive Data”。不过相比而言,还是这个名字更为贴切。它指的是这一类模式:有些问题的处理使用传统的方法,必须依赖于对数据进行有序的访问,例如深度优先搜 索,这样就很难并行化。但是假如我们愿意花费一些额外的计算量,我们就能够采用并行的方法来解决这个问题。

    常用的一个例子是如下的“寻找根节点”的问题。假设我们有一个森林,里面每一个节点都只记录了自己的前向节点,根节点的前向节点就是它自己。我们要 给每一个节点找到它的根节点。用传统的方法,我们只能从当前节点出发,依次查找它的前向节点,直到前向节点是它自身。这种算法对每一个节点的时间复杂度是 O(N)。总的时间复杂度是N*O(N)。

    如果我们能换一种思路来解这个问题就可以将其并行化了。我们可以给每一个节点定义一个successor(后继结点),successor的初始值 都是其前向节点。然后我们可以同步的更新每一个节点的successor,令其等于“successor的successor”,直到successor 的值不再变化为止。这样对于上图的例子,最快两次更新,我们就可以找到每个节点的根节点了。这种方法能同时找到所有节点的根节点,总的时间复杂度是 N*log (N)。

    3. 后记

    如前所述,“并行编程中的设计模式”是一个仍在不断变化、发展的领域。这篇博文简要介绍了这一领域当前的发展现状,并选取八个常用的模式进行了介绍。我涉足并行编程领域不久,很多理解也并不深入。所以文章的缺点错误在所难免,真诚希望能得到大家的批评指正。

    4. 参考文献

    本文的写作参考了如下资源,可以作为进一步阅读的材料:

    · UC Berkeley, A Pattern Language for Parallel Programming

    · Eun-Gyu Kim, Parallel Programming Patterns

    · Jim Browne, Design Patterns for Parallel Computation

    · Tim Mattson, Patterns for Parallel Programming

    · Michael Nielsen, Using Map Reduce to compute PageRank

    · Aater Suleman, Parallel Programming: Do you know Pipeline Parallelism?

    展开全文
  • 并行编程入门

    千次阅读 2016-10-14 20:10:38
    1. 并行编程简介 2. MapReduce 2.1 MapReduce简介 2.2 MapReduce框架 2.3 Hadoop介绍 2.4 Hadoop基本类 2.5 Hadoop编程实例1.并行编程简介1.1.并行编程作用,用途商业用途,科学计算,大数据分析1.2....

    目录

    1. 并行编程简介
    2. MapReduce
      2.1 MapReduce简介
      2.2 MapReduce框架
      2.3 Hadoop介绍
      2.4 Hadoop基本类
      2.5 Hadoop编程实例

    #1.并行编程简介
    ##1.1.并行编程作用,用途
    商业用途,科学计算,大数据分析

    ##1.2.并行编程兴起原因
    目前的串行编程的局限性
    使用的流水线等隐式并行模式的局限性
    硬件的发展
    ##1.3.并行算法设计原则步骤
    a.分析问题
    b.分解问题
            其中分解方法有:
            数据分解
            递归分解
            探测性分解
            推测性分解
            混合分解
    c.根据分解方法,产生任务
    d.将任务映射到处理器上
    e.要注意的问题:
            减少任务之间的交互(任务粒度,任务的依赖)
            负载均衡(静态均衡和动态均衡)

    ###1.4并行算法模型
            数据并行模型
            任务图模型
            工作池模型(任一个任务可映射到任一个处理器上)
            主-从模型
    ###

    ##1.5.基本通信操作(单端口,双向)
    对于不同的操作,对于不同的设备模型,有如下几种组合:
    a.一对多广播及多对一归约(一传到二,然后二传到4)
    环或线性阵列:
    格网:
    超立方体:
    b.多对多广播 及 多对多归约
    环或线性阵列:
    格网:
    超立方体:
    d.全归约 及 前缀和
    环或线性阵列:
    格网:
    超立方体:
    e.散发及 收集归约
    环或线性阵列:
    格网:
    超立方体:
    f.循环移位
    环或线性阵列:
    格网:
    超立方体:

    ##1.6.解析建模
    模型需要考虑的因素有:

    • 开销分析
    • 性能度量
              执行时间,加速比,总并行开销,效率,成本
    • 粒度影响
    • 系统可扩展性
      ###1.7使用消息传递模式编程
      使用MPI API 进行编程
    MPI,消息传递接口
    int MPI_Init(int *argc,char ***grgv)
    
    int MPI_Finalize()
    
    int MPI_Comm_size(MPI_Comm comm,int * size):用size返回comm域中进程数目
    
    int MPI_Comm_rank(MPI_Comm comm,int * rank):用rank返回comm域中进程等级(0-size-1)
    
    int MPI_Send(void buf,int count,MPI_Datatype datatype,int dest,int tag,MPI_comm comm);
    
    int MPI_Recv(void buf,int count,MPI_Datatype datatype,int source,int tag,MPI_comm comm,MPI_status status);
    
    int MPI_Get_count(MPI_Status *status, MPI_Datatype datatype, int *count) 
    

    ###

    #2.MapReduce
    参考文献:
    http://www.open-open.com/lib/view/open1328763069203.html
    http://www.wnt.com.cn/html/news/tophome/top_xytd/top_xytd_jswz/bbs_service/20130711/111140562.html
    http://blog.csdn.net/geekcome/article/details/9024419
    http://www.cnblogs.com/biyeymyhjob/archive/2012/08/12/2633608.html
    http://www.educity.cn/wenda/578905.html
    http://www.ibm.com/developerworks/cn/opensource/os-cn-hadoop1/#ibm-pcon
    http://wiki.apache.org/hadoop/
    http://hadoop.apache.org/
    http://research.google.com/archive/mapreduce-osdi04.pdf

    IBM Hadoop分布式并行编程系列:
    第一部分:http://www.ibm.com/developerworks/cn/opensource/os-cn-hadoop1/
    第二部分:http://www.ibm.com/developerworks/cn/opensource/os-cn-hadoop2/
    第三部分:http://www.ibm.com/developerworks/cn/opensource/os-cn-hadoop3/
    http://www.educity.cn/wenda/578905.html
    http://datalife.iteye.com/blog/930318

    ##2.1MapReduce简介
            MapReduce 是 Google 公司的核心计算模型,它将复杂的运行于大规模集群上的并行计算过程高度的抽象到了两个函数,Map 和 Reduce, 这是一个令人惊讶的简单却又威力巨大的模型。适合用 MapReduce 来处理的数据集(或任务)有一个基本要求: 待处理的数据集可以分解成许多小的数据集,而且每一个小数据集都可以完全并行地进行处理
    这里写图片描述

            计算模型的核心是 Map 和 Reduce 两个函数,这两个函数由用户负责实现,功能是按一定的映射规则将输入的 <key, value> 对转换成另一个或一批 <key, value> 对输出。
    这里写图片描述
            以一个计算文本文件中每个单词出现的次数的程序为例,<k1,v1> 可以是 <行在文件中的偏移位置, 文件中的一行>,经 Map 函数映射之后,形成一批中间结果 <单词,出现次数>, 而 Reduce 函数则可以对中间结果进行处理,将相同单词的出现次数进行累加,得到每个单词的总的出现次数。
    基于 MapReduce 计算模型编写分布式并行程序非常简单,程序员的主要编码工作就是实现 Map 和 Reduce 函数,其它的并行编程中的种种复杂问题,如分布式存储,工作调度,负载平衡,容错处理,网络通信等,均由 MapReduce 框架(比如 Hadoop )负责处理,程序员完全不用操心。

    ##2.2 MapReduce框架
    ### 2.2.1运行架构图
    如下:这里写图片描述

    ### 2.2.流程分析
    1.在客户端启动一个作业。
    2.向JobTracker请求一个Job ID。
    3.将运行作业所需要的资源文件复制到HDFS上,包括MapReduce程序打包的JAR文件、配置文件和客户端计算所得的输入划分信息(输入划分信息?)。这些文件都存放在JobTracker专门为该作业创建的文件夹中。文件夹名为该作业的Job ID。JAR文件默认会有10个副本(mapred.submit.replication属性控制);输入划分信息告诉了JobTracker应该为这个作业启动多少个map任务等信息。
    4.JobTracker接收到作业后,将其放在一个作业队列里,等待作业调度器对其进行调度(这里是不是很像微机中的进程调度呢,呵呵),当作业调度器根据自己的调度算法调度到该作业时,**会根据输入划分信息为每个划分创建一个map任务,并将map任务分配给TaskTracker执行。对于map和reduce任务,TaskTracker根据主机核的数量和内存的大小有固定数量的map槽和reduce槽。**这里需要强调的是:map任务不是随随便便地分配给某个TaskTracker的,这里有个概念叫:数据本地化(Data-Local)。意思是:将map任务分配给含有该map处理的数据块的TaskTracker上,同时将程序JAR包复制到该TaskTracker上来运行,这叫“运算移动,数据不移动”。而分配reduce任务时并不考虑数据本地化。
    5.TaskTracker每隔一段时间会给JobTracker发送一个心跳,告诉JobTracker它依然在运行,同时心跳中还携带着很多的信息,比如当前map任务完成的进度等信息。当JobTracker收到作业的最后一个任务完成信息时,便把该作业设置成“成功”。当JobClient查询状态时,它将得知任务已完成,便显示一条消息给用户。
    以上是在客户端、JobTracker、TaskTracker的层次来分析MapReduce的工作原理的,下面我们再细致一点,从map任务和reduce任务的层次来分析分析吧。
    ### 2.2.2.Map、Reduce任务中Shuffle和排序的过程
    流程分析:
    这里写图片描述

    Map端:
            1.每个输入分片会让一个map任务来处理,默认情况下,以HDFS的一个块的大小(默认为64M)为一个分片,当然我们也可以设置块的大小。map输出的结果会暂且放在一个环形内存缓冲区中(该缓冲区的大小默认为100M,由io.sort.mb属性控制),当该缓冲区快要溢出时(默认为缓冲区大小的80%,由io.sort.spill.percent属性控制),会在本地文件系统中创建一个溢出文件,将该缓冲区中的数据写入这个文件。

            2.在写入磁盘之前,线程首先根据reduce任务的数目将数据划分为相同数目的分区,也就是一个reduce任务对应一个分区的数据。这样做是为了避免有些reduce任务分配到大量数据,而有些reduce任务却分到很少数据,甚至没有分到数据的尴尬局面。其实分区就是对数据进行hash的过程。然后对每个分区中的数据进行排序,如果此时设置了Combiner,将排序后的结果进行Combia操作,这样做的目的是让尽可能少的数据写入到磁盘。

            3.当map任务输出最后一个记录时,可能会有很多的溢出文件,这时需要将这些文件合并。合并的过程中会不断地进行排序和combia操作,目的有两个:1.尽量减少每次写入磁盘的数据量;2.尽量减少下一复制阶段网络传输的数据量。最后合并成了一个已分区且已排序的文件。为了减少网络传输的数据量,这里可以将数据压缩,只要将mapred.compress.map.out设置为true就可以了。

            4.将分区中的数据拷贝给相对应的reduce任务。有人可能会问:分区中的数据怎么知道它对应的reduce是哪个呢?其实map任务一直和其父TaskTracker保持联系,而TaskTracker又一直和JobTracker保持心跳。所以JobTracker中保存了整个集群中的宏观信息。只要reduce任务向JobTracker获取对应的map输出位置就ok了哦。

    到这里,map端就分析完了。那到底什么是Shuffle呢?Shuffle的中文意思是“洗牌”,如果我们这样看:一个map产生的数据,结果通过hash过程分区却分配给了不同的reduce任务,是不是一个对数据洗牌的过程呢?呵呵。

    Reduce端:
            1.Reduce会接收到不同map任务传来的数据,并且每个map传来的数据都是有序的。如果reduce端接受的数据量相当小,则直接存储在内存中(缓冲区大小由mapred.job.shuffle.input.buffer.percent属性控制,表示用作此用途的堆空间的百分比),如果数据量超过了该缓冲区大小的一定比例(由mapred.job.shuffle.merge.percent决定),则对数据合并后溢写到磁盘中。
            2.随着溢写文件的增多,后台线程会将它们合并成一个更大的有序的文件,这样做是为了给后面的合并节省时间。其实不管在map端还是reduce端,MapReduce都是反复地执行排序,合并操作,现在终于明白了有些人为什么会说:排序是hadoop的灵魂。
            3.合并的过程中会产生许多的中间文件(写入磁盘了),但MapReduce会让写入磁盘的数据尽可能地少,并且最后一次合并的结果并没有写入磁盘,而是直接输入到reduce函数

    ##2.3 Hadoop简介
    ###2.3.1 Hadoop是什么
    MapReduce的一个开源实现
    ### 2.3.2数据分布存储
            Hadoop 中的分布式文件系统 HDFS 由一个管理结点 ( NameNode )和N个数据结点 ( DataNode )组成,每个结点均是一台普通的计算机。在使用上同我们熟悉的单机上的文件系统非常类似,一样可以建目录,创建,复制,删除文件,查看文件内容等。但其底层实现上是把文件切割成 Block,然后这些 Block 分散地存储于不同的 DataNode 上,每个 Block 还可以复制数份存储于不同的 DataNode 上,达到容错容灾之目的。NameNode 则是整个 HDFS 的核心,它通过维护一些数据结构,记录了每一个文件被切割成了多少个 Block,这些 Block 可以从哪些 DataNode 中获得,各个 DataNode 的状态等重要信息。
    ###2.3.3 分布式并行计算
            Hadoop 中有一个作为主控的 JobTracker,用于调度和管理其它的 TaskTracker, JobTracker 可以运行于集群中任一台计算机上。TaskTracker 负责执行任务,必须运行于 DataNode 上,即 DataNode 既是数据存储结点,也是计算结点。 JobTracker 将 Map 任务和 Reduce 任务分发给空闲的 TaskTracker, 让这些任务并行运行,并负责监控任务的运行情况。如果某一个 TaskTracker 出故障了,JobTracker 会将其负责的任务转交给另一个空闲的 TaskTracker 重新运行。
    ###2.3.4 本地计算
            数据存储在哪一台计算机上,就由这台计算机进行这部分数据的计算,这样可以减少数据在网络上的传输,降低对网络带宽的需求。在 Hadoop 这样的基于集群的分布式并行系统中,计算结点可以很方便地扩充,而因它所能够提供的计算能力近乎是无限的,但是由是数据需要在不同的计算机之间流动,故网络带宽变成了瓶颈,是非常宝贵的,“本地计算”是最有效的一种节约网络带宽的手段,业界把这形容为“移动计算比移动数据更经济”。

    这里写图片描述

    ###2.3.5 任务粒度

             把原始大数据集切割成小数据集时,通常让小数据集小于或等于 HDFS 中一个 Block 的大小(缺省是 64M),这样能够保证一个小数据集位于一台计算机上,便于本地计算。有 M 个小数据集待处理,就启动 M 个 Map 任务,注意这 M 个 Map 任务分布于 N 台计算机上并行运行,Reduce 任务的数量 R 则可由用户指定。
    ###2.3.6 Partition
            把 Map 任务输出的中间结果按 key 的范围划分成 R 份( R 是预先定义的 Reduce 任务的个数),划分时通常使用 hash 函数如: hash(key) mod R,这样可以保证某一段范围内的 key,一定是由一个 Reduce 任务来处理,可以简化 Reduce 的过程。
    ###2.3.7 Combine
            在 partition 之前,还可以对中间结果先做 combine,即将中间结果中有相同 key的 <key, value> 对合并成一对。combine 的过程与 Reduce 的过程类似,很多情况下就可以直接使用 Reduce 函数,但 combine 是作为 Map 任务的一部分,在执行完 Map 函数后紧接着执行的。Combine 能够减少中间结果中 <key, value> 对的数目,从而减少网络流量。

    ###2.3.8 Reduce 任务从 Map 任务结点取中间结果
            Map 任务的中间结果在做完 Combine 和 Partition 之后,以文件形式存于本地磁盘。中间结果文件的位置会通知主控 JobTracker, JobTracker 再通知 Reduce 任务到哪一个 DataNode 上去取中间结果。注意所有的 Map 任务产生中间结果均按其 Key 用同一个 Hash 函数划分成了 R 份,R 个 Reduce 任务各自负责一段 Key 区间。每个 Reduce 需要向许多个 Map 任务结点取得落在其负责的 Key 区间内的中间结果,然后执行 Reduce 函数,形成一个最终的结果文件。
    ###2.3.9 任务管道
            有 R 个 Reduce 任务,就会有 R 个最终结果,很多情况下这 R 个最终结果并不需要合并成一个最终结果。因为这 R 个最终结果又可以做为另一个计算任务的输入,开始另一个并行计算任务
    ###2.3.10

    ##2.4Hadoop基本类
    ###2.4. 1 InputFormat类
    该类的作用是将输入的文件和数据分割成许多小的split文件,并将split的每个行通过LineRecorderReader解析成<Key,Value>,通过job.setInputFromatClass()函数来设置,默认的情况为类TextInputFormat,其中Key默认为字符偏移量,value是该行的值。

    ###2.4.2.Map类
    根据输入的<Key,Value>对生成中间结果,默认的情况下使用Mapper类,该类将输入的<Key,Value>对原封不动的作为中间按结果输出,通过job.setMapperClass()实现。实现Map函数。

    ###2.4.3.Combine类
    实现combine函数,该类的主要功能是合并相同的key键,通过job.setCombinerClass()方法设置,默认为null,不合并中间结果。实现map函数

    ###2.4.4.Partitioner类
    该该主要在Shuffle过程中按照Key值将中间结果分成R份,其中每份都有一个Reduce去负责,可以通过job.setPartitionerClass()方法进行设置,默认的使用hashPartitioner类。实现getPartition函数
    ###2.4.5.Reducer类
    将中间结果合并,得到中间结果。通过job.setReduceCalss()方法进行设置,默认使用Reducer类,实现reduce方法。
    ###2.4. 6.OutPutFormat类
    该类负责输出结果的格式。可以通过job.setOutputFormatClass()方法进行设置。默认使用TextOUtputFormat类,得到<Key,value>对。

    hadoop主要是上面的六个类进行mapreduce操作,使用默认的类,处理的数据和文本的能力很有限,具体的项目中,用户通过改写这六个类(重载六个类),完成项目的需求。说实话,我刚开始学的时候,我怀疑过Mapreudce处理数据功能,随着学习深入,真的很钦佩mapreduce的设计,基本就二个函数,通过重载,可以完成所有你想完成的工作

    ##2.5Hadoop编程实例
    ###2.5.1 环境搭建
    Cygwin 安装配置

    1. 下载Cygwin安装文件
    2. 运行安装文件,选择一个下载站点,继续
    3. 选择要安装的程序,默认是不安装某些组件,需要手动选择
            Net Category下的:openssh,openssl
            BaseCategory下的:sed (若需要Eclipse,必须sed)
            Devel Category下的:subversion(建议安装)
    4. 等待下载并完成安装,之后,设置环境变量,把 C:/cygwin/bin;C:/cygwin/usr/bin 加入到系统环境变量的Path中
    5. 打开cygwin,输入 ssh-host-config
        当询问if privilege separation should be used 时输入 no . 
        当询问if sshd should be installed as a service 时输入yes . 
        当询问about the value of CYGWIN environment variable enter 时输入 ntsec .
        其余询问均输入 no
    ps:如果电脑上没有 有密码的帐号,配置会不成功。此时,应该创建一个windows 带密码的帐号,也可以通过该配置界面创建一个
    6. 打开 控制面板-》管理-》服务 启动名为 CYGWIN sshd 的服务,亦可在cygwin中输入 cygrunsrv --start sshd 启动sshd,
        输入cygrunsrv --stop sshd停止sshd
    7. 打开cygwin,输入 ssh-keygen,当询问要filenames 和 pass phrases 的时候都点回车,接受默认的值
    8. 命令结束后输入 cd ~/.ssh 转到.ssh目录,输入 ls –l 应该包含两个文件:id_rsa.pub 和 id_rsa
    9. 在第8步的窗口(当前目录在.ssh)中输入 cat id_rsa.pub >> authorized_keys
    10. 输入 ssh localhost 启动SSH
    

    PS:对于window64位系统,开始我安装的是对应的64位的Cygwin,但是配置不成功,会出现如下错误。删除后,重新安装32位的cygwin后,就好了
    这里写图片描述
    在cygwin中开启停用删除服务的命令:
    开启服务: $ net start 服务名
    停止服务: $ net stop 服务名
    删除服务: $ cygrunsrv -R 服务名
    cygwin自带的命令:
    检查所有安装的软件的版本号: $ cygcheck -c
    检查当前Cygwin的版本号: $ cygcheck -c cygwin
    cygwin编译搭建hadoop环境需要安装的软件包:
    1.openssh
    2.openssl
    3.sed
    4.zlib
    4.tcp_wrappers
    5.diffutils
    6.vim
    7.subversion
    cygwin没有自动卸载功能,需要手动操作3个步骤如下:
    1.停止服务: $ net stop 服务名
    2.删除服务: $ cygrunsrv -R 服务名
    3.删除cygwin文件

    伪分布模式配置
    可以把伪分布模式看作是只有一个节点的集群,在这个集群中,这个节点既是Master,也是Slave,既是NameNode,也是DataNode,既是JobTracker,也是TaskTracker
    这种模式也是在一台单机上运行,但用不同的 Java 进程模仿分布式运行中的各类结点 ( NameNode, DataNode, JobTracker, TaskTracker, Secondary NameNode ),请注意分布式运行中的这几个结点的区别:
    从分布式存储的角度来说,集群中的结点由一个 NameNode 和若干个 DataNode 组成, 另有一个 Secondary NameNode 作为 NameNode 的备份。 从分布式应用的角度来说,集群中的结点由一个 JobTracker 和若干个 TaskTracker 组成,JobTracker 负责任务的调度,TaskTracker 负责并行执行任务。TaskTracker 必须运行在 DataNode 上,这样便于数据的本地计算。JobTracker 和 NameNode 则无须在同一台机器上

    hadoop配置文件详解、安装及相关操作
    http://blog.csdn.net/lin_fs/article/details/7349497
    http://blog.csdn.net/ruby97/article/details/7423088
    注意事项:
    对于配置文件的更改,我开始是直接在window下打开修改的,结果出现如下错误:
    这里写图片描述
    原因:在windows下打开修改后,会更改文件的编码方式,使得文件在linux环境下读取错误问题
    解决办法:
    1.使用utraedit工具打开后,转换成Linux编码方式
    2.重新操作,在复制后,不在window下修改,直接在Linux中用vim编辑器打开修改(需要了解vim命令)
    改完之后,重新操作,结果如下:
    这里写图片描述

    关于错误:ipc.Client: Retrying connect to server: localhost/127.0.0.1:9000. Already tried 0 time(s).的错误。hadoop安装完成
    用jps命令,也看不不到namenode的进程, 必须再用命令hadoop namenode format格式化后,才能再使用
    原因是:hadoop默认配置是把一些tmp文件放在/tmp目录下,重启系统后,tmp目录下的东西被清除,所以报错
    解决方法:在conf/core-site.xml (0.19.2版本的为conf/hadoop-site.xml)中增加以下内容

       <property>
        <name>hadoop.tmp.dir</name>
        <value>/var/log/hadoop/tmp</value>
       <description>A base for other temporary directories</description>
       </property>
       重启hadoop后,格式化namenode即可 
    

    测试配置是否成功
    浏览器下查看Hadoop系统情况的地址。
    http://127.0.0.1:50070/ HDFS情况
    http://127.0.0.1:50060/ Task Tracker 情况
    http://127.0.0.1:50030/ Job Tracker-Map/Reduce Administration
    这里写图片描述

    ###2.5. 2 hadoop命令 1. 格式化工作空间 bin/hadoop namenode –format
    1. 启动hdfs
      进入hadoop目录,在bin/下面有很多启动脚本,可以根据自己的需要来启动。

    三、Hadoop hdfs 整合
    可按如下步骤删除和更改hdfs不需要的文件:
    1.将hadoop-core-1.0.0.jar 移动到lib目录下。
    2. 将ibexec目录下的文件移动到bin目录下。
    3. 删除除bin、lib、conf、logs之外的所有目录和文件。
    4. 如果需要修改日志存储路径,则需要在conf/hadoop-env.sh文件中增加:
    export HADOOP_LOG_DIR=/home/xxxx/xxxx即可。
    四、HDFS文件操作
    Hadoop使用的是HDFS,能够实现的功能和我们使用的磁盘系统类似。并且支持通配符,如*。

    1. 查看文件列表
      查看hdfs中/user/admin/hdfs目录下的文件:bin/hadoop fs -ls /user/admin/hdfs
      查看hdfs中/user/admin/hdfs目录下的所有文件(包括子目录下的文件):bin/hadoop fs -lsr /user/admin/hdfs

    2. 创建文件目录
      新建一个叫做newDir的新目录:bin/hadoop fs -mkdir /user/admin/hdfs/newDir

    3. 删除hdfs中/user/admin/hdfs目录下一个名叫needDelete的文件: bin/hadoop fs -rm /user/admin/hdfs/needDelete
      删除hdfs中/user/admin/hdfs目录以及该目录下的所有文件:bin/hadoop fs -rmr /user/admin/hdfs

    4. 上传文件
      上传一个本机/home/admin/newFile的文件到hdfs中/user/admin/hdfs目录下
      sh bin/hadoop fs –put /home/admin/newFile /user/admin/hdfs/

    5. 下载文件
      下载hdfs中/user/admin/hdfs目录下的newFile文件到本机/home/admin/newFile中
      执行sh bin/hadoop fs –get /user/admin/hdfs/newFile /home/admin/newFile

    6. 查看hdfs中/user/admin/hdfs目录下的newFile文件
      bin/hadoop fs –cat /home/admin/newFile

    7.学习各种 HDFS 命令的使用:bin/hadoop dfs –help 可以

    ###2.5. 3 运行 wordcount 应用
    1.将本地文件系统上的 ./test-in 目录拷到 HDFS 的根目录上,目录名改为 input
    $ bin/hadoop dfs -put test input

    2.查看执行结果,将文件从 HDFS 拷到本地文件系统中再查看:
    $ bin/hadoop jar hadoop-0.20.0-examples.jar wordcount input output
    $ bin/hadoop dfs -get output output
    $ cat output/*
    也可以直接查看
    $ bin/hadoop dfs -cat output/*
    $ bin/stop-all.sh #停止 hadoop 进程

    ###2.5.4 eclipse编程环境搭建
    http://www.cnblogs.com/flyoung2008/archive/2011/12/09/2281400.html

    展开全文
  • 浅谈并行编程中的任务分解模式

    千次阅读 2014-06-04 16:59:11
     并行编程使用线程来使得多个操作能够同时运行。... 不熟悉并行编程的开发者通常对例如面向对象的传统的编程模式感到非常适应。在传统的编程模式下,程序以预先定义的起点开始运行,譬如main函数,然后接连地做完
  • 并行编程中的设计模式

    千次阅读 2014-04-10 22:02:19
    这篇文章是对这段时间学习并行编程中的设计模式的一个总结。有不当之处,希望得到大家的批评、指正。 首先,所谓“并行编程中的设计模式”(patterns in parallel programming)仍处于不断的被发现、发掘的阶段。...
  • 3.并行循环使用模式 3.1并行For循环 3.2并行ForEach循环 3.3并行LINQ(PLINQ) 1】开篇介绍 最近这几天在捣鼓并行计算,发现还是有很多值得分享的意义,因为我们现在很多人对它的理解还是有点不准确,包括我自己也...
  • 简述并行编程

    千次阅读 2007-05-26 13:25:00
    并行编程模式主要有三种,那么三种模式的优劣又是怎样的呢?请看下文: 并行编程模式主要有以下三种: 共享地址空间模式:以OpenMP为代表,主要是利用添加并行化指令到顺序程序中,由编译器完成自动并行化。 消息传递...
  • 并行编程模型

    千次阅读 2017-03-12 17:19:33
    在计算领域,并行编程模型是并行计算机体系架构的一种抽象,它便于编程人员在程序中编写算法及其组合。一个编程模型的价值可以通过其通用性(generality)来判断,如不同体系架构的一系列不同的问题能否在该模型中很...
  • 服务器编程之fork并行模式

    千次阅读 2013-08-09 17:01:47
    服务器编程之fork并行模式 ...fork是POSIX系统中产生新进程的唯一方法,可以实现进程并行编程模式。 在介绍服务器编程的fork模式之前,我们首先来说说fork自身的问题,对于深知fork的读者可以跳过本段
  • 并行计算复习第四篇 并行计算软件支撑:并行编程
  • OpenMP并行编程

    千次阅读 2012-11-07 15:39:43
    OpenMP并行编程 Posted in 并行计算 on June 26th, 2010 距离上次写并行计算概述很有段日子了,后续的可能至少有三篇文章需要写。今天花了点时间针对Openmp共享内存的并行编程写了点东西。这里只能提供一点...
  • C#并行编程(3):并行循环

    万次阅读 2019-04-13 08:43:57
    C#并行编程(3):并行循环 初识并行循环 并行循环主要用来处理数据并行的,如,同时对数组或列表中的多个数据执行相同的操作。 在C#编程中,我们使用并行类System.Threading.Tasks.Parallel提供的静态方法...
  • 并发编程模式

    千次阅读 多人点赞 2019-07-31 20:12:05
    一、future模式 在网上购物时,提交订单后,在收货的这段时间里无需一直在家里等候,可以先干别的事情。类推到程序设计中时,当提交请求时,期望得到答复时,如果这个答复可能很慢。传统的是一直等待到这个答复收到...
  • C#并行编程(1):理解并行

    万次阅读 2019-04-13 08:41:12
    C#并行编程(1):理解并行 什么是并行 并行是指两个或者多个事件在同一时刻发生。 在程序运行中,并行指多个CPU核心同时执行不同的任务;对于单核心CPU,严格来说是没有程序并行的。并行是为了提高任务执行效率...
  • SAP HANA并行编程

    千次阅读 2013-04-30 23:12:38
    并行对于现代的大数据的处理...相对于Hadoop,在SAP HANA中实现并行编程是比较容易的,SAP HANA的并行对Developer来说是透明的,只需遵循一定的规则,数据库会自动的实现并行。 其中有两条规则至关重要: 1. store
  • C# 并行编程 之 异步编程模型

    千次阅读 2015-06-17 09:21:50
    异步编程模型的使用
  • 并行编程OpenMP基础及简单示例

    万次阅读 多人点赞 2016-12-24 22:30:16
    OpenMP基本概念 OpenMP是一种用于共享内存...编译器根据程序中添加的pragma指令,自动将程序并行处理,使用OpenMP降低了并行编程的难度和复杂度。当编译器不支持OpenMP时,程序会退化成普通(串行)程序。程序中已有
  • 基于多核的并行编程

    千次阅读 2018-09-08 17:53:36
    并行(Concurrency):two or more progress are in progress at the same time. 当系统有一个以上CPU时,则线程的操作有可能非并发,当一个CPU执行一个线程时,另一个CPU可以执行另一个线程,两个线程互不抢占CP
  • Java 并发包下的提供Lock,Lock相对于Synchronized可以更好的解决线程同步问题,更加的灵活和高效,并且ReadWriteLock锁还能实现读、写的分离。但线程间仅仅互斥是不够的,...可以查看:Java并发编程-阻塞队列(Blockin
  • 随着多核时代的到来与流行,传统的单线程串行程序的编程模式必将改变,取而代之的将是并行编程。目前已经有五种主要并行编程模型,下面将对此五种模型进行概括性的分析与比较: 1. MPI  MPI(Message Passing ...
  • Guava - 并行编程Futures

    千次阅读 2017-07-04 14:37:01
    这里转载一篇关于Guava - 并行编程Futures介绍,随后附上自己的调用: 1、介绍 Guava为Java并行编程Future提供了很多有用扩展,其主要接口为ListenableFuture,并借助于Futures静态扩展。 继承至Future的...
  • MATLAB并行编程

    千次阅读 2015-10-08 10:26:29
    1 并行问题的由来——从抛硬币说起  举个简单的例子:抛100次硬币统计正面向上的次数。我们可以拿一个硬币重复地抛100次。但有人嫌麻烦,就想能不能再叫一个人带另外一个硬币过来,两个人同时抛,这样每个人就能...
  • python并行编程 - GPU篇

    千次阅读 2018-11-29 12:50:47
    设计并行编程 任务分解:将程序分解为任务,在不同处理器上执行以实现并行化。(可以使用以下两种方法) 领域分解:将问题数据分解 (当处理的数据量很大时,分开处理) 功能性分解:将问题分解为任务 (把大...
  • 几种多核并行编程方法的比较

    千次阅读 2013-07-06 12:19:15
    随着多核时代的到来与流行,传统的单线程串行程序的编程模式必将改变,取而代之的将是并行编程。目前已经有四种主要并行编程模型,下面将对此五种模型进行概括性的分析与比较: 1. MPI  MPI(Message Passing ...
  • 用 Hadoop 进行分布式并行编程

    千次阅读 2012-10-09 21:16:46
    用 Hadoop 进行分布式并行编程 Hadoop 简介摘要:Hadoop 是一个实现了 MapReduce 计算模型的开源分布式并行编程框架,借助于 Hadoop, 程序员可以轻松地编写分布式并行程序,将其运行于计算机集群上,完成海量数据...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 122,166
精华内容 48,866
关键字:

并行编程模式目录