精华内容
下载资源
问答
  • 并行计算的四种模型
    千次阅读
    2022-03-26 10:17:06

    一、几种并发模型

    一般来说,模型是抽象出来具有某些普遍特征的单元。它可能是一个(组)公式,也可能是一个算法等等。目前比较常见的几个模型有如下几个:
    1、PRAM
    PRAM(Parallel Random Access Machine,随机存取并行机器)模型是一种抽象的并行计算模型,即共享存储的SIMD模型。其假定有一个无限容量大的共享存储器,具有N个(N可达无限)功能、架构相同的处理器,相关处理器随时可以通过共享存储单元相互交互数据。根据处理器对共享存储单元同时读、同时写的限制,PRAM模型可以分为下面几种:
    a、互斥读和互斥写(Exclusive-Read and Exclusive-Write)的PRAM模型,简称为EREW
    b、并发读但互斥写(Concurrent-Read and Exclusive-Write)的PRAM模型,简称为CREW
    c、互斥读和并发写(Exclusive-Read and Concurrent-Write)的PRAM模型,简称为ERCW
    d、并发读和并发写(Concurrent-Read and Concurrent-Write)的PRAM模型,简称为CRCW
    但同时写是有困难的,因此对CRCW模型进一步描述:
    a、所有处理器并发写相同的数,即公共(common)的PRAM-CRCW(CPRAM-CRCW)
    b、按优先级的处理器写,即优先(Priority)的PRAM-CRCW(PPRAM-CRCW)
    c、任意处理器自由写,即任意(Arbitrary)的PRAM-CRCW(APRAM-CRCW)
    d、向存储器中写入所有处理器写的数的和,即求和(Sum)的PRAM-CRCE,(SPRAM-CRCW)

    2、LogP
    LogP是面向高性能并行计算的模型,1993年D.Culer等人提出了点对点通信的多计算机模型,即充分利用分布式网络存储、多处理理器网络通信机制等,在屏蔽具体的网络结构和算法通过消息机制来实现的一种模型。
    LogP模型是一种分布存储的、点到点通信的多处理机模型,网络通信抽象为4个主要参数:
    a、L(Latency) 最大通信延迟,即源模块到目的模块传递消息(一个或几个字)通信所需要的时间上限
    b、o(overhead)通信开销,即处理机发送或接收消息的时间长度,在这段时间里处理不能执行其它操作
    c、g(gap)通信间隔,即处理机连续发送或接收消息时的最小时间间隔,此值的倒数即通信带宽
    d、P(Processor)处理机/存储器模块个数,其每个周期即为处理器的单位运行时间
    假设每个周期完成一次操作,L,o和g都可以表示成处理器周期的整数倍

    3、BSP
    BSP(Bulk Synchronous Parallel)模型最早由Leslie和Valiant 在 1990 年提出,它是一种异步MIMD-DM模型(DM: distributed memory,SM: shared memory),BSP模型支持消息传递系统,块内异步并行,块间显式同步,其基于master/worker同步(lock-step)执行, 数据从输入的队列中读取。BSP并行计算模型由下面4个参数描述:
    P:处理器的数量(带有存储器)
    s:处理器的运行速度
    g:每秒本地计算操作的数目/通信网络每秒传送的字节数,即选路器吞吐率,视为带宽因子 (time steps/packet)=1/bandwidth
    L:路障同步器,全局的同步时间开销,即全局同步之间的时间间隔 (Barrier synchronization time)
    BSP计算模型既是体系结构模型也是并行设计的方法。整体上是一个同步设计,同时具有水平和垂直两个方向的结构。并且,其引入了超步(superstep)概念,它和LogP在效率是等效的。

    二、特点和简要分析

    1、PRAM
    PRAM模型适合于并行算法的表达、分析和比较,使用简单,隐藏了很多关于并行计算机的底层细节(处理器间通信、存储系统管理和进程同步),略加设计和修改就可以应用在不同的并行计算平台上。此模型中,可灵活的按实际情况增加进程通信及同步相关设计。
    其也有如下不足:
    a、此模型使用一个存储容量较小的全局共享存储器,不适合于分布存储结构的MIMD机器
    b、此模型是同步的,即通过同步来实现的异步,不能反映现实中很多系统的异步性
    c、此模型假定要求太高(如对处理机间通信无延迟、无限带宽和无开销)这个不现实
    d、此模型假设处理机有限或无限,对并行任务的增大无开销
    e、引模型对锁线程技术和流水线预取技术未能描述,略显滞后

    2、LogP
    LogP模型相对PRAM模型来说更接近实际,对通信和信息交换方面的开销都进行了处理,特别是对多线程的应用更是相对合理。
    a、正如上面所说,对网络IO和处理机之间的瓶颈进行了说明。抓住了网络与处理机之间的性能瓶颈。真正通过异步操作实现处理机间的消息通信
    b、较好的适应了多线程和虚拟处理机(VP)技术
    c、消息延迟不确定,但延迟上限不超过L
    d、LogP模型可以更适用一些好的策略,如作业分配,计算与通信平等以及平衡的通信模式等
    e、算法实际运行时间可估算。
    此模型的不足之处在于对网络通信模式描述模糊,对流水线和缓存等没有考虑,同时多线程的操作带来Context切换的开销,编程的复杂度上升且需要对P2P路由器通信有了解。

    3、BSP
    a、 BSP模型将计算划分为一个一个的超步(superstep),有效避免死锁
    b、 它将处理器和路由器分开,强调了计算任务和通信任务的分开,而路由器仅仅完成点到点的消息传递,不提供组合、复制和广播等功能,这样做既掩盖具体的互连网络拓扑,又简化了通信协议
    c、 采用障碍同步的方式以硬件实现的全局同步是在可控的粗粒度级,从而提供了执行紧耦合同步式并行算法的有效方式,而程序员并无过分的负担(BSP model eliminates the need for programmers to manage memory, assign communication and perform low-level synchronization. Threads of the program are assigned (typically in a randomized way) by the machine to the processors)
    d、 在分析BSP模型的性能时,假定局部操作可以在一个时间步内完成,而在每一个超级步中,一个处理器至多发送或接收h条消息。假定s是传输建立时间,所以传送h条消息的时间为gh+s,如果 ,则L至少应该大于等于gh。很清楚,硬件可以将L设置尽量小,而软件可以设置L的上限。在实际使用中,g可以定义为每秒处理器所能完成的局部计算数目与每秒路由器所能传输的数据量之比。如果能够合适的平衡计算和通信,则BSP模型在可编程性方面具有主要的优点,而直接在BSP模型上执行算法,这个优点将随着g的增加而更加明显
    e、提供对PRAM模型所设计的算法,可以模拟一些PRAM的方法实现

    三、总结

    不同串行化的模型结构只有冯诺伊曼计算模型,并行计算的设计其实不少,除了上面的常见的,还有SEDA阶段式事件驱动架构和C^3模型等。但是其实哪种优劣还是得看应用场景和具体情况。倒是BSP的应用中,有Google的Pregel和大数据分析的Spark,更为程序员们知道。目标要宏大,但实现要聚焦,这才是学习的目的和行动的方式。
    在这里插入图片描述

    更多相关内容
  • 并行计算之C3模型

    2016-04-26 09:21:36
  • MapReduce是Google提出的分布式并行计算编程模型,用于大规模数据的并行处理。Ma-pReduce模型受函数式编程语言的启发,将大规模数据处理作业拆分成若干个可独立运行的Map任务,分配到不同的机器上去执行,生成某种格式的...
  • 并行计算的编程模型试读版
  • 基于MapReduce框架的集群系统,提出了1新 的计算模型用于大规模图形的3-clique计算,来实现图挖掘. 计算的基本步骤是:首先获取每个节点的第1跳信息,然 后是第2跳信息,最后得到所有基于该节点的3-clique. 该计算模型...
  • 云计算-一多agent并行计算模型及其应用研究.pdf
  • 云计算-一面向网格的并行计算模型及算法实现研究.pdf
  • 云计算-一改进的NHBL并行计算模型及其性能评测.pdf
  • 并行计算模型有哪些?

    万次阅读 多人点赞 2021-04-22 00:31:44
    并行计算模型通常指从并行算法的设计和分析出发,将各种并行计算机(至少是某一类并行计算机)的基本特征抽象出来,形成一个抽象的计算模型。 从更广的意义上说,并行计算模型为并行计算提供了硬件和软件界面,在该...

    写在前面

    本文隶属于专栏《100个问题搞定大数据理论体系》,该专栏为笔者原创,引用请注明来源,不足和错误之处请在评论区帮忙指出,谢谢!

    本专栏目录结构和文献引用请见100个问题搞定大数据理论体系

    解答

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

    在这里插入图片描述

    补充

    为什么需要并行计算模型?

    Spark、 Hadoop是迭代模式,只适合一般的计算,在机器学习等计算量非常大的领域,传统的迭代模型不再适用。并行计算模型就是为了解决一些特定场景下的计算量问题。

    BSP模型

    (Bulk Synchronous Parallel,整体同步并行计算模型)是一种并行计算模型,由英国计算机科学家 Viliant 在20世纪80年代提出。

    Google发布的一篇论文(Pregel:A System for Large-scale Graph Processing)使得这一概念被更多人所认识。

    和 Mapreduce-样, Google并没有开源 Pregel, Apache按 Pregel 的思想提供了类似的框架Hama。

    BSP模型基本原理

    BSP模型是一种异步MIMD-DM模型(DM-Distributed Memory,SM–Shared Memory), 其支持消息传递系统、块内异步并行、块间配式同步。

    该模型基于一个 Master协调,所有的 Worker 同步(lock-step)执行,数据从输入的队列中读取。

    BSP计算模型不仅是一种体系结构模型,也是设计并行程序的一种方法。

    BSP程序的设计准则是整体同步(Bulk Synchrony),其独特之处在于超步(Super Step)概念的引入。

    一个BSP程序同时具有水平和垂直两个方向的结构。从垂直上看,一个BSP程序由一系列串行的超步(Super Step)组成,如图所示,这种结构类似于一个串行程序结构。

    BSP超步

    从水平上看,在一个超步中,所有的进程并行执行局部计算。一个超步可分为三个阶段,如图所示。

    BSP超步三个阶段

    1. 本地计算阶段,每台处理器只对存储在本地内存中的数据进行本地计算。
    2. 全局通信阶段,对任何非本地数据进行操作。
    3. 栅栏同步阶段,等待所有通信行为结束。

    BSP并行计算模型可以用p、s、g、i4个参数进行描述

    1. p为处理器的数目(带有存储器)。
    2. s为处理器的计算速度。
    3. g为每秒本地计算操作的数目/通信网络每秒传送的字节数,称之为选路器昋吐率,视为带宽因子。
    4. i为全局的同步时间开销,称之为全局同步之间的时间间隔(Barrier Synchronization Time)

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

    BSP模型的特点

    1. BSP模型将计算划分为一个一个的超步(Super Step),有效避免了死锁。
    2. 它将处理器和路由器分开,路由器仅仅完成点到点的消息传递,不提供组合、复制和广播等功能,这样做既掩盖了具体的互连网络拓扑,又简化了通信协议。
    3. 障碍同步是以硬件实现的全局同步,是可控的粗粒度级的,从而提供了执行紧耦合同步式并行算法的有效方式,而程序员并无过多的负担。
    4. 在分析BSP模型的性能时,假定局部操作可以在一个时间步内完成,而在每一个超步中, 一台处理器最多发送或接收h条消息(称为h-relation)
    5. 为PRAM模型设计的算法都可以采用在每台BSP处理器上模拟一些PRAM处理器的方法来实现。

    BSP模型的评价

    1. 在并行计算时, Viliant试图为软件和硬件之间架起一座类似冯・诺伊曼机的桥梁,BSP模型可以起到这样的作用。正因如此,BSP模型也被称为桥模型。
    2. 一般而言,分布式存储的MIMD模型的可编程性比较差,但在BSP模型中,如果计算和通信可以适当平衡,则它在可编程性方面将呈现出更大的优势。
    3. 在BSP模型中直接实现了一些重要的算法(如矩阵乘、并行前序运算、FFT和排序等),均避免了自动存储管理的额外开销。
    4. BSP模型可以有效地在超立方体网络和光交叉开关互连技术上实现,显示出该模型与特定的技术实现无关,只需路由器具有一定的通信吞吐率。
    5. 在BSP模型中,“超步”的长度必须能够充分地适应任意的h-relation。
    6. 在BSP模型中,在“超步”开始发送的消息,即使网络延迟时间比“超步”的长度短,该消息也只能在下一个“超步”中使用
    7. BSP模型中的全局障碍同步假定是用特殊的硬件支持的,很多并行机中可能并没有相应的硬件。

    BSP模型的实现

    BSP计算框架有很多实现,最有名的是Google的大规模图计算框架Pregel,首次提出将BSP模型应用于图计算。

    Yahoo!贡献的 Apache Giraph专注于送代图计算(如 Pagerank、最短连接等),每个Job就是一个没有 Reducer过程的 Hadoop Job。

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

    PRAM模型

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

    PRAM模型的优点

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

    PRAM模型的缺点

    1. 模型中使用了一台全局共享存储器,且局存容量较小,不足以描述分布主存多处理器的性能瓶颈,而且共享单一存储器的假定,显然不适合分布存储结构的MIMD机器。
    2. PRAM模型是同步的,这就意味着所有的指令都按照锁步( Clock Step)的方式操作。用户虽然感觉不到同步的存在,但同步的存在的确很耗费时间,而且不能反映现实中很多系统的异步性。
    3. PRAM模型假设每台处理器可在单位时间内访问共享存储器的任一单元,因此要求处理器间通信无延迟、无限带宽和无开销。假定每台处理器均可以在单位时间内访问任何存储单元而略去了实际存在的、合理的细节,如资源竞争和有限带宽,这是不现实的。
    4. 未能描述多线程技术和流水线预取技术,而这两种技术又是当今并行体系结构应用最普遍的技术。

    LogP模型

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

    LogP模型的通信网络由4个主要参数来描述

    1. L(Latency):表示源处理器与目的处理器进行消息(一个或几个字)通信所需的等待或延退时间的上限,表示网络中消息的延迟。
    2. o(overhead):表示处理器准备发送或接收每条消息的时间开销(包括操作系统核心开销和网络软件开销),在这段时间内处理器不能执行其他操作。
    3. g(gap):表示一台处理器连续两次发送或接收消息时的最小时间间隔,其倒数即微处理器的通信带宽。
    4. P(Processor):处理器/存储器模块个数

    LogP模型的特点

    1. 抓住了网络与处理器之间的性能瓶颈。g反映了通信带宽,单位时间内最多有Lg个消息能进行处理器间传送。
    2. 处理器间异步工作,并通过处理器间的消息传送来完成同步。
    3. 对多线程技术有一定的反映。每台物理处理器可以模拟多台虚拟处理器(VP),当某台VP 有访问请求时,计算不会终止,但VP的数目受限于通信带宽和上下文交换的开销。VP受限于网络容量,最多有Lg台VP。
    4. 消息延迟不确定,但延迟不大于L。消息经历的等待时间是不可预测的,但在没有阻塞的情况下最大不超过L。
    5. LogP模型鼓励编程人员采用一些好的策略,如作业分配、计算与通信重叠及平衡的通信模式等。
    6. 可以预估算法的实际运行时间。

    LogP模型的不足

    1. 对网络中的通信模式描述得不够深入,如对重发消息可能占满带宽、中间路由器缓存饱和等未加描述
    2. LogP模型主要适用于消息传递算法设计,对于共享存储模式,则简单地认为异地读操作相当于两次消息传递,未考虑流水线预取技术、 Cache引起的数据不一致性及 Cache命中率对计算的影响。
    3. 未考虑多线程技术的上下文开销。
    4. LogP模型假设用点对点消息路由器进行通信,这增加了编程者考虑路由器上相关通信操作的负担。

    C3模型

    C3模型假定处理器不能同时发送和接收消息,它对超步的性能分析分为两部分:

    1. 计算单元(CU),依赖于本地计算量;
    2. 通信单元(COU),依赖于处理器发送和接收数据的多少、消息的延迟及通信引起的拥挤量。

    该模型考虑了两种路由(存储转发路由和虫蚀寻径路由)和两种发送接收原语(阻塞和无阻塞)对COU的影响

    C3模型的特点

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

    C3模型的不足

    1. C度量的前提为同一通信对中的两台处理器要分別位于对分网络的不同子网络内。
    2. 该模型假设网络带宽等于处理器带宽,从而影响了正确描述可扩展系统。
    3. 在K级算法中,处理器间的顺序可以有多种排列,但C3模型不能区分不同排列的难易程度。

    BDM模型

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

    其主要有4个参数。

    1. P:处理器个数。
    2. t:处理器从发出访问请求到得到远程数据的最大延迟时间,包括准备请求时间、请求包在网络中路由的时间、目的处理器接收请求的时间,以及将包中M个连续字返回给原处理器的时间。
    3. M:局部存储器中连续的M个字。
    4. 处理器发送数据到网络或从网络接收数据的时间。

    BDM模型的特点

    1. 用M反映出空间局部性特点,提供了一种评价共享主存算法的性能方法,度量了因远程访问引起的处理器间的通信。
    2. BDM认可流水线技术。某台处理器的K次预取所需的时间为+KMo(否则为K(r+Mo) 可编程性好。
    3. 考虑了共享主存中的存储竞争问题。
    4. 可以用来分析网络路由情况。

    BDM模型的不足

    1. 认为初始数据置于内部存储中,对于共享主存程序的编程者来说,需要额外增加数据移动操作
    2. 未考虑网络中影响延迟的因素,如处理器的本地性、网络重拥挤等。
    3. 未考虑系统开销。
    展开全文
  • _并行计算__并行计算_

    2021-09-30 17:24:44
    从当今多核微处理器的发展趋势出发,介绍适用于多核微处理器的细粒度并行编程模型CUDA,以及其适用于“并行计算”课程教学的一系列优势
  • 并行计算之C3模型ppt

    2016-04-26 09:31:32
    C3模型是并行计算模型中的一,这个ppt是我们总结出来的,对C3模型有详细的讲解
  • SMP上的OpenMP / MPI混合并行计算模型设计
  • 云计算-异构环境中并行计算模型与任务调度的研究.pdf
  • 为解决串行时域多分辨率(MRTD)散射模型运行时间长和内存消耗大的问题, 基于消息传递接口(MPI)技术设计了一非球形气溶胶散射并行计算模型。介绍了MRTD散射模型的基本框架和2并行数据通信方案, 并基于MPI重复非...
  • 云计算-二维水动力学模型并行计算研究.pdf
  • 多核处理器机群Memory层次化并行计算模型研究.pdf
  • 基于GPU的并行计算性能分析模型
  • 基于GPU的并行计算性能分析模型.pdf
  • 基于MapReduce框架的集群系统,提出了1新的计算模型用于大规模图形的3-clique计算,来实现图挖掘. 计算的基本步骤是:首先获取每个节点的第1跳信息,然后是第2跳信息,最后得到所有基于该节点的3-clique. 该计算...
  • 并行计算导论

    2017-07-06 20:47:28
    并行计算导论》(原书第2版)尽可能采用与底层平台无关的体系结构并且针对抽象模型来设计处落地。书中选择MPI、POSIX线程和OpenMP作为编程模型,并在不同例子中反映了并行计算的不断变化的应用组合。
  • 研究了CMAQ大气模型在64位Linux操作系统上不同CPU核心数目并行计算模拟耗时以及结果的差异情况。研究结果表明,并行计算能大幅缩短CMAQ模拟耗时,以16个CPU核心并行处理为性价比最佳值;此时连续模拟中国区域37天...
  • 装饰并发(Decorated Concurrency)一简化的Python并行计算模型。 DECO自动并行化Python程序,并且需要对现有串行程序进行最少的修改。 使用pip安装:pip install deco装饰并发简化的Python并行计算模型。 DECO...
  • 云计算-模型燃烧室燃烧流场并行计算.pdf
  • 基于MapReduce和GPU双重并行计算的云计算模型.pdf
  • 并行计算与MPI.pdf

    2019-06-01 16:44:36
    关于MPI、并行计算的总结对比,目录如下: 1. 并行计算 1.1. 相关背景 1.2. 什么是并行计算 1.3. 主要目的 1.4. 并行计算与分布式计算 1.5. 并行的基本条件 1.6. 主要的并行系统 1.6.1. 共享内存模型 1.6.2. 消息...
  • 云计算-面向大数据处理的并行计算模型及性能优化.pdf
  • 云计算-基于DFS的并行粒度计算模型及其应用.pdf
  • 文章主要介绍了一基于并行计算机架构的OS 模型,其中主要包括并行计算机架构模式、并行计算机OS模型并行计算机OS的QOS模型等几个方面。并行计算机的性能优越,数据计算和数据处理能力强大,在国民经济社会实践中...
  • 云计算-交通仿真系统的并行计算、智能优化和混杂模型研究.pdf
  • #资源达人分享计划#

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 211,314
精华内容 84,525
热门标签
关键字:

并行计算的四种模型