从BSP模型到Apache Hama

 

一、什么是BSP模型

– 概述

  BSP(Bulk Synchronous Parallel,全体一并并行总结模型)是一种并行统计模型,由大英帝国总括机科学家Viliant在上世纪80年代提出。谷歌(Google)发布的一篇随想(《Pregel:
A System for Large-Scale Graph
Processing》)使得这一概念被更三个人所认识,据说在Google80%的程序运行在MapReduce上,20%的程序运行在Pregel上。和MapReduce一样,谷歌(Google)并从未开源Pregel,Apache按Pregel的想想提供了近乎框架Hama。

– 并行总计模型介绍

  并行统计模型平日指从并行算法的计划性和分析出发,将各个互动计算机(至少某一类并行计算机)的基本特征抽象出来,形成一个虚无的盘算模型。从更广的含义上说,并行总计模型为并行计算提供了硬件和软件界面,在该界面的预订下,并行系统硬件设计者和软件设计者可以付出对并行性的支撑机制,从而增强系统的习性。

  常用的并行计算模型有:PRAM模型LogP模型、BSP模型、C3模型BDM模型

 

 

二、BSP模型基本原理

 

  BSP模型是一种异步MIMD-DM模型(DM:
distributed memory,SM: shared
memory),BSP模型支撑音讯传递系统,块内异步并行,块间显式同步,该模型基于一个master协调,所有的worker同步(lock-step)执行,
数据从输入的体系中读取,该模型的架构如图所示:

NoSQL 1

  其余,BSP并行统计模型可以用 p/s/g/I 4个参数进行描述:

  1. P为处理器的数码(带有存储器)。

  2. s为总结机的持筹握算速度。

  3. g为每秒本地总结操作的数目/通讯网络每秒传送的字节数,称之为选路器吞吐率,视为带宽因子
    (time steps/packet)=1/bandwidth。

  4. i为大局的一头时间支付,称之为全局同步之间的小运间隔 (Barrier
    synchronization time)。

    那么借使有p台处理器并且传送h个字节新闻,则gh就是通讯的支出。同步和通讯的付出都规格化为处理器的指定条数。

    BSP总计模型不仅是一种连串布局模型,也是规划并行程序的一种艺术。BSP程序设计准则是完整一并(bulk
    synchrony),其特有之处在于超步(superstep)概念的引入。一个BSP程序同时持有水平和垂直五个地方的社团。从垂直上看,一个BSP程序由一星罗棋布串行的超步(superstep)组成,如图所示:

    NoSQL 2

    那种布局类似于一个串行程序结构。从品位上看,在一个超步中,所有的进程并行执行局部统计。一个超步可分为八个阶段,如图所示:

    NoSQL 3    

1.  本地计算阶段,每个处理器只对存储本地内存中的数据进行本地计算。

2.  全局通信阶段,对任何非本地数据进行操作。

3.  栅栏同步阶段,等待所有通信行为的结束。

 

三、BSP模型特点

  1. BSP模型将计算划分为一个一个的超步(superstep),有效幸免死锁。

2.
它将电脑和路由器分开,强调了总括职分和通讯职责的离别,而路由器仅仅落成点到点的音信传递,不提供组成、复制和播放等功效,那样做既掩盖具体的互连互连网拓扑,又简化了通讯协议;

3.
选取障碍同步的格局以硬件落成的全局同步是在可控的粗粒度级,从而提供了实施紧耦合同步式并行算法的实惠办法,而程序员并无过度的承担;

4.
在条分缕析BSP模型的习性时,假定一些操作可以在一个时光步内完结,而在每一个顶尖步中,一个总计机至多发送或收取h条新闻(称为h-relation)。假定s是传输建马上间,所以传送h条音讯的时间为gh+s,如若,则L至少应该超过等于gh。很通晓,硬件可以将L设置尽量小(例如利用流水线或大的通信带宽使g尽量小),而软件可以设置L的上限(因为L越大,并行粒度越大)。在实际应用中,g可以定义为每秒处理器所能完结的有些计算数据与每秒路由器所能传输的数据量之比。若是能够适当的平衡总计和通讯,则BSP模型在可编程性方面抱有举足轻重的优点,而一向在BSP模型上举办算法(不是机动的编译它们),这么些优点将随着g的增多而更为不问可见;

5.
为PRAM模型所安顿的算法,都足以利用在各类BSP处理器上模仿一些PRAM处理器的章程来贯彻。

 

四、BSP模型的评论

 

1.
在并行统计时,Valiant试图也为软件和硬件之间架起一座类似于冯·诺伊曼机的大桥,它论证了BSP模型可以起到这样的职能,正是因为这么,BSP模型也常叫做桥模型。

2.
形似而言,分布存储的MIMD模型的可编程性相比较差,但在BSP模型中,即便统计和通讯可以方便的平衡(例如g=1),则它在可编程方面显示出主要的助益。

3.
在BSP模型上,曾一贯完成了一部分重中之重的算法(如矩阵乘、并行前序运算、FFT和排序等),他们均幸免了自动存储管理的额外费用。

4.
BSP模型可以使得的在超立方体互连网和光交叉开关互连技术上贯彻,突显出,该模型与特定的技术完毕毫无干系,只要路由器有肯定的通讯吞吐率。

5.
在BSP模型中,一流步的长度必须可以丰裕的适应任意的h-relation,那一点是人们最不欣赏的。

6.
在BSP模型中,在一流步起先发送的信息,即便互连网延迟时间比一级步的尺寸短,该音信也不得不在下一个一级步才能被利用。

7.
BSP模子中的全局障碍同步假定是用特殊的硬件协理的,但不少并行机中或许没有对号入座的硬件。

 

五、BSP与MapReduce对比

 

  执行机制:MapReduce是一个数码流模型,每个职责只是对输入数据举行拍卖,爆发的出口数据作为另一个职分的输入数据,并行职务之间独立地举办,串行任务之间以磁盘和数目复制作为沟通介质和接口。

  BSP是一个状态模型,种种子职务在该地的子图数据上开展测算、通讯、修改图的动静等操作,并行义务之间通过音信通信交换中间总结结果,不需求像MapReduce那样对任何数据进行复制。

  迭代处理:MapReduce模型理论上急需接二连三开行若干作业才得以成功图的迭代处理,相邻作业之间通过分布式文件系统交流全体多少。BSP模型仅启动一个功课,利用多个超步就足以成功迭代处理,一次迭代里面通过音讯传递中间计算结果。由于收缩了课业启动、调度开支和磁盘存取费用,BSP模型的迭代执行功能较高。

  数据分割:基于BSP的图处理模型,须求对加载后的图数据开展四次再分布的进程,以确定新闻通讯时的路由地址。例如,各职责并行加载数据经过中,依据早晚的映射策略,将读入的数码再次分发到对应的计量义务上(平日是身处内存中),既有磁盘I/O又有网络通讯,开支很大。可是一个BSP作业仅需一遍数据分割,在事后的迭代总括进程中除去信息通讯之外,不再供给展开数据的动迁。而据悉MapReduce的图处理模型,一般情状下,不须要特其余数码分割处理。可是Map阶段和Reduce阶段存在中间结果的Shuffle进度,扩大了磁盘I/O和互连网通信支出。

  MapReduce的宏图初衷:解决广大、非实时数据处理难题。”大规模”决定数据有局部性特性可利用(从而得以划分)、可以批处理;”非实时”代表响应时间可以较长,有足够的岁月实施顺序。而BSP模型在实时处理有完美的显现。那是二者最大的一个有别于。

 

六、BSP模型的落实

 

1.Pregel

  谷歌的普遍图计算框架,首次提议了将BSP模型应用于图总括,具体请看Pregel——大规模图处理连串,不过至今未开源。

http://blog.csdn.net/strongwangjiawei/article/details/8120318

2.Apache Giraph

  ASF社区的Incubator项目,由Yahoo!进献,是BSP的java达成,专注于迭代图统计(如pagerank,最短连接等),每一个job就是一个从未reducer进度的hadoop
job。http://giraph.apache.org/

3.Apache Hama

  也是ASF社区的Incubator项目,与Giraph不一致的是它是一个纯粹的BSP模型的java达成,并且不单单是用于图计算,意在提供一个通用的BSP模型的施用框架。http://hama.apache.org/

4.GraphLab

  CMU的一个迭代图总结框架,C++落成的一个BSP模型应用框架,不过对BSP模型做了必然的修改,比如每一个超步之后并不设置全局同步点,总计可以完全异步进行,加快了义务的完结时间。http://graphlab.org/

5.Spark

  加州大学Berkeley分校落到实处的一个注意于迭代测算的采纳框架,用Scala语言写就,提议了RDD(弹性分布式数据集)的定义,每一步的测算数据都从上一步结果精简而来,大大下落了互连网传输,同时确保了血统的纯正性(即出错只需再次回到上一步即可),增强了容错功效。斯Parker小说里也根据此框架完成了BSP模型(叫Bagel)。值得一提的是国内的豆瓣也按照该考虑用Python落成了这么一个框架叫Dpark,并且已经开源。https://github.com/douban/dpark

6.Trinity

  这是微软的一个图统计平台,C#支出的,它是为着提供一个专用的图总括应用平台,包罗底层的囤积到上层的使用,应该是能够完毕BSP模型的,小说发在SIGMOD13上,可恨的是也不开源。

  主页http://research.microsoft.com/en-us/projects/trinity/

 

以下多少个也是部分BSP的达成,可是关怀度不是很高,基本都是对Pregel的开源落成:

7.GoldenOrb

另一个BSP模型的java达成,是对Pregel的一个开源达成,应用在hadoop上。

官网:http://www.goldenorbos.org/(要FQ)

源码:https://github.com/jzachr/goldenorb

8.Phoebus

Erlang语言达成的BSP模型,也是对Pregel的一个开源达成。

https://github.com/xslogic/phoebus

9.Rubicon

  Pregel的开源已毕。https://launchpad.net/rubicon

10.Signal/Collect

  也是一个Scala版的BSP模型完毕。http://code.google.com/p/signal-collect/

11.PEGASUS

在hadoop上完毕的一个java版的BSP模型,公布在SIGKDD2011上。

http://www.cs.cmu.edu/~pegasus/index.htm

 

七、Apache Hama简介

– Hama概述

背景:

  二零零六年4月Hama被视为Apache众多类型中一个被孵化的连串,作为Hadoop项目中的一个子项目,BSP模型是Hama总括的主干,并且达成了分布式的盘算框架,拔取这一个框架可以用来矩阵总结(matrix)和面向图计算(graph)、互连网总结(network)。

  Hama是成立在Hadoop上的分布式并行计算模型。基于Map/Reduce 和 Bulk
Synchronous的贯彻框架。运行条件须要关联Zookeeper、Hbase、HDFS组件。集群环境中的系统架构由BSPMaster/GroomServer(Computation
Engine)、Zookeeper(Distributed Locking)、HDFS/Hbase(Storage
Systems)那3大块组成。Hama中有2个基本点的模子: 矩阵计算(Matrix package)和
面向图总计(Graph package)。

  Hama的首要应用领域是:矩阵计算、面向图总计、PageRank、排序计算、BFS。

– Hama Architecture

Hama系统架构

  Apache的Hama首要由三个部分构成:BSPMaster,GroomServers和Zookeeper,上边那张图根本概述了Hama的完整系统架构,并且描述了系统模块之间的报导与互相。Hama的集群中需求有HDFS的运作环境担负持久化存储数据(例如:job.jar),BSPMaster负责举办对Groom
Server 进行职分调配,groom Server
负责进行对BSPPeers举办调用程序开展具体的调用,Zookeeper负责对Groom
Server 进行失效转载。

NoSQL 4

BSPMaster(划分统计到Groom,管理Groom,类似MapReduce的JobTracker)

  在Apache
Hama中BSPMaster模块是系统中的一个要害角色,他器重担负的是联名各样计算节点之间的干活,每一个测算节点在其登记到master上来的时候会分配到一个唯一的ID。Master内部维护着一个盘算节点列表,讲明当前什么总计节点出于alive状态,该列表中就包含各样总结节点的ID和地点音讯,以及哪些计算节点上被分配到了整个统计义务的哪一部分。Master中这一个音信的数据结构大小取决于整个统计职分被分为多少个partition。由此,一台一般布局的BSPMaster丰硕用来协调对一个大型计算。
上边我们来看望BSPMaster做了怎么样工作:

    1. 保安着Groom服务器的景况。
    2. 控制在集群环境中的superstep。
    3. 保安在groom中job的做事意况新闻。
    4. 分配义务、调度职务到独具的groom服务器节点。
    5. 播音拥有的groom服务器执行。
    6. 管制种类节点中的失效转载。
    7. 提供用户对集群环境的管制界面。

  一个BSPMaster或者七个grooms服务器是由此脚本启动的,在Groom服务器中还包蕴了BSPeer的实例,在开行GroomServer的时候就会启动了BSPPeer,BSPPeer是整合在GrommServer中的,GrommServer通过PRC代理与BSPmaster连接。当BSPmaster、GroomServer启动完成之后,每个GroomServer的生命周期通过发送”心跳”信息给BSPmaster服务器,在这些”心跳”音信中涵盖了GrommServer服务器的情事,这一个景况包涵了可以处理职责的最大容量,和可用的系统内存状态,等等。

  BSPMaster的绝大多数行事,如input
,output,computation,saving以及resuming from
checkpoint,都将会在一个称作barrier的地点停下。Master会在每两回操作都会发送相同的一声令下到具备的计算节点,然后等待从各类计算节点的对答(response)。每四遍的BSP主机接收心跳音信之后,那些音讯会牵动了新式的groom服务器状态,BSPMaster服务器对交付一个答应的新闻,BSPMaster服务器将会与groom
服务器进行确定活动的groom server空闲状态,也就是groom
服务器可资源并且对其举办职务调度和义务分配。BSPMaster与Groom
Server两者之间通信应用分外简单的FIFO(先进先出)原则对计量的天职展开分配、调度。

GroomServer

  一个Groom服务器对应一个拍卖BSPMaster分配的义务,每个groom都亟待与BSPMaster进行报导,处理任务并且想BSPMaster处理告知景况,集群状态下的Groom
Server须求周转在HDFS分布式存储环境中,而且对于Groom Server来说一个groom
服务器对应一个BSPPeer节点,需求周转在同一个物理节点上。

ZookeeperNoSQL,

  在Apache
HaMa项目中zookeeper是用来有效的军事管制BSPPeer节点之间的共同间隔(barrier
synchronization),同时在系统失效转载的成效上揭橥了紧要的功效。

1. 1. Apache Hama作业流程

NoSQL 5

  1. 一个新的job被交付后,BSPJobClient先做一些伊始化Job的干活:准备好学业的输入资源、代码等。

  2. BSPMaster将Job划分为一个个的task,将task分配给GroomServer去执行,执行进程中维护GroomServer的进度与气象。GroomServer发送心跳给BSPMaster来保持通讯。顶尖步的主宰是由BSPMaster完毕的。

  3. GroomServer启动BSPPeer,由BSPPeer来具体举办task。GroomServer主要任务是BSPPeer的开行和终止,维护任务的实践意况,向BSPMaster报告意况。一个GroomServer可运行五个task。类似于MapReduce的tasktracker的职务槽。所有的task有一个masterTask,masterTask在整个统计先导和得了时分别调用setup()和cleanup()。如若该GroomServer下的一个task失利,GroomServer会重新起动这么些task,如果3次重启task都失利,则GroomServer向BSPMaster汇报该义务失利。

  4. BSPeer在总括时期间的通讯是P2P方式开展的,由zookeeper负责调度。在一个超步中BSPeer只可以发新闻或者处理上一个超步中吸收到的音信。例:A发送音讯给B—>栅栏—>这一次一级步停止下一个一流步先导—>B接收到A发送的新闻—>……

    别的,默许配置下Hama是即将发送的和接到到的新闻都缓存在内存中,所以hama本身的一起通讯功效不相符做多量数据传递,它只适合在联合总括进程中发送少量的音信。

  5. 在方方面面总括进程中,zookeeper负责栅栏同步,未来会用来容错机制。

 

– Apache Hama与Google Pregel

  Hama类似谷歌发明的Pregel,若是你听过谷歌Pregel那几个利器的话,那么就对BSP统计模型不会陌生,谷歌(Google)的Pregel也是基于BSP模型,在谷歌的全体统计种类中有20%的盘算是依赖于Pregel的揣测模型,谷歌(Google)利用Pregel完毕了图遍历(BFS)、最短路径(SSSP)、PageRank统计,我臆想谷歌的谷歌 Me
产品很有可能会大方利用Pregel的计量方法,用Pregel来绘制谷歌(Google)Me产品中SNS的涉嫌图。

  谷歌的Pregel是应用GFS或BigTable举办绳锯木断存储,谷歌(Google)的Pregel是一个Master-slave主从布局,有一个节点扮演master角色,其余节点通过name
service定位该终端并在第四次时展开挂号,master负责对计量职务进展切分到各节点(也得以协调指定,考虑load
balance等要素),依据顶ID哈希分配顶点到机械(一个机器可以有两个节点,通过name
service进行逻辑区分),每个节点间异步传输新闻,通过checkpoint机制实施容错(更尖端的容错通过confined
recovery完毕),并且每个节点向master汇报心跳(ping)维持状态。

  Hama是Apache中Hadoop的子项,所以Hama可以与Apache的HDFS进行宏观的整合,利用HDFS对须求周转的天职和数量开展持久化存储,也足以在别的文件系统和数据库中。当然大家得以信任BSP模型的处理统计能力是相对没有极限的尤其对于图统计的话,换句话说BSP模型如同MapReduce一样可以广泛的行使在其他一个分布式系统中,我们可以尝试的对落实选用Hama框架在分布式总结中收获越来越多的推行,比如:矩阵总括、排序总括、pagerank、BFS
等等。

– Hama与MapReduce对比

MapReduce的不足:

  1. MapReduce 紧要针对松耦合型的数据处理利用,
    对于不便于分解成众多相互独立子职责的紧耦合型计算职分, 处理功用很低。

  2. MapReduce 不可以显式的接济迭代计算。

  3. MapReduce 是一种离线统计框架, 不符合进行流式计算和实时分析。

Hama的优势:

1.
在科学计算领域的适用性:Hama提供的底子零部件可以适应三种索要矩阵和图纸统计的采取。MapReduce在唯有的科普科学总括方面存在不足。比如求一个巨型矩阵的逆矩阵,须求展开大批量的迭代计算,而读写文件的次数并不多。此时Hama的迭代速度快的优势便显示出来。

2.
包容性:Hama能动用Hadoop和它相关的装有功用,因为Hama很好的格外了现有Hadoop接口;

3.
可扩大性:得益于Hama的包容性,Hama可以丰裕利用大规模分布式接口的底蕴功用和劳务,比如亚马逊(亚马逊(Amazon))EC2足以不要任何修正就足以选择Hama;

4.
编程形式的油滑:为了保险灵活性来支撑分裂的总计形式,Hama提供了简要计算引擎接口;任何遵守此接口的预计引擎都能随随便便过渡和退出;

 

– Hama亟待解决的标题

 

  1. 全盘容错能力。

  2. NoSQL的输入输出格式

  3. 无视同台(消除栅栏)

  4. 利用异步音信:现在音讯是在一流步的末梢进行传递,在超级步里信息异步发送会推动更加多的面世设计。

– Hama容错机制

BSPMaster出错:

  【未解决】https://issues.apache.org/jira/browse/HAMA-509

GroomServer出错:

  恢复GroomServer上的task。【未解决】https://issues.apache.org/jira/browse/HAMA-618

task出错:

  当BSPMaster发现义务出错时,控制GroomServer復苏task。【已解决】https://issues.apache.org/jira/browse/HAMA-534

  task会周期pingGroomServer,若是不能够ping通则杀死自己,如若GroomServer长时间收不到某task的ping音讯,则检查task是或不是正常运行。【已解决】https://issues.apache.org/jira/browse/HAMA-498

 

summarizes:

https://issues.apache.org/jira/browse/HAMA-505

 

– Hama API

BSP

1.编辑自己的BSP类须要一而再org.apache.hama.bsp.BSP ,并且需求重写bsp()方法,bsp()方法的宣示如下:

public abstract void bsp(BSPPeer<K1, V1, K2, V2, M extends
Writable> peer) throws IOException, SyncException,
InterruptedException;

2.规行矩步大家团结一心的政工编写bsp()方法,该办法内含有一个或多个超步,栅栏同步接口是peer.sync();

3.进度间通讯接口如下:

NoSQL 6

    上面是一个发送接收音信的事例:

NoSQL 7

4.在大家团结一心的BSP类中还有setup()和cleanup()四个措施,分别在bsp()方法在此之前和之后执行,可以对那三个办法重写,完结部分必要。BSP类概要如下图:

NoSQL 8

Graph

1.
hama提供了Graph包,接济顶点为骨干的图统计,使用较少的代码就可以兑现google
Pregel风格的拔取。

兑现一个Hama
Graph应用包罗对预订义的Vertex类举办子类化,模板参数涉及3种档次,顶点、边和音信(
vertices, edges, and messages ):

NoSQL 9

用户重写compute()方法,该格局将在每个超步的外向顶点中执行。Compute()方法能够查询当前终端及其边的新闻,并向其余顶点发送音信。

2.经过持续 org.apache.hama.graph. VertexInputReader
类,根据自己的文件格式创制自己的 VertexReader,示例如下:

NoSQL 10

    1. 经过持续org.apache.hama.graph.AbstractAggregator类,可以编写自己的聚合器。聚合器用来做全局的通信、监控等。超步内具备的终极都得以给聚合器一个值,聚合器整合所有点提供的值,在下一个超步每个终端都可以选拔聚合器整合后的值。在一个job里可以使用多个聚合器,只需求在创建job时登记一下即可,注册如下:

      NoSQL 11

极限使用聚合器是按聚合器注册时的各种(0,1,2,3…)向聚合器发送数据,以及使用聚合器内的数码的api如下:

极限提供值给聚合器:

NoSQL 12

 

终极使用聚合器:

NoSQL 13

 

八、安装Hama

  见文章:http://www.cnblogs.com/BYRans/p/4588276.html

 

九、编写Hama job

  在eclipse下新建Java Project,将hama安装时须要的jar包全体导入工程。

官网中计算PI的事例:

(代码见官网文档)

  将工程Export成Jar文件,发到集群上运行。运行命令:

  $HAMA_HOME/bin/hama jar jarName.jar

  输出:

 

NoSQL 14

 

Current supersteps number: 0()

Current supersteps number: 4()

The total number of supersteps: 4(总顶级步数目)

Counters: 8(一共8个计数器)

SUPERSTEPS=4(BSPMaster一流步数目)

LAUNCHED_TASKS=3(共多少个task)

org.apache.hama.bsp.BSPPeerImpl$PeerCounter

SUPERSTEP_SUM=12(总共的一流步数目,task数目*BSPMaster一级步数目)

MESSAGE_BYTES_TRANSFERED=48(传输信息字节数)

TIME_IN_SYNC_MS=657(同步消耗时间)

TOTAL_MESSAGES_SENT=6(发送新闻条数)

TOTAL_MESSAGES_RECEIVED=6(接收音信条数)

TASK_OUTPUT_RECORDS=2(义务输出记录数)

  

PageRank例子:

(代码见附件)

输出:

NoSQL 15

 

十、相关知识介绍

  • ### PRAM模型

  PRAM(Parallel Random Access
Machine,随机存取并行机器)模型,也称之为共享存储的SIMD模型,是一种浮泛的并行总结模型,它是从串行的RAM模型直接发展起来的。在那种模型中,假定存在一个容量无限大的共享存储器,有有限个或极端个效益雷同的处理器,且他们都兼备简易的算术运算和逻辑判断成效,在任曾几何时刻个总结机都足以透过共享存储单元相互交互数据。

 

PRAM模型的长处:

  PRAM模型尤其吻合于并行算法的公布、分析和相比较,使用简易,很多有关相互计算机的底部细节,比如拍卖器间通信、存储系统管理和进程同步都被含有在模型中;易于设计算法和稍加修改便得以运行在区其他交互总括机种类上;根据须要,可以在PRAM模型中插足一些诸就像步和通信等急需考虑的始末。

 

PRAM模型的弱点:

1.
模型中动用了一个大局共享存储器,且局存容量较小,不足以描述分布主存多处理机的性质瓶颈,而且共享单一存储器的借使,显明不吻合于分布存储结构的MIMD机器;

2.
PRAM模型是联合的,那就意味着所有的下令都听从锁步的法子操作,用户固然觉得不到一起的留存,但共同的留存真正很成本时间,而且不能反体现实中很多体系的异步性;

3.
PRAM模型即使了各类处理器可在单位时间访问共享存储器的任一单元,因而要求处理机间通讯无延迟、无限带宽和无开支,假定每个处理器均可以在单位时间内访问任何存储单元而略去了实际存在的,合理的细节,比如资源竞争和少数带宽,那是不具体的;

4.
未能描述八线程技术和流程预取技术,而那二种技术又是后日相互连串布局用的最普遍的技艺。

 

  • ### LogP模型

由Culler(1993)年提出的,是一种分布存储的、点到点通信的多处理机模型,其中通信由一组参数描述,举办隐式同步。

 

LogP模型是一种分布存储的、点到点通讯的多处理机模型,其中通讯互联网由4个紧要参数来讲述:

  1. L(Latency)
    表示源处理机与目标处理机进行音信(一个或多少个字)通讯所急需的等待或延迟时间的上限,表示互联网中消息的推迟。

2.
o(overhead)表示处理机准备发送或接收每个音讯的年华支付(包涵操作系统主题开发和互连网软件费用),在那段时光里处理不可能实施别的操作。

3.
g(gap)表示一台处理机延续两遍发送或收受音信时的细微时间间隔,其倒数即微处理机的通讯带宽。

  1. P(Processor)处理机/存储器模块个数。

 

LogP模型的特点:

1.
抓住了互连网与处理机之间的特性瓶颈。g反映了通讯带宽,单位时间内最多有L/g个音信能拓展拍卖机间传送。

  1. 处理机之间异步工作,并因此处理机间的消息传送来完结一道。

3.
对八线程技术有一定反映。每个物理处理机可以上行下效七个虚拟处理机(VP),当某个VP有访问请求时,计算不会停下,但VP的个数受限于通讯带宽和上下文沟通的开销。VP受限于互联网容量,至多有L/g个VP。

4.
新闻延迟不确定,但延迟不大于L。音信经历的守候时间是不足预测的,但在未曾阻塞的情景下,最大不当先L。

5.
LogP模型鼓励编程人士采取部分好的国策,如作业分配,总计与通讯重叠以及平衡的通讯情势等。

  1. 可以预猜度法的实际运作时刻。

 

LogP模型的不足之处:

1.
对互连网中的通讯情势描述的不够深切。如重发音讯可能占满带宽、中间路由器缓存饱和等未加描述。

2.
LogP模子主要适用于新闻传递算法设计,对于共享存储格局,则不难地认为远地读操作相当于四遍音信传递,未考虑流水线预取技术、Cache引起的数码不同性以及Cache命中率对计量的震慑。

  1. 未考虑八线程技术的上下文开支。

4.
LogP模型假诺用点对点新闻路由器举行通讯,那增加了编程者考虑路由器上相关通讯操作的负担。

 

  • ### C3模型

  C3模子即使处理机不可能而且发送和拔取音讯,它对超步的属性分析分为两局地:计算单元CU,信赖于地点总结量;通讯单元COU,看重与处理机发送和接收数据的多少、新闻的推移及通讯引起的拥挤量。该模型考虑了三种路由(存储转载路由和虫蚀寻径路由)和三种发送/接收原语(阻塞和无阻塞)对COU的熏陶。

 

C3 模型的特征:

  1. 用Cl和Cp来度量网络的人山人海对算法质量的熏陶;
  2. 考虑了不一样路由和分裂发送或收取原语对通讯的熏陶;
  3. 不需求用户指定调度细节,就可以评估超步的日子复杂性;
  4. 类似于H-PRAM模型的层次结构,C3模子给编程者提供了K级路由算法的思绪,即系统被分成K级子系统,各级子系统的操作互相独立,用超步代替了H-PRAM中的Sub
    PRAM进行划分。

 

C3 模型的不足之处:

    1. Cl度量的前题假如为同样通讯对中的2个处理机要分别位居互联网对分后的分化子互连网内;
    2. 模型假如了互连网带宽等于处理机带宽,那影响了不易描述可扩展系统;
    3. 在K级算法中,处理机间顺序可以由八种排列,但C3模型不可能分别差异排列的难易程度。

 

  • ### BDM模型

1996年J.F.JaJa等人提议了一种块分布存储模型(BDM, Block Distributed
Model)。它是共享存储编程情势与基于新闻传递的遍布存储系统里头的大桥模型。首要有4个参数:

  1. P处理器个数。

2.τ处理机从发生访问请求到收获远程数据的最大延迟时间(包含准备呼吁时间、请求包在网络中路由的时日、目标处理机接收请求的时日以及将包中M个三番五次字重返给原处理机的光阴)。

  1. M局地存储器中连连的M个字。

4.σ甩卖机发送数据到网络或从互连网接收数据的光阴。

BDM模型的特性:

  1. 用M反映出空间局地性特点,提供了一种评价共享主存算法的特性方法,度量了因远程访问引起的拍卖间的通讯;
  2. BDM认同流水线技术。某个处理机的K次预取所需的光阴为τ+KMσ
    (否则为K(τ+Mσ))
  3. 可编程性好;
  4. 设想了共享主存中的存储竞争难点;
  5. 能够用来分析网络路由气象。

 

BDM模型的阙如:

  1. 以为发轫数据置于局存中,对于共享主存程序的编程者来说,须要分外增添数量移动操作;
  2. 未考虑网络中影响延迟的要素(如处理机的本地性、互连网重拥挤等);
  3. 未考虑系统开发。

  

网站地图xml地图