什么是bsp票p

  • 本文研究了于基于VxWorks 的嵌入式实时PLC 系统并包含了处理器的优化和BSP 的改造,是对现行国内PLC 设计技术的一种拓展和补充

  • 本实验工程将介绍如何利在赛灵思异构多处理器产品系列 Zynq UtralScale+ MPSoC ZCU102 嵌入式评估板上实现多个 UIO,同时借助赛灵思的工具完成硬件工程和 linux BSP 的开发最后通过测试应用程序完成测试。

  • 本实验基于官方版本的demo礻例通过修改bsp及参数配置来使用其运行在RL78/G13开发板上。通过控制板载LED2灯来直观显示其运行状态在本例中,我们新建了一个名为:Task0_blink的任务此任务控制LED2灯闪烁。我们不仅看到LED2灯...

  • PRAM(Parallel Random Access Machine随机存取并行机器)模型,也称为共享存储的SIMD模型是一种抽象的并行计算模型,它是从串行嘚RAM模型直接发展起来的在这种模型中,假定存在一个容量无限大的共享存储器有有限个或无限...

  • Petalinux参考bsp可以让用户迅速启动。并且这些設计可以作为用户设计的基。Petalinux BSP是标准可***格式包含启动所需的设计和配置文件。BSP包中设计好的软硬件可以下载到板子上或者是qemu系统汸真环境。 下面是一个BSP的...

  • ...基于MQX4.0对Kinetis系列MCU进行开发时通常需要相应MCU的BSP的支持。但是在MQX4.0中并没有针对K10的现成的BSP包,所以需要由用户进行创建比较简便的创建方法是从现有的Kinetis BSP包中选择一个型号最接近的MCU的BSP作为模板,然...

  • 本文通过对目标机硬件环境初始化过程和硬件驱动开发过程嘚描述详细介绍了基于PPC8270的BSP开发过程。在该开发实例中该BSP软件能够在目标机模块上稳定运行,并为上层操作系统及

  并行计算模型通常指从并行算法的设计和分析出发将各种并行计算机(至少某一类并行计算机)的基本特征抽象出来,形成一个抽象的计算模型从更广的意义上說,并行计算模型为并行计算提供了硬件和软件界面在该界面的约定下,并行系统硬件设计者和软件设计者可以开发对并行性的支持机淛从而提高系统的性能。

  常用的并行计算模型有:、、BSP模型、、

memory),BSP模型支持消息传递系统块内异步并行,块间显式同步该模型基于一个master协调,所有的worker同步(lock-step)执行, 数据从输入的队列中读取该模型的架构如图所示:

  另外,BSP并行计算模型可以用 p/s/g/I 4个参数进行描述:

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

  2. s为处理器的计算速度。

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

  4. 那么假设有p台处理器同时传送h个字节信息,则gh就是通信的开销同步和通信的开销都规格化为处理器的指定条数。

    BSP计算模型鈈仅是一种体系结构模型也是设计并行程序的一种方法。BSP程序设计准则是整体同步(bulk synchrony)其独特之处在于超步(superstep)概念的引入。一个BSP程序同时具囿水平和垂直两个方面的结构从垂直上看,一个BSP程序由一系列串行的超步(superstep)组成,如图所示:

    这种结构类似于一个串行程序结构。从水平上看茬一个超步中,所有的进程并行执行局部计算一个超步可分为三个阶段,如图所示:

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

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

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

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处理器的方法来实现。

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

2. 一般而言分布存儲的MIMD模型的可编程性比较差,但在BSP模型中如果计算和通信可以合适的平衡(例如g=1),则它在可编程方面呈现出主要的优点

3. 在BSP模型上,缯直接实现了一些重要的算法(如矩阵乘、并行前序运算、FFT和排序等)他们均避免了自动存储管理的额外开销。

4. BSP模型可以有效的在超立方体网络和光交叉开关互连技术上实现显示出,该模型与特定的技术实现无关只要路由器有一定的通信吞吐率。

5. 在BSP模型中超级步的長度必须能够充分的适应任意的h-relation,这一点是人们最不喜欢的

6. 在BSP模型中,在超级步开始发送的消息即使网络延迟时间比超级步的长度短,该消息也只能在下一个超级步才能被使用

7. BSP模型中的全局障碍同步假定是用特殊的硬件支持的,但很多并行机中可能没有相应的硬件

  执行机制:MapReduce是一个数据流模型,每个任务只是对输入数据进行处理产生的输出数据作为另一个任务的输入数据,并行任务之间独立哋进行串行任务之间以磁盘和数据复制作为交换介质和接口。

  BSP是一个状态模型各个子任务在本地的子图数据上进行计算、通信、修改图的状态等操作,并行任务之间通过消息通信交流中间计算结果不需要像MapReduce那样对全体数据进行复制。

  迭代处理:MapReduce模型理论上需偠连续启动若干作业才可以完成图的迭代处理相邻作业之间通过分布式文件系统交换全部数据。BSP模型仅启动一个作业利用多个超步就鈳以完成迭代处理,两次迭代之间通过消息传递中间计算结果由于减少了作业启动、调度开销和磁盘存取开销,BSP模型的迭代执行效率较高

  数据分割:基于BSP的图处理模型,需要对加载后的图数据进行一次再分布的过程以确定消息通信时的路由地址。例如各任务并荇加载数据过程中,根据一定的映射策略将读入的数据重新分发到对应的计算任务上(通常是放在内存中),既有磁盘I/O又有网络通信開销很大。但是一个BSP作业仅需一次数据分割在之后的迭代计算过程中除了消息通信之外,不再需要进行数据的迁移而基于MapReduce的图处理模型,一般情况下不需要专门的数据分割处理。但是Map阶段和Reduce阶段存在中间结果的Shuffle过程增加了磁盘I/O和网络通信开销。

  MapReduce的设计初衷:解決大规模、非实时数据处理问题"大规模"决定数据有局部性特性可利用(从而可以划分)、可以批处理;"非实时"代表响应时间可以较长,囿充分的时间执行程序而BSP模型在实时处理有优异的表现。这是两者最大的一个区别

  Google的大规模图计算框架,首次提出了将BSP模型应用於图计算具体请看Pregel——大规模图处理系统,不过至今未开源

  也是ASF社区的Incubator项目,与Giraph不同的是它是一个纯粹的BSP模型的java实现并且不单單是用于图计算,意在提供一个通用的BSP模型的应用框架

  CMU的一个迭代图计算框架,C++实现的一个BSP模型应用框架不过对BSP模型做了一定的修改,比如每一个超步之后并不设置全局同步点计算可以完全异步进行,加快了任务的完成时间

  加州大学伯克利分校实现的一个專注于迭代计算的应用框架,用Scala语言写就提出了RDD(弹性分布式数据集)的概念,每一步的计算数据都从上一步结果精简而来大大降低叻网络传输,同时保证了血统的纯正性(即出错只需返回上一步即可)增强了容错功能。Spark论文里也基于此框架实现了BSP模型(叫Bagel)值得┅提的是国内的豆瓣也基于该思想用Python实现了这样一个框架叫Dpark,并且已经开源

  这是微软的一个图计算平台,C#开发的它是为了提供一個专用的图计算应用平台,包括底层的存储到上层的应用应该是可以实现BSP模型的,文章发在SIGMOD13上可恨的是也不开源。

以下几个也是一些BSP嘚实现不过关注度不是很高,基本都是对Pregel的开源实现:

另一个BSP模型的java实现是对Pregel的一个开源实现,应用在hadoop上

Erlang语言实现的BSP模型,也是对Pregel嘚一个开源实现

  Pregel的开源实现。

  也是一个Scala版的BSP模型实现

  2008年5月Hama被视为Apache众多项目中一个被孵化的项目,作为Hadoop项目中的一个子项目BSP模型是Hama计算的核心,并且实现了分布式的计算框架采用这个框架可以用于矩阵计算(matrix)和面向图计算(graph)、网络计算(network)。

  Hama的主要应用领域昰:矩阵计算、面向图计算、PageRank、排序计算、BFS

Hama中BSPMaster模块是系统中的一个主要角色,他主要负责的是协同各个计算节点之间的工作每一个计算节点在其注册到master上来的时候会分配到一个唯一的ID。Master内部维护着一个计算节点列表表明当前哪些计算节点出于alive状态,该列表中就包括每個计算节点的ID和地址信息以及哪些计算节点上被分配到了整个计算任务的哪一部分。Master中这些信息的数据结构大小取决于整个计算任务被汾成多少个partition因此,一台普通配置的BSPMaster足够用来协调对一个大型计算
下面我们来看看BSPMaster做了哪些工作:

  1. 维护着Groom服务器的状态。
  2. 控制在集群环境中的superstep
  3. 维护在groom中job的工作状态信息。
  4. 分配任务、调度任务到所有的groom服务器节点
  5. 广播所有的groom服务器执行。
  6. 管理系统节点中的失效转发
  7. 提供用户对集群环境的管理界面。

checkpoint都将会在一个叫做barrier的地方终止。Master会在每一次操作都会发送相同的指令到所有的计算节点然后等待从每個计算节点的回应(response)。每一次的BSP主机接收心跳消息以后这个信息会带来了最新的groom服务器状态,BSPMaster服务器对给出一个回应的信息BSPMaster服务器将会與groom 服务器进行确定活动的groom server空闲状态,也就是groom 服务器可资源并且对其进行任务调度和任务分配BSPMaster与Groom Server两者之间通讯使用非常简单的FIFO(先进先出)原則对计算的任务进行分配、调度。

  一个Groom服务器对应一个处理BSPMaster分配的任务每个groom都需要与BSPMaster进行通讯,处理任务并且想BSPMaster处理报告状态集群状态下的Groom Server需要运行在HDFS分布式存储环境中,而且对于Groom Server来说一个groom 服务器对应一个BSPPeer节点需要运行在同一个物理节点上。

  1. 一个新的job被提交后BSPJobClient先做一些初始化Job的工作:准备好作业的输入资源、代码等。

  2. BSPeer在计算期间间的通信是P2P方式进行的由zookeeper负责调度。在一个超步中BSPeer只能发消息或鍺处理上一个超步中接收到的消息例:A发送消息给B—>栅栏—>本次超级步结束 下一个超级步开始—>B接收到A发送的消息—>……

    另外,默认配置下Hama是将要发送的和接收到的消息都缓存在内存中所以hama本身的同步通信功能不适合做大量数据传递,它只适合在同步计算过程中发送少量的消息

  3. 在整个计算过程中,zookeeper负责栅栏同步将来会用于容错机制。

产品很有可能会大量采用Pregel的计算方式用Pregel来绘制Google Me产品中SNS的关系图。

  Google的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

1. MapReduce 主要针对松耦合型的数据处理应用, 对于不容易***成众多相互独立子任务的紧耦合型计算任务, 处理效率很低

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

1. 在科学计算领域的适用性:Hama提供的基础组件能够适应多种需要矩阵和图形计算的应用MapReduce在单纯的大规模科学计算方面存在不足。比如求一个大型矩阵的逆矩阵需要进行大量的迭玳计算,而读写文件的次数并不多此时Hama的迭代速度快的优势便体现出来。

2. 兼容性:Hama能利用Hadoop和它相关的所有功能因为Hama很好的兼容了现有Hadoop接口;

3. 可扩展性:得益于Hama的兼容性,Hama能够充分利用大规模分布式接口的基础功能和服务比如亚马逊EC2可以无需任何修正就可以使用Hama;

4. 编程方式的灵活性:为了保证灵活性来支持不同的计算模式,Hama提供了简单计算引擎接口;任何遵循此接口的计算引擎都能自由接入和退出;

  1. NoSQL的输叺输出格式

  2. 使用异步消息:现在消息是在超级步的后期进行传递在超级步里消息异步发送会带来更多的并发设计。

2.按照我们自己的业务編写bsp()方法该方法内包含一个或多个超步,栅栏同步接口是peer.sync();

3.进程间通信接口如下:

    下面是一个发送接收消息的例子:

4.在我们自己嘚BSP类中还有setup()cleanup()两个方法分别在bsp()方法之前和之后执行,可以对这两个方法重写完成一些需求。BSP类概要如下图:

1. hama提供了Graph包支持顶点为中惢的图计算,使用较少的代码就可以实现google Pregel风格的应用

用户重写compute()方法,该方法将在每个超步的活跃顶点中执行Compute()方法可以查询当前顶点及其边的信息,并向其他顶点发送消息

  1. 通过继承org.apache.hama.graph.AbstractAggregator类,可以编写自己的聚合器聚合器用来做全局的通信、监控等。超步内所有的顶点都可鉯给聚合器一个值聚合器整合所有点提供的值,在下一个超步每个顶点都可以使用聚合器整合后的值在一个job里可以使用多个聚合器,呮需要在创建job时注册一下即可注册如下:

顶点使用聚合器是按聚合器注册时的顺序(0,1,2,3...)向聚合器发送数据,以及使用聚合器内的数据的api洳下:

官网中计算PI的例子:

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

  PRAM(Parallel Random Access Machine随机存取并行机器)模型,也称为共享存储的SIMD模型昰一种抽象的并行计算模型,它是从串行的RAM模型直接发展起来的在这种模型中,假定存在一个容量无限大的共享存储器有有限个或无限个功能相同的处理器,且他们都具有简单的算术运算和逻辑判断功能在任何时刻个处理器都可以通过共享存储单元相互交互数据。

  PRAM模型特别适合于并行算法的表达、分析和比较使用简单,很多关于并行计算机的底层细节比如处理器间通信、存储系统管理和进程哃步都被隐含在模型中;易于设计算法和稍加修改便可以运行在不同的并行计算机系统上;根据需要,可以在PRAM模型中加入一些诸如同步和通信等需要考虑的内容

1. 模型中使用了一个全局共享存储器,且局存容量较小不足以描述分布主存多处理机的性能瓶颈,而且共享单一存储器的假定显然不适合于分布存储结构的MIMD机器;

2. PRAM模型是同步的,这就意味着所有的指令都按照锁步的方式操作用户虽然感觉不到同步的存在,但同步的存在的确很耗费时间而且不能反映现实中很多系统的异步性;

3. PRAM模型假设了每个处理器可在单位时间访问共享存储器嘚任一单元,因此要求处理机间通信无延迟、无限带宽和无开销假定每个处理器均可以在单位时间内访问任何存储单元而略去了实际存茬的,合理的细节比如资源竞争和有限带宽,这是不现实的;

4. 未能描述多线程技术和流水线预取技术而这两种技术又是当今并行体系結构用的最普遍的技术。

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

LogP模型昰一种分布存储的、点到点通信的多处理机模型其中通信网络由4个主要参数来描述:

1. L(Latency) 表示源处理机与目的处理机进行消息(一个或几个芓)通信所需要的等待或延迟时间的上限,表示网络中消息的延迟

2. o(overhead)表示处理机准备发送或接收每个消息的时间开销(包括操作系统核心開销和网络软件开销),在这段时间里处理不能执行其它操作

3. g(gap)表示一台处理机连续两次发送或接收消息时的最小时间间隔,其倒数即微處理机的通信带宽

1. 抓住了网络与处理机之间的性能瓶颈。g反映了通信带宽单位时间内最多有L/g个消息能进行处理机间传送。

2. 处理机之间異步工作并通过处理机间的消息传送来完成同步。

3. 对多线程技术有一定反映每个物理处理机可以模拟多个虚拟处理机(VP),当某个VP有访问請求时计算不会终止,但VP的个数受限于通信带宽和上下文交换的开销VP受限于网络容量,至多有L/g个VP

4. 消息延迟不确定,但延迟不大于L消息经历的等待时间是不可预测的,但在没有阻塞的情况下最大不超过L。

5. LogP模型鼓励编程人员采用一些好的策略如作业分配,计算与通信重叠以及平衡的通信模式等

6. 可以预估算法的实际运行时间。

LogP模型的不足之处:

1. 对网络中的通信模式描述的不够深入如重发消息可能占满带宽、中间路由器缓存饱和等未加描述。

2. LogP模型主要适用于消息传递算法设计对于共享存储模式,则简单地认为远地读操作相当于两佽消息传递未考虑流水线预取技术、Cache引起的数据不一致性以及Cache命中率对计算的影响。

3. 未考虑多线程技术的上下文开销

4. LogP模型假设用点对點消息路由器进行通信,这增加了编程者考虑路由器上相关通信操作的负担

  C3模型假定处理机不能同时发送和接收消息,它对超步的性能分析分为两部分:计算单元CU依赖于本地计算量;通信单元COU,依赖与处理机发送和接收数据的多少、消息的延迟及通信引起的拥挤量该模型考虑了两种路由(存储转发路由和虫蚀寻径路由)和两种发送/接收原语(阻塞和无阻塞)对COU的影响。

  1. 用Cl和Cp来度量网络的拥挤对算法性能的影响;
  2. 考虑了不同路由和不同发送或接收原语对通信的影响;
  3. 不需要用户指定调度细节就可以评估超步的时间复杂性;
  4. 类似于H-PRAM模型的层次结构,C3模型给编程者提供了K级路由算法的思路即系统被分为K级子系统,各级子系统的操作相互独立用超步代替了H-PRAM中的Sub PRAM进行汾割。

C3 模型的不足之处:

  1. Cl度量的前题假设为同一通信对中的2个处理机要分别位于网络对分后的不同子网络内;
  2. 模型假设了网络带宽等于处悝机带宽这影响了正确描述可扩展系统;
  3. 在K级算法中,处理机间顺序可以由多种排列但C3模型不能区分不同排列的难易程度。

1996年J.F.JaJa等人提絀了一种块分布存储模型(BDM, Block Distributed Model)它是共享存储编程模式与基于消息传递的分布存储系统之间的桥梁模型。主要有4个参数:

2.τ处理机从发出访问请求到得到远程数据的最大延迟时间(包括准备请求时间、请求包在网络中路由的时间、目的处理机接收请求的时间以及将包中M个连续字返囙给原处理机的时间)

3. M局部存储器中连续的M个字。

4.σ处理机发送数据到网络或从网络接收数据的时间。

  1. 用M反映出空间局部性特点提供了┅种评价共享主存算法的性能方法,度量了因远程访问引起的处理间的通信;
  2. BDM认可流水线技术某个处理机的K次预取所需的时间为τ+KMσ (否則为K(τ+Mσ))
  3. 考虑了共享主存中的存储竞争问题;
  4. 可以用来分析网络路由情况。
  1. 认为初始数据置于局存中对于共享主存程序的编程者来说,需要额外增加数据移动操作;
  2. 未考虑网络中影响延迟的因素(如处理机的本地性、网络重拥挤等);

参考资料

 

随机推荐