精华内容
下载资源
问答
  • 并行算法的基本设计策略
    千次阅读
    2020-06-18 16:14:36

    并行算法的设计技术

    目前普遍使用的并行算法的设计技术:
    1).流水线技术
    将任务分割成许多子任务,每个处理器完成其中一个,且第一个处理器完成第一个子任务后,第二个处理器可以开始完成第二个子任务…
    2).分治策略
    将原问题分成若干个特征相同的子问题,分别处理。(类似超线程技术)
    常见的分治策略:任务分割;数据分割
    3).平衡树方法
    将输入元素作为叶子节点构造二叉平衡树。
    4).倍增技术(指针跳跃技术)
    适合处理链表、有向图等数据结构;经常应用于通信系统中。
    5).加速级联策略
    将最优算法(计算速度慢)和最快算法(不是最优)级联起来。

    并行程序开发

    一个软件开发环境主要由硬件平台、操作系统、支撑语言、软件开发工具、应用软件包等组成。并行程序开发主要在于并行程序的设计、调试、维护和监控。

    一、并行程序开发环境

    现在研究重点是扩充现有的编译系统的并行语言功能,主要为:
    数据级并行(利用Fortran等开发);
    任务级并行(利用MPI、Linda等开发)

    二、并行语言和消息传递环境

    现在大多并行开发语言为Fortran、Pascal和C语言。并行环境常用的有PVM(Parallel Virtual Machine并行虚拟机)、MPI(Message Passing Interface 消息传递接口)和Express

    三、并行程序设计

    并行程序的设计有多种方式,主要分为:
    共享变量方法;消息传递方法;数据并行程序设计;面向对象的并行程序设计;函数程序设计方法;逻辑程序设计方法。
    选择并实现一种并行编程方法前,需要重点考虑:成熟性、易编程性、灵活性、效率、可移植性和成本。
    成熟性:主要指编译器和消息传递器的成熟性,有时也考虑开发工具的支持水平和完善程度。
    易编程性:编程方法容易实现并容易产生维护代码。
    效率:保持编译器和运行系统操作所有的进程通信和同步。

    四、并行编程技术遇到的挑战

    1.确定性:并行应用普遍会产生不可预知的结果,这类问题往往很难发现并有效修复。这就需要为并行编程提供一个可靠的、可预知的环境。
    2.问题划分:不同的处理机有时需要运行不同的程序,如何对个各个处理机进行任务划分。
    3.负载平衡:任务的分配可以是静态的,也可以是动态的,如何保证各个计算节点具有相当的工作量。
    4.数据的分配和收集:编程时必须考虑数据的分配(初始数据和计算环节中的过程数据)以及回收(计算结果的返回)。
    5.性能调整:未达到希望的效率是,必须对程序进行调整。
    6.执行环境:一般情况下,并行程序要适应多种并行计算环境。
    7.开销:并行程序需要哪些额外开销,如通信开销和程序管理开销等。

    更多相关内容
  • MPI 第五章 并行算法的一般设计策略 详细的查阅了有关资料,并自己做了一个易懂的ppt
  • 第二篇包括并行算法的一般设计策略基本设计技术和一般设计过程;第三篇包括矩阵运算、稠密与稀疏线性方程组的求解和快速傅里叶变换;第四篇包括并行程序设计基础、共享存储与分布存储系统 并行编程以及并行程序...
  • 并行算法设计基础

    千次阅读 2019-07-05 22:31:56
    并行算法的定义和分类 并行算法:一些可同时执行的诸进程的集合,这些进程互相作用和协调动作从而达到给定问题的求解。 并行算法分类 数值计算与非数值计算 同步算法和异步算法 分布算法 确定算法和随机算法 ...

     

    并行算法的定义和分类

    • 并行算法:一些可同时执行的诸进程的集合,这些进程互相作用和协调动作从而达到给定问题的求解。

    并行算法分类

    • 数值计算与非数值计算
    • 同步算法和异步算法
    • 分布算法
    • 确定算法和随机算法

    并行算法的表达

    描述语言

    • 可以使用类Algol、类Pascal等。
    • 在描述语言中引入并行语句。

    并行算法的复杂性度量

    串行算法的复杂性度量

    • 最坏情况下的复杂度(Worst-CASE Complexity)
    • 期望复杂度(Expected Complexity)

    并行算法的复杂性度量

    • 运行时间t(n):包含计算时间和通信时间,分别用计算时间步和选路时间步作单位。n为问题实例的输入规模。
    • 处理器数p(n)
    • 并行算法成本c(n):c(n)=t(n)p(n)
    • 总运算量W(n):并行算法求解问题时所完成的总的操作步数。

    Brent定理

      令W(n)是某并行算法A在运行时间T(n)内所执行的运算量,则A使用p台处理器可在t(n)=O(W(n)/p+T(n))时间内执行完毕。

    • W(n)和c(n)密切相关
    • P=O(W(n)/T(n))时,W(n)和c(n)两者是渐进一致的
    • 对于任意的p,c(n)>W(n)

    并行算法中的同步和通讯

    同步

    • 同步是在时间上强使各执行进程在某一点必须互相等待
    • 可用软件、硬件和固件的方法来实现

    通讯

    • 共享存储多处理器使用:global read(X,Y)和global write(X,Y)
    • 分布存储多计算机使用:send(X,i)和receive(Y,j)

    并行计算模型

    PRAM模型

    PRAM(Parallel Random Access Machine)模型是多指令流多数据流(MIMD)并行机中的一种具有共享存储的模型。

    基本概念

    • 由Fortune和Wyllie于1978年提出,又称SIMD-SM模型。有一个集中的共享存储器和一个指令控制器,通过SM(流多处理器)的R/W交换数据,隐式同步计算。

    结构图

    分类

    (1)PRAM-CRCW并发度并发写

    • CPRAM-CRCW(Common PRAM-CRCW):仅允许写入相同数据
    • PPRAM-CRCW(Priority PRAM-CRCW):仅允许优先级最高的处理器写入
    • APRAM-CRCW(Arbitrary PRAM-CRCW):允许任意处理器自由写入

    (2)PRAM-CREW并发读互斥写

    (3)PRAM-EREW互斥读互斥写

    计算能力比较

    • PRAM-CRCW是最强的计算模型,PRAM-EREW可logp倍模拟PRAM-CREW和PRAM-CRCW

    优缺点

    •  适合并行算法表示和复杂性分析,易于使用,隐藏了并行机的通讯、同步等细节
    • 不适合MIMD并行机,忽略了SM的竞争、通讯延迟等因素。

    异步APRAM模型

    基本概念

    • 又称分相(Phase)PRAM或MIMD-SM。每个处理器有其局部存储器、局部时钟、局部程序;无全局时钟,各处理器异步执行;处理器通过SM进行通讯;处理器间依赖关系,需在并行程序中显式地加入同步路障。

    指令类型

    1. 全局读
    2. 全局写
    3. 局部操作
    4. 同步

    计算过程

    由同步障分开全局相组成

    计算时间

    • 设局部操作位单位时间;全局读/写平均时间为d,d随着处理器数目的增加而增加;同步路障时间为B=B(p)非降函数。
    • 满足关系2≤d≤B≤p;B=B(n)=O(dlogp)或O(dlogp/logd)令tph为全局相内各处理器执行时间最长者,则APRAM上的计算时间为:T=∑tph+B×同步障次数

    优缺点

    • 易编程和分析算法的复杂度。
    • 但与现实相差较远,其上并行算法非常有限,也不适合MIMD-DM模型。

    BSP模型

    基本概念

      由Valiant(1990)提出的,“块”同步模型,是一种异步MIMD-DM模型,支持消息传递系统,块内异步并行,块间显式同步。

    模型参数

    • p:处理器数(带有存储器)
    • l:同步障时间(Barrier synchronization time)
    • g:带宽因子(time steps/packet)=1/bandwidth

    计算过程

      由若干超级步组成,每个超级步计算模式为下图:

    优缺点

    • 强调了计算和通讯的分离,提供了一个编程环境,易于程序复杂性分析。
    • 但是需要显式同步机制,限制至多h条消息的传递等。

    logP模型

    基本概念

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

    模型参数

    • l:network latency
    • o:communication overhead
    • g:gap=1/bandwidth
    • P:#processors

    注:l和g反映了通讯网络的容量

    优缺点

    • 捕捉了MPC的通讯瓶颈,隐藏了并行机的网络拓扑、路由、协议,可以应用到共享存储、消息传递、数据并行的编程模型中。
    • 但难以进行算法描述、设计和分析。

    BSP vs. logP

    • BSP→logP:BSP块同步→BSP子集同步→BSP进程对同步=logP
    • BSP可以常数因子模拟logP,logP可以对数因子模拟BSP
    • BSP=logP+Barriers-Overhead
    • BSP提供了更方便的程设环境,logP更好地利用了机器资源
    • BSP似乎更简单、方便和符合结构化编程

    并行算法的一般设计方法

    串行算法的直接并行化

    算法设计方法描述

    方法描述

    • 发掘和利用现有串行算法中的并行性,直接将串行算法改造为并行算法。

    评注

    • 由串行算法直接并行化的方法是并行算法设计的最常用方法之一
    • 不是所有的串行算法都可以直接并行化的
    • 一个好的串行算法并不能并行化为一个好的并行算法
    • 许多数值串行算法可以并行化为有效的数值并行算法

    例:快排序算法的并行化

    算法:PRAM-CRCW上的快排序二叉树构造算法

    输入:序列(A1,...,An)和n个处理器

    输出:供排序用的一颗二叉排序数

    从问题描述开始设计并行算法

    方法描述

    • 从问题本身描述出发,不考虑相应的串行算法,设计一个全新的并行算法。

    评注

    • 挖掘问题的固有特性与并行的关系
    • 设计全新的并行算法是一个挑战性和创造性的工作
    • 利用串的周期性的PRAM-CRCW算法是一个很好的范例

    借用已有的算法求解新问题

    方法描述

    • 找出求解问题和某个已解决问题之间的联系
    • 改造或利用已知算法应用到求解问题上

    评注

    • 这是一项创造性的工作
    • 使用矩阵乘法算法求解所有点对间最短路径是一个很好的范例

    利用矩阵乘法求所有点对间最短路径

    计算原理

    并行算法的基本设计技术

    划分设计技术

    • 均匀划分技术
    • 方根划分技术
    • 对数划分技术
    • 功能划分技术

    分治设计技术

    并行分治设计步骤

    • 将输入划分成若干个规模相等的子问题
    • 同时(并行地)递归求解这些子问题
    • 并行地归并子问题的解,直至得到原问题的解

    双调归并网络

    平衡数设计技术

    设计思想

    • 以树的叶节点为输入,中间节点为处理节点,由叶向根或由根向叶逐层进行并行处理。

    倍增设计技术

    设计思想

    • 又称指针跳跃(pointer jumping)技术,特别适合于处理链表或有向树之类的数据结构
    • 当递归调用时,所要处理数据之间的距离逐步加倍,经过k步后即可完成距离为2k的所有数据的计算

    流水线设计技术

    设计思想

    • 将算法流程划分成p个前后衔接的任务片段,每个任务片段的输出作为下一个任务片段的输入
    • 所有任务片段按同样的速率产生出结果

    评注

    • 流水线技术是一种广泛应用在并行处理中的技术
    • 脉动算法(Systolic algorithm)是其中一种流水线技术

    并行算法的一般设计过程

    PCAM设计方法学

    设计并行算法的四个阶段:

    • 划分(Partitioning):分解成小的任务,开拓并发性
    • 通讯(Communication):确定诸任务间的数据交换,监测划分的合理性
    • 组合(Agglomeration):依据任务的局部性,组合成更大的任务
    • 映射(Mapping):将每个任务分配到处理器上,提高算法的性能

    PCAM设计过程

    划分

    划分的方法描述

    • 充分开拓算法的并发性和可扩展性
    • 先进行数据分解(称域分解),再进行计算功能的分解(称功能分解)
    • 使数据集和计算集互不相交
    • 划分阶段忽略处理器数目和目标机器的体系结构
    • 能分为两类划分:①域分解(domain decomposition);②功能分解(functional decomposition)

    域分解

    • 划分的对象是数据,可以是算法的输入数据、中间处理数据和输出数据
    • 将数据分解成大致相等的小数据片
    • 划分时考虑数据上的相应操作
    • 如果一个任务需要别的任务中的数据,则会产生任务间的通讯

    功能分解

    • 划分的对象是计算,将计算划分为不同的任务,其出发点不同于域分解
    • 划分后,研究不同任务所需的数据。如果这些数据不相交的,则划分是成功的;如果数据有相当的重叠,意味着要重新进行域分解和功能分解
    • 功能分解是一种更深层次的分解

    划分依据

    • 划分是否具有灵活性?
    • 划分是否避免了冗余计算和存储?
    • 划分任务尺寸是否大致相当?
    • 任务数与问题尺寸是否成比例?
    • 功能分解是一种更深层次的分解,是否合理?

    通讯

    通讯方法描述

    • 通讯是PCAM设计过程的重要阶段
    • 划分产生的诸任务,一般不能完全独立执行,需要在任务间进行数据交流;从而产生了通讯
    • 功能分解确定了诸任务之间的数据流
    • 诸任务是并发执行的,通讯则限制了这种并发性

    四种通讯模式

    • 局部/全局通讯
    • 结构化/非结构化通讯
    • 静态/动态通讯
    • 同步/异步通讯

    通讯判据

    • 所有任务是否执行大致相当的通讯?
    • 是否尽可能的局部通讯?
    • 通讯操作是否能并行执行?
    • 同步任务的计算能否并行执行?

    组合

    方法描述

    • 组合是由抽象到具体的过程,是将组合的任务能在一类并行机上有效的执行
    • 合并小尺寸任务,减少任务数。如果任务数恰好等于处理器数,则也完成了映射过程
    • 通过增加任务的粒度和重复计算,可以减少通讯成本
    • 保持映射和扩展的灵活性,降低软件工程成本

    表面-容积效应

    • 通讯量与任务子集的表面成正比,计算量与任务子集的体积成正比
    • 增加重复计算有可能减少通讯量

    重复计算

    • 重复计算减少通讯量,但增加了计算量,应保持恰当的平衡
    • 重复计算的目标应减少算法的总运算时间

    组合判据

    • 增加粒度是否减少了通讯成本?
    • 重复计算是否已权衡了其得益?
    • 是否保持了灵活性和可扩展性?
    • 组合的任务数是否与问题尺寸成比例?
    • 是否保持了类似的计算和通讯?
    • 有没有减少并行执行的机会?

    映射

    方法描述

    • 每个任务要映射到具体的处理器,定位到运行机器上
    • 任务数大于处理器数时,存在负载平衡和任务调度问题
    • 映射的目标:减少算法的执行时间(并行的任务→不同的处理器;任务之间存在高通讯的→同一处理器)
    • 映射实际是一种权衡,属于NP完全问题

    负载平衡算法

    • 静态的:事先确定
    • 概率的:随机确定
    • 动态的:执行期间动态负载
    • 基于域分解的:递归对剖;局部算法;概率方法;循环映射

    任务调度算法

    • 任务放在集中的或分散的任务池中,使用任务调度算法将池中的任务分配给特定的处理器

    映射判据

    • 采用集中式负载平衡方案,是否存在通讯瓶颈?
    • 采用动态负载平衡方案,调度策略的成本如何?

     

    参考文献

    https://wenku.baidu.com/view/b183017a1ed9ad51f01df2d7.html?rec_flag=default&sxts=1542421861193

     https://wenku.baidu.com/view/17709aca3186bceb19e8bbd4.html?rec_flag=default&sxts=1542421875283

    https://wenku.baidu.com/view/b994bbf6998fcc22bcd10dd7.html?rec_flag=default&sxts=1542421883056

    展开全文
  • 并行算法】知识点总结

    千次阅读 2021-01-05 21:48:58
    第一章 1、并行计算的定义和主要目的P11 定义:并行计算是指同时对多个任务或多条指令、或对多个数据项进行处理。完成此项处理的计算机系统称为并行计算机系统,它是将多个处理器(可以几...(1)并行计算机的设计 (2)有

    第一章
    1、并行计算的定义和主要目的P11
    定义:并行计算是指同时对多个任务或多条指令、或对多个数据项进行处理。完成此项处理的计算机系统称为并行计算机系统,它是将多个处理器(可以几个、几十个、几千个、几万个等)通过网络连接以一定的方式有序地组织起来(一定的连接方式涉及网络的互联拓扑、通信协议等,而有序的组织则涉及操作系统、中间件软件等)。
    并行计算的主要目的:
    一是为了提供比传统计算机快的计算速度;
    二是解决传统计算机无法解决的问题。
    2、并行计算研究的主要内容P12-17
    (1)并行计算机的设计
    (2)有效算法的设计
    (3)评价并行算法的方法
    (4)并行计算机语言
    (5)并行编程环境与工具
    (6)并行程序的可移植性
    (7)并行计算机的自动编程
    3、并行计算机体系结构要素P34-37
    结点、互联网络、内存
    4、什么是并行计算机、并行计算机的组成部分P26-27
    并行计算机是由一组处理单元组成的,这组处理单元通过相互之间的通信与协作,以更快的速度共同完成一项大规模的计算任务。
    并行计算机的组成部分:计算节点和节点间的通信与协作机制。

    5、进程的定义、状态和进程间的信息交流方式P39-40
    (1)进程的定义:进程(process)可表示成四元组(P, C, D, S)
    P是程序代码
    C是进程的控制状态
    D是进程的数据
    S是进程的执行状态
    (2)进程的状态:
    非存在状态:进程依赖的程序还没有投入运行
    就绪状态:进程由其父进程调入并准备运行
    运行状态:进程占有CPU和其它必须的计算资源,并执行指令
    挂起状态:由于CPU或其它必须的计算资源被其它进程占有,或必须等待某类事件的发生,进程转入挂起状态
    退出状态:进程正常结束或因异常退出而被废弃
    (3)进程间的信息交流方式:
    进程是操作系统资源调度的基本单位
    各进程不能直接访问其它进程的局部内存空间
    多个进程之间相互交流信息 的三种形式 :
    通信:进程间的数据传递称为进程间通信
    同步:同步是使位于相同或不同处理机中的多个进程之间相互等待的操作
    聚集:聚集将位于相同或不同处理机中的多个进程的局部结果综合起来

    6、并行计算机的分类Flynn(1966年)分类法P48

    Flynn(1966年)分类法是根据系统的指令流和数据流对计算机系统进行分类的一种方法。

    指令流:机器所执行的指令序列
    数据流:指令流调用的数据序列(包括输入数据和中间结果)

    1)SISD:传统的单处理机系统。由程序生成的一个单指令流,在任意时刻处理单独的数据项。
    2)SIMD:如:阵列处理机系统(Processor Arrays)。由一个控制器负责从存储器中取出指令并将这些指令发送给各个处理器,每个处理器同步执行相同的指令,但操作不同的数据。
    3)MISD:相当于在指令一级并行,而在被操作的数据级串行的情况,实际上这种模型是不能实现的。
    4)MIMD:当今绝大多数并行计算机都属于这一类。每个处理器拥有一个单独的程序,每个程序为每一个处理器生成一个指令流,每条指令对不同的数据进行操作。

    第二章
    1、并行处理技术的核心P1
    核心:增加同一时间间隔的操作数
    2、并行算法的定义P3
    并行算法:适合于并行操作的一类算法的总称。
    并行算法是指在各种并行计算机上求解问题和处理数据的算法,其本质是把多个任务映射到多个处理器中执行。并行算法的实现强烈依赖于计算机硬件环境和软件环境。
    3、并行算法的分类P4
    按运算对象分类
    数值算法、非数值算法;
    按进程间程序执行的顺序关系分类
    同步算法、异步算法;独立并行算法;
    (分布式算法)
    按处理机承担的计算任务粒度分类
    细粒度并行算法、中粒度并行算法、
    大粒度并行算法
    4、并行算法运行时的相关时间定义P5-7
    并行算法运行时间:并行算法在具体并行计算机上求解一个问题所需时间。一般用Tp表示。
    如果并行算法的不同任务进程不能同时开始或同时结束,并行算法运行的时间定义为:第一个任务进程开始执行的时间算起到最后一个任务进程执行完毕所需的时间。

    5、并行机的规模P9
    并行计算机的规模指某一具体并行计算机所具有的最大计算性能,包括处理机台数、单机性能、网络带宽、整体内存大小与输入输出能力等硬件指标;还涉及操作系统、并行程序设计环境等软件指标。
    6、问题的规模和分类P10
    问题规模:指问题求解的规模或问题求解的大小。问题规模是衡量并行计算机性能的一个重要参数。可以将问题规模大致分为:输入输出规模、计算规模、内存需求规模和通信(同步)规模。
    应用问题的分类:
    根据算法实现的难易程度、通信方式,将问题分为:同步问题(松散同步问题、非规则松散同步问题)、异步问题、独立并行问题。
    7、并行算法的度量指标P12-13
    除运行时间、并行机规模和问题规模,对于并行算法的度量指标还包括
    1)并行度:算法中可并行执行的单位操作数
    操作是计算的基本单位,一般指加减乘除等基本算术运算,也可以指某一任务级的作业。
    2)粒度:粒度是一个相对的概念,与算法固有的内在并行度和具体的并行机相关。大粒度以为着并行执行的是大任务。
    3)成本:运行时间与处理机个数的乘积
    4)加速比:在单处理机上的运行时间除以多处理机上运行的时间
    8、绝对加速比和相对加速比的定义P18-19
    绝对加速比:将最好的串行算法与并行算法相比较.
    定义一(与具体机器有关)将最好的串行算法在一台上的运行时间与并行算法在N台运行的时间相比。
    定义二(与具体机器无关)将最好的串行算法在最快的顺序机上的执行时间与并行算法在并行机上的运行时间相比。
    在这里插入图片描述

    相对加速比:同一并行算法在单节点上运行时间与在多个相同节点构成的处理机系统上的运行时间之比。
    这种定义侧重于描述算法和并行计算机本身的可扩展性。
    在这里插入图片描述

    9、可扩展性的直观定义、研究目的和度量方法P47-49
    直观定义:对任意数量(n)的处理机和任意规模(s)的问题,若所有算法的系统效率 E =1, 则系统是可扩展的。
    可扩展性的研究目的:
    1)确定某类问题的何种并行算法与何种并行系统的组合,可有效的利用系统大量处理机
    2)有算法在小规模并行机上的运行性能来预测起移植到大规模并行机上后的运行性能
    3)对一固定规模的问题,能确定起运行在某类并行系统上时,所需的最有处理机台数和获得的最大加速比
    4)指导并行算法和并行机体系结构的改进
    度量方法:
    等效率可扩展性度量方法:揭示问题规模与系统规模的关系(1987);
    等速度可扩展性度量方法:揭示并行算法-机器组合的关系(1996)
    等时间/通信开销比的可扩展性度量方法:等计算时间/通信开销比(1999)
    可扩展性度量方法的基本要求:
    1)能提供并行系统规模的变化如何影响起性能的信息;2)能描述并行算法与并行机组合的函数;3)可评估、可比较的定性性能度量方法。

    第三章
    1、并行计算模型的定义和作用P3-4

    定义: 并行计算模型:从并行算法的设计和分析出发,将各种并行计算机(至少是某一类)的基本特征抽象出来,形成一个抽象的并行计算模型。
    并行计算模型的作用
    1)是并行算法实现的基础
    2)给并行算法设计与分析提供了一个简单方便的框架
    3)使并行算法的设计具有一定的生命力

    2、PRAM模型定义、优缺点P7-9
    定义:PRAM(Parallel Random Access Machine)模型是单指令流多数据流(SIMD)并行机中的一种具有共享存储的模型。它假设有一个无限大容量的共享存储器,并且有多个功能相同的处理器,在任意时刻处理器可以访问共享存储单元。
    优缺点:
    优点
    适合并行算法表示和复杂性分析,易于使用,隐藏了并行机的通讯、同步等细节。
    缺点
    不适合MIMD并行机,忽略了SM的竞争、通讯延迟等因素
    不现实,首先容量无限大的存储器是不存在的,而且由于各方面的原因,全局访存通常要比预想的慢。其次,他忽略了通信带宽的影响。

    3、APRAM模型定义、优缺点P10、P14
    定义:
    又称分相(Phase)PRAM或MIMD-SM。每个处理器有其局部存储器、局部时钟、局部程序;无全局时钟,各处理器异步执行;处理器通过SM进行通讯;处理器间依赖关系,需在并行程序中显式地加入同步(路)障(Synchronization Barrier)。
    优缺点
    易编程和分析算法的复杂度,但与现实相差较远,其上并行算法非常有限,也不适合MIMD-DM模型。
    4、LogP模型的参数表示意义、优缺点P16-17
    参数表示意义:
    L(Latency):源处理机与目标处理机之间进行消息通信(一个或几个字)所需等待的延迟时间的上限。
    o(overhead):处理机用于发送或者接受每个消息的时间开销。
    g(gap):一台处理机连续进行消息发送或接收时的最小时间间隔。
    P(Processor):处理机或处理模块的数量
    LogP模型是异步的,假设所有消息都很短。
    优缺点:
    捕捉了MPC的通讯瓶颈,隐藏了并行机的网络拓扑、路由、协议,可以应用到共享存储、消息传递、数据并行的编程模型中;但难以进行算法描述、设计和分析。
    5、BSP模型中参数的意义P19
    BSP模型以三个参数描述分布式存储的多计算模型。三个参数:
    处理机(P)
    处理机之间的点对点通信的选路器(g)
    执行以时间间隔L为周期的路障同步器(L)
    6、LogP模型与BSP模型之间的关系P18-19
    BSP vs. LogP
    BSPLogP:BSP块同步BSP子集同步BSP进程对同步=LogP
    BSP可以常数因子模拟LogP,LogP可以对数因子模拟BSP
    BSP=LogP+Barriers-Overhead
    BSP提供了更方便的程设环境,LogP更好地利用了机器资源
    BSP似乎更简单、方便和符合结构化编程
    7、并行算法设计的常用手段P20
    设计算法经常采用以下三种手段:
    1)将现有的串行算法中固有的并行性直接并行化;
    2)从问题本身出发设计一个新的算法;
    3)修改已有的并行算法,使其可以求解相似问题
    8、并行算法常用的设计技术P48-49
    目前普遍使用的并行算法的设计技术:
    1).流水线技术
    将任务分割成许多子任务,每个处理器完成其中一个,且第一个处理器完成第一个子任务后,第二个处理器可以开始完成第二个子任务…
    2).分治策略
    将原问题分成若干个特征相同的子问题,分别处理。
    常见的分治策略:任务分割;数据分割
    3).平衡树方法
    将输入元素作为叶子节点构造二叉平衡树。
    4).倍增技术(指针跳跃技术)
    适合处理链表、有向图等数据结构;经常应用于通信系统中。
    5).加速级联策略
    将最优算法(计算速度慢)和最快算法(不是最优)级联起来。
    9、并行程序设计的主要方式P51
    并行程序的设计有多种方式,主要分为:
    共享变量方法;消息传递方法;数据并行程序设计;面向对象的并行程序设计;函数程序设计方法;逻辑程序设计方法。
    第四章
    1、三对角方程组的并行求解的常方法P31
    求解三对角线性方程组的并行算法有很多:追赶法、基于递推公式的并行算法、循环约化法、分裂法等。我们这里只考虑目前最有效的矩阵分裂法。

    2、稀疏矩阵的压缩存储P69
    矩阵的压缩存储:为多个值相同的元素只分配一个存储空间,对零元素不分配空间
    一般来说,稀疏矩阵非0元素的分布是无规律的。因此,在存储非0元素的同时,还要存储适当的辅助信息。
    稀疏矩阵常用的压缩存储方式:(1)三元组表(2)十字链表
    (1)三元组表:存储特点:
    对于矩阵中每个非0元素,用它的行号、列号、元素值,即(i, j, aij)表示。
    将表示稀疏矩阵的所有非0元素的三元组按行优先(列优先)顺序排列,则可得到一个其结点均是三元组的线性表,称为三元组表。
    要唯一确定一个稀疏矩阵,还必须存储该矩阵的行数和列数。
    (2)十字链表:十字链表是稀疏矩阵链接形式存储结构的一种(当然还有其它形式)。
    在该方法中每一个非0元素用一个结点表示,结点中除了表示非0元素的行、列和值的三元组外,还增加了两个链域:
    行指针域:用来指向本行中下一个非0元素;
    列指针域:用来指向本列中下一个非0元素。
    在每一个行链表和每一个列链表增加一个和表结点相同的表头结点,表头结点中的行、列域置为0,并且将所有的行、列链表和他们的头结点一起链成一个循环链表。

    实际实现时,两组头结点可以合用,即第i行链表和第i 列链表共享一个表头结点。因为表头结点中值域v无用,所以可以将它作为指针域,用来指向下一个表头结点的指针。

    3、矩阵与向量乘法的并行设计(一维划分)P12-16

    4、矩阵与矩阵乘法的并行设计(行列划分)P27-29

    5、Cannon 算法P41-45
    第五章
    1、矩阵的LU分解

    2、三对角方程组的并行求解

    3、Arnoldi算法P69

    4、FOM算法P74

    第九章
    1、消息传递模型的原理和优缺点P208
    原理:消息传递模型中,计算由一个或多个进程组成,进程间的通信通过调用库函数发送和接收消息来完成。
    优点:
    1)具有高度的可移植性。
    2)允许用户显式地控制控制并行并行程序的存储,特别可以控制每个进程所使用的内存。(需要编程人员对内存分配,需要考虑通信顺序等细节问题)
    缺点:消息传递接口的不同对程序性能将产生重要影响,主要因素有:实际消息传递的带宽、延迟和计算与通信的重叠。

    2、什么是MPI?P209-210
    MPI一个信息传递接口的标准,用来开发基于信息传递的并行程序,它的目的是为用户提供功能强、可移植和灵活的信息传递接口库。(注:MPI是一个库而不是一种语言)
    3、MPI中6个常用函数的基本功能P211
    MPI_INIT 初始化MPI
    MPI_FINALIZE 终止MPI
    MPI_COMM_SIZE 确定进程的数目
    MPI_COMM_RANK 确定进程的序号
    MPI_SEND 发送一条信息
    MPI_RECV 就收一条信息
    补充部分
    1、Matlab并行循环执行的前提条件Chap2(一)P1
    对于次数确定的循环(for循环),如果循环的‘计数模块’对于单次循环是独立的(计算结果与循环体的执行顺序无关),那么理论上可以将整个循环拆分成几个子循环,然后将子循环的结果合并。
    2、简约操作及其满足条件Chap2(一)P51-57
    只有当循环的操作题相互独立时才可以用parfor关键字进行并行。但是有一类特殊的循环操作不受这个条件限制,这类操作我们称为简约操作。
    简约操作所对应的循环体并不独立,但是执行结果与执行顺序无关。

    简约变量在parfor中应该满足一些要求
    1.简约变量只能出现在简约赋值操作的表达式中
    简约操作可以由上面给的各种操作符引导,也可以自己定义。
    2.在同一parfor中,对简约变量的操作必须一致。
    3.如果简约变量的操作是‘*’或者‘[]’,x在操作符前面或者后面都可以,但是位置必须恒定。
    4.简约变量赋值应满足结合律和交换律

    3、在parfor循环中,Matlab变量主要分类Chap2(二)P2
    循环变量(loop variable)
    分段变量(sliced variable)
    广播变量(broadcast variable)
    简约变量(reduction variable)
    临时变量(temporary variable)

    4、SPMD并行结构的优势Chap3P10
    SPMD并行结构给用户提供了更大的自由度,用户可以控制更多的并行计算的细节。

    5、SPMD结构中可以使用的三种数据对象
    数据集分割方式:
    1)通过数据文件的方式将大的数据集分割到各个计算节点;
    2)通过composite对象(Matlab特有结构);
    3)通过分布式数值阵列(Matlab特有结构)。
    6、一般并行程序的数据类型Chap5P3-7
    1)同体变量2)异体变量3)独有变量4)分布式变量
    7、常用两种通用并行程序设计的方式
    Matlab并行程序一般由三种方式实现:
    1)利用Matlab内置的并行结构;
    2)利用Matlab提高的通用并行程序设计;
    3)Matlab和其他语言混合编程

    展开全文
  • 并行计算及并行算法

    万次阅读 多人点赞 2018-06-13 22:27:31
    一、并行计算  简单地说,并行计算就是在并行计算机上所做的计算。从普通意义上讲,它和常说的高性能计算、超级计算等是同义词。并行计算的初衷是为了努力仿真自然世界中一个序列中含有众多同时发生的、复杂且相关...

    一、并行计算

      简单地说,并行计算就是在并行计算机上所做的计算。从普通意义上讲,它和常说的高性能计算超级计算等是同义词。并行计算的初衷是为了努力仿真自然世界中一个序列中含有众多同时发生的、复杂且相关事件的事务状态。
      为了利用并行计算求解一个计算问题,通常基于以下考虑:1.将计算任务分解成多个子任务,有助于同时解决;2.在同一时间,由不同的执行部件可同时执行多个子任务;3.多计算资源下解决问题的耗时要少于单个计算资源下的耗时。
      并行计算可分为:1.计算密集型:如大型科学工程计算与数值模拟等;2.数据密集型:如数字图书馆、数据仓库、数据挖掘和计算可视化等;3.网络密集型:如协同计算和远程诊断等。

    二、并行计算机体系结构

    1.并行计算机结构模型

    (1)结构类型

    • SISD:单指令流单数据流计算机(冯诺依曼机)
    • SIMD:单指令流多数据流计算机
    • MISD:多指令流单数据流计算机
    • MIMD:多指令流多数据流计算机

    (2)几种MIMD

    • PVP并行向量处理机:多VP(向量处理器)通过交叉开关和多个SM(共享内存)相连
    • SMP对称多处理机:多P/C(商品微处理器)通过交叉开关/总线和多个SM(共享内存)相连
    • MPP大规模并行处理机:处理节点有商品微处理器+LM(分布式本地内存),节点间通过高带宽低延迟定制网络互联,异步MIMD,多个进程有自己的地址空间,通过消息传递机制通信
    • COW工作站机群:节点是完整操作系统的工作站,且有磁盘
    • DSM分布共享存储处理机:高速缓存目录DIR确保缓存一致性,将物理分布式LM组成逻辑共享SM从而提供统一地址的编程空间

    注:对称指所有处理器都能同等地访问I/O很同样的运行程序(如OS和I/O服务程序),而非对称主从式是仅有主处理器运行OS和控制访问I/O并监控从处理器执行

    2.并行计算机访存模型

    UMA(Uniform Memory Access)均匀存储访问:物理存储器被所有处理器均匀共享,所有处理器对所有SM访存时间相同,每台处理器可带有高速私有缓存,外围设备共享。
    - NUMA非均匀存储访问:共享的SM是由物理分布式的LM逻辑构成,处理器访存时间不一样,访问LM或CSM(群内共享存储器)内存储器比访问GSM(群间共享存储器)快
    - COMA(Cache-Only MA)全高速缓存存储访问:NUMA的特例、全高速缓存实现
    - CC-NUMA(Coherent-Cache NUMA)高速缓存一致性NUMA:NUMA+高速缓存一致性协议
    - NORMA(No-Remote MA)非远程存储访问:无SM,所有LM私有,通过消息传递通信

    3.Cache一致性协议

    • 监听总线协议:总线连接通信,写无效和写更新策略
    • 基于目录的协议:目录记录共享数据缓存状态,读缺失时查看目录D,写更新时通知目录D

    4.其他并行计算概念

    衡量并行计算机性能单位:

    • PFLOPS:每秒1千万亿 (=10^15) 次的浮点运算
    • TFLOPS:每秒1万亿 (=10^12) 次的浮点运算
    • GFLOPS:每秒10亿 (=10^9) 次的浮点运算

    TOP500前500名超级计算机排名指标(GFLOPS):
    Rmax:Maximal LINPACK(Linear system package) performance achieved
    Rpeak:Theoretical peak performance

    三、并行计算性能评测

    1、机器级的性能测评

    主要包括CPU和存储器的某些基本性能指标,并行通信开销以及机器的成本、价格和性能价格比等。
    (1)CPU和存储器的某些基本性能指标

    • 工作负载:指计算操作的数目,通常可用执行时间、所执行的指令数目和所完成的浮点运算数3个物理量来度量。
    • 并行执行时间: Tn=Tcomput+Tparo+Tcomm T n = T c o m p u t + T p a r o + T c o m m 。其中 Tcomput T c o m p u t 为计算时间, Tparo T p a r o 为并行开销时间,包括进程管理(生成、切换和结束等)、组操作(进程组的生成与消亡等)时间,和进程查询(询问进程的标志、等级和组大小等)时间; Tcomm T c o m m 为相互通信时间,包括同步(如路障、临界区、事件等)、通信(如点到点通信、整体通信、读/写共享变量等)时间和聚操作(如归约和前缀运算等)时间。

    • 存储器的层次结构:各层存储器的容量、延迟和带宽。

    • 存储器带宽的估算

    (2)通信开销 Tcomm T c o m m

    (3)机器的成本、价格和性能价格比

    2、算法级的性能测评

    包括加速、效率和可扩放性等。

    (1)并行系统的加速(比)
    指对于一个给定的应用,并行算法(或并行程序)的执行速度相对于串行算法(或串行程序)的执行速度加快了多少倍。

    加速比性能定律
    Amdahl加速定律(固定计算负载)
    Gustafson定律(适用于可扩放问题)
    Sun&Ni定律(受限于存储器)

    约定:

    • p是处理器数
    • 问题规模W=程序中串行分量Ws+可并行部分Wh
    • f为串行部分比例,f=Ws/W
    • S为加速比

    (2)扩放性
    最朴素的含义是在确定的应用背景下,计算机系统(或算法或编程等)性能随处理器数的增加而按比例提高的能力。被广泛用来描述并行算法能否有效利用可扩充的处理器的能力。

    3、程序级的性能测评

    基本测试程序、数学库测试程序和并行测试程序等

    四、并行计算理论基础:并行算法设计

    1、并行算法

    并行算法是一些可同时执行的诸进行的集合,这些进程互相作用和协调动作从而实现给定问题的求解。
    从不同角度分类成数值计算和非数值计算的并行算法;同步、异步和分布的并行算法;共享存储和分布存储的并行算法;确定的和随机的并行算法等。

    2、并行算法的表达

    (1)par-do

    n个节点并行完成for循环(每个节点不同,和i相关):

    for i = 1 to n par-do
        ...
    endfor

    (2)for all

    所有节点都执行相同语句:

    for all Pi, where 0 <= i <= k do
        ...
    endfor

    3、并行算法的复杂度

    通常分析以下指标:

    • 运行时间t(n):求解问题的时间,包括计算时间和通信时间
    • 处理器数目p(n):求解给定问题所用的处理器数目
    • 成本c(n):c(n) = t(n)*p(n)
    • 成本最优——并行算法的成本在数量级上等于最坏情况下串行求解次问题所需要的执行步数
    • 工作量W(n):并行算法完成的总的操作数量
    • 工作量最优:功耗低、环保

    并行算法的WT表示——Brent定理:

    令W(n)是并行算法A在运行时间T(n)内所执行的运算量,则A使用p台处理器可在t(n) = O(W(n)/p + T(n))时间内执行完毕

    4、并行计算模型

    1.PRAM模型(SIMD-SM)

    PRAM(Parallel Random Access Machine)并行随机存取机器,是一种抽象并行计算模型,它假设:

    • 存在容量无限大的SM
    • 有限或无限个功能相同的处理器,且均有简单算术运算和逻辑判断功能
    • 任何时刻各处理器可通过SM交换数据

    根据并发访问机制,又分为:

    • 不允许同时读和同时写的PRAM-EREW
    • 允许同时读但不允许同时写的PRAM-CREW
    • 允许同时读和同时写的PRAM-CRCW

    PRAM-CRCW又分为:

    • 只允许同时写相同的数CPRAM-CRCW
    • 只允许优先处理器先写PPRAM-CRCW
    • 允许任意处理器自由写APRAM-CRCW

    PRAM优点:

    • 适合并行算法表达、分析和比较
    • 使用简单,屏蔽了通信、存储管理、进程同步等并行细节
    • 易于修改算法设计以适应不同并行机

    PRAM缺点:

    • PRAM是同步模型,同步锁费时
    • 不适用于MIMD和DM
    • 假设任何处理器可在单位时间内访问任何处理单元而不考虑竞争和带宽,不现实

    2.异步APRAM模型(MIMD-SM)

    异步APRAM模型假设:

    • 每个处理器有LM、局部时钟、局部程序
    • 处理器通信经过SM
    • 无全局时钟,各处理器异步执行各自指令
    • 处理器之间的指令相互依赖关系必须显式加入同步障
    • 一条指令可以在非确定但有界时间内完成

    指令类型有:

    • 全局读:从SM读到LM
    • 局部操作:LM操作存入LM
    • 全局写:LM写入SM
    • 同步:各处理器需等到其他处理器到达后才能继续执行

    APRAM比PRAM更加接近实际并行机

    3.BSP模型(MIMD-DM)

    BSP(Bulk Synchronous Parallel)大同步并行机(APRAM算作轻量)是一个分布式存储的MIMD模型,它的计算由若干全局同步分开的、周期为L的超级步组成,各超级步中处理器做LM操作并通过选路器接收和发送消息;然后做一次全局检查,以确定该超级步是否已经完成(块内异步并行,块间显式同步)

    参数:处理器数p、选路器吞吐率g、全局同步间隔L、一个超级步中一个处理器至多发送或接收h条消息

    4.LogP模型:MIMD-DM,点到点通讯

    LogP模型是分布式存储、点到点通信的MIMD模型

    LogP采取隐式同步,而不显式同步障

    5、并行算法基本设计策略

    1 、串改并
    发掘和利用现有串行算法中的并行性,直接将串行算法改造为并行算法

    最常用的设计思路但并不普适,好的串行算法一般无法并行化(数值串行算法可以)

    快速排序的串改并
    SISD上串行执行,最坏情况下O(n^2),理想情况下O(nlogn)

    思路:将O(n)的划分(Partition)并行化是关键,算法:

    • 构造一棵二叉排序树,主元是根
    • 小于等于主元素处于左子树,大于主元素处于右子树
    • 左右子树均是二叉排序树

    在CRCW模型上,用伪代码描述如下:

    //A[1...n]排序用n个处理器,处理器i中存有A[i]
    //f[i]中存有其元素是主元素的处理器号
    //LC[1...n]和RC[1...n]分别记录给定主元素的左儿子和右儿子
    
    for each processor i par-do
        root = i    //所有处理器竞争,只有一个写入root
        f[i] = root //所有处理器都把root写入自己的f[i]
        LC[i] = RC[i] = n + 1   //初始值
    endfor
    
    repeat for each processor i != root do
        if (A[i] < A[f[i]]) || (A[i] == A[f[i]] && i < f[i])
            LC[f[i]] = i    //并发写,所有满足条件的i只有一个写入LC[f[i]]作为左子树的根,也就是下一次循环的主元素
            if i == LC[f[i]] then
                exit        //若当前处理器写入则什么也不做
            else
                f[i] = LC[f[i]] //若当前处理器没有写入,那么它只能当LC[f[i]]的字节点了
            endif
        else
            RC[f[i]] = i    //并发写,所有满足条件的i只有一个写入RC[f[i]]作为右子树的根,也就是下一次循环的主元素
            if i == RC[f[i]] then
                exit        //若当前处理器写入则什么也不做
            else
                f[i] = RC[f[i]] //若当前处理器没有写入,那么它只能当RC[f[i]]的字节点了
            endif
        endif
    endrepeat

    每次迭代构造一层排序二叉树花费O(1)时间,在基本平衡的情况下树高O(logn),则算法复杂度为O(logn)

    2 、全新设计
    从问题本身描述出发,不考虑相应的串行算法,设计 一个全新的并行算法

    有向环K着色算法的并行化设计
    问题:有向环顶点着色,一共K种颜色,相邻顶点不允许同色

    串行算法(3着色):交替2种颜色,若顶点是奇数则需要用到第3种颜色(难以并行化)

    SIMD-EREW上的并行K着色算法:

    //初始随机着色为c[i],每个顶点着色不同
    //输出着色方案为nc[i]
    for i = 1 to n par-do
        k = c[i]和c[i的后继]的最低的不同二进制位
        nc[i] = 2 * k + c[i]的二进制第k位
    endfor

    O(1)时间完成,需要算法正确性证明

    3、借用法
    找出求解问题和某个已解决问题之间的联系,改造或利用已知算法应用到求解问题上

    利用矩阵乘法求所有点对间最短路径
    d[k][i][j]表示从vi到vj**至多**经过k-1个中间顶点时的最短路径,d[k][i][j] = min{d[k/2][i][l]+d[k/2][l][j]}

    那么可以用矩阵乘法的改进(乘变加,求和变min)做logn次矩阵乘法即可

    思路是这样,具体伪代码略,需要O(n^3)个节点,时间复杂度为O(log^2(n))

    6、并行算法常用设计技术

    1、划分设计技术

    使用划分法把问题求解分成两步:

    • 把给定问题划分成p个几乎等尺寸的子问题
    • 用p台处理器并行求解子问题

    (1)均匀划分(PSRS排序)

    长度为n的待处理序列均匀划分给p个处理器,每个处理器处理n/p个元素

    MIMD机器上的PSRS排序算法:

    (1)均匀划分:将n个元素A[1..n]均匀划分成p段,分配给p个处理器
    (2)局部排序:pi调用串行排序算法对A[(i-1)n/p+1..in/p]排序
    (3)选取样本:pi从其有序子序列A[(i-1)n/p+1..in/p]中选取p个样本元素
    (4)样本排序:用一台处理器对p2个样本元素进行串行排序
    (5)选择主元:用一台处理器从排好序的样本序列中选取p-1个主元,并播送给其他pi 
    (6)主元划分:pi按主元将有序段A[(i-1)n/p+1..in/p]划分成p段
    (7)全局交换:各处理器将其有序段按段号交换到对应的处理器中(一定保证均匀划分??)
    (8)归并排序:各处理器对接收到的元素进行归并排序

    (2)方根划分(Valiant归并排序)

    长度为n的待处理序列,取i*sqrt(n)为划分元,将元素划分成若干段交给处理器处理

    SIMD-CREW机器上的Valiant归并排序:

    (1)方根划分:把A和B(长n有序段)的第i*sqrt(n)元素作为划分元,把A和B分成若干段
    (2)段间比较:A中的所有划分元和B中的所有划分元比较,确定A中划分元应插入B中的哪一段
    (3)段内比较:A中的划分元和B中相应段比较并确定插入位置,这些插入位置又将B重新划分成了若干段
    (4)段组合并:插入A划分元后,又得到若干有序段组需要归并,递归直到有一组(A)的长度为0

    使用n个处理器可以在O(loglogn)内完成

    (3)对数划分(并行归并排序)

    取i*logn作为划分元划分

    定义位序rank(x,X)为X中小于等于x的元素个数,则有PRAM-CREW上的对数划分:

    //非降有序的A={a[1],...,a[n]}和B={b[1],...,b[m]}归并
    //假设log(m)和k=m/log(m)均为整数
    j[0]=0
    j[k]=n
    
    for i = 1 to k - 1 par-do
        j[i] = rank(b[ilogm], A)
    endfor
    
    for i = 1 to k - 1 par-do
        Bi = {b[ilogm+1], ..., b[(i+1)logm]}
        Ai = {a[j[i]+1], ..., a[j[i+1]]}
    endfor
    
    //将原问题转化为子序列组Bi和Ai的归并,那么同样可以递归调用完成整个序列的归并
    //对数划分保证Bi和Ai中的元素均大于Bi-1和Ai-1中的元素

    (4)功能划分( (m,n)-选择)

    功能划分是根据特定问题而把序列分成p个等长组,每组符合问题特性的一种划分方法

    (m,n)-选择问题是将长为n的序列中选取前m个较小的元素,利用功能划分来实现并行化的(m,n)-选择问题求解:

    (1)功能划分:将A划分成g=n/m组,每组含m个元素
    (2)局部排序:使用Batcher排序网络将各组并行排序
    (3)两两比较:将所排序的各组两两比较,从而形成MIN序列
    (4)排序-比较:对各个MIN序列,重复执行第(2)和第(3)步,直至选出m个最小者

    2、分治设计技术

    分治将复杂问题划分成较小规模特性相同的子问题,且子问题类型和原问题类型相同,通常用递归完成分治算法

    3、平衡树设计技术

    以树的叶结点为输入,中间结点为处理结点,由叶向根或由根向叶逐层进行并行处理

    4、倍增设计技术

    递归调用时,所要处理数据之间的距离逐步加倍, 经过k步后即可完成距离为2^k的所有数据的计算

    5、流水线技术

    将算法路程分成p个前后衔接的任务片段,一个任务片段完成之后其后继任务片段可以立即开始,那么久可以引入流水线的思想来处理多条数据

    五、并行计算软件支撑:并行编程

    1、并行程序设计基础

    1.1 并行语言构造方法

    • 库例程:MPI、Pthreads
    • 扩展串行语言:Fortran90
    • 加编译注释构造:OpenMP

    1.2 并行性问题

    可利用SPMD来伪造MPMD

    需要运行MPMD:parbegin S1 S2 S3 parend
    可以改造成SPMD:

    for i = 1 to 3 par-do
        if i == 1 then S1
        else if i == 2 then S2
        else if i == 3 then S3
    endfor

    那么并行扩展至需要支持SPMD即可

    1.3 交互/通信

    (1)交互类型

    • 通信:进程间传数(共享变量、消息传递、参数传递[父进程传给子进程])
    • 同步:进程间相互等待或继续执行的操作(原子同步、控制同步[同步障、临界区]、数据同步[锁、condition、监控程序和事件])
    • 聚合:将分进程所计算的的结果整合起来(规约、扫描)

    (2)交互方式

    • 同步交互:所有参与者全部到达后继续执行
    • 异步交互:任意进程到达后不必等待其他进程即可继续执行

    (3)交互模式

    按编译时是否能确定交互模式可分为静态的、动态的

    按多少发送者和接收者:

    • 一对一:点到点通信
    • 一对多:广播、散播
    • 多对一:收集、规约
    • 多对多:全交换、扫描、置换、移位

    1.4 并行编程风范

    • 相并行:BSP模式,程序由一组超级步组成,步内各自并行计算,步间通信同步
    • 主从并行:主进程串行执行并且协调任务,子进程计算任务,需要划分设计并结合相并行
    • 分治并行:父进程把负载分割并指派给子进程,难以平衡负载
    • 流水线并行:进程划分成流水线,依次依赖,数据开始流动
    • 工作池并行:进程从工作池中取任务执行

    1.5 并行程序设计模型

    (1)隐式并行

    用串行语言编程,编译器货操作系统自动转化成并行代码

    特点:语义简单、可以执行好、易调试易验证、but效率低

    (2)数据并行

    SIMD模型,包括数据选路和局部计算,特点:但现场、松散同步、常用聚合操作

    数据并行计算π:

    long i,j,t,N=100000;
    double local[N], temp[N], pi, w;
    w = 1.0/N;
    
    forall (i = 0; i < N; i++) {
        local[i] = (i + 0.5) * w;
        temp[i] = 4.0 / (1.0 + local[i] * local[i]);
    }
    
    pi = reduce(temp, +);

    (3)消息传递

    MPP、COW自然模型,MPI广泛应用:多线程异步并行、地址空间分开、常用SPMD形式编码

    MPI消息传递计算π:

    #define N 100000
    main(){
        double local=0.0,pi,w,temp=0.0;
        long i,taskid,numtask;
    
        w=1.0/N;
    
        MPI_Init(&argc,&argv);
        MPI_Comm_rank(MPI_COMM_WORLD,&taskid);
        MPI_Comm_Size(MPI_COMM_WORLD,&numtask);
    
        for (i = taskid; i < N; i=i + numtask){
            temp = (i+0.5)*w;
            local = 4.0/(1.0+temp*temp)+local; 
        }
    
        MPI_Reduce(&local,&pi,1,MPI_Double,MPI_MAX,0, MPI_COMM_WORLD);
    
        if (taskid == 0) printf(“pi is %f \n”,pi*w); 
    
        MPI_Finalize() ;
    }

    (4)共享变量

    PVP、SMP、DSM自然模型,多线程异步,显示同步而隐式通信

    OpenMP使用共享变量计算π:

    #define N 100000
    main(){
        double local,pi=0.0,w;
        long i;
    
        w=1.0/N;
    
        #pragma parallel
        #pragma shared(pi, w)
        #pragma local(i, local) 
        {
            #pragma parallel for (i = 0; i < N; i++)
            {
                local = (i + 0.5) * w;
                local = 4.0 / (1.0 + local * local);
            }
            #pragma critical
            {
                pi = pi + local
            }
        }
    }

    六、共享存储系统并行编程——OpenMP编程

    OpenMP是FORK-JOIN模型,主线程串行执行,直到编译制导并行域出现

    七、分布存储系统并行编程——MPI编程

    MPI是一种消息传递接口的标准,适用于分布式存储系统的编程模型

    与OpenMP不同的是,MPI是多进程的并行模式,运行时需要在外部指定开启进程数,并且是用SPMD的编程风格去模拟MPMD的编程风格(用进程号区别),不会FORK-JOIN而是通过消息传递同步

    八、GPU体系结构及编程——CUDA编程

    展开全文
  • 并行计算复习第二篇 并行计算理论基础:并行算法设计Ch5 并行算法与并行计算模型5.1 并行算法的基础知识1.并行算法的表达(1)par-don个节点并行完成for循环(每个节点不同,和i相关):for i = 1 to n par-do ... ...
  • 第一章 1、并行计算的定义和主要目的 定义:并行计算是指同时对多个任务或多条指令、或对多个数据项进行处理。完成此项处理的计算机系统称为并行计算机系统,它是将多个处理器(可以几个、几十...(2)有效算法设计 (3
  • 因此,本文基于异构负载的特点,基于可分负载理论,采用LIFO的通信策略,单纯形通信模型,基于Needleman-Wunsch的双序列全局比对并行算法进行设计,提出了该策略。划分分数数据矩阵,确定最佳的迭代次数并分配给子...
  • 并行计算程序设计(CUDA C)

    千次阅读 2021-11-23 11:08:25
    并行算法的原理和模式 处理器架构特性和约束 异构并行计算简介 目标 了解延迟设备(CPU 内核)和吞吐量设备(GPU 内核)之间的主要区别 了解为什么成功的应用程序越来越多地使用这两种类型的设备 CPU:面向延迟...
  • 1.3.4并行算法 1.3.5其他实用算法 第2章算法分析基础 2.1算法分析体系及计量 2.1.1算法分析的评价体系 2.1.2算法的时间复杂性 2.1.3算法的空间复杂性 2.1.4NP完全性问题 2.2算法分析实例 2.2.1非递归算法分析 2.2.2...
  • 本书是并行计算系列丛书之开篇, 它以并行计算为主题, 围绕并行计算机、并行算法和并行程序设计展开讨论, 强调融并行计算机体系结构、数值与非数值并行算法设计以及并行程序设计为一体, 着力构建并行计算“结构—...
  • 算法---->并行算法

    千次阅读 2013-05-20 16:32:53
    并行算法 一、并行算法 什么是并行算法? 它可理解为: 适合于在某类并行计算机上求解问题和处理数据的算法, 是一些可同时执行的诸进程的集合, 这些进程相互作用和协调作用, 从而达到对给定问题的求解。 二、并行...
  • 并行遗传算法解决TSP问题

    千次阅读 2018-01-17 20:33:35
    并行遗传算法解决TSP问题一、问题描述旅行商问题(TSP)可简单描述为:一位销售商从n个城市中的某一城市出发,不重复地走完其余n-1个城市并回到原出发点,在所有可能路径中求出路径长度最短的一条。旅行商的路线可以...
  • 用C++ 17并行算法实现更好的性能 作者:Billy 2018年9月11日 这篇文章是微软的C++产品团队和其他客人回答我们从客户那里收到的问题的一系列常规文章的一部分。这些问题可以是任何C++相关的:MSVC工具集,标准语言和库...
  • 基本遗传算法(GA)详解

    千次阅读 2022-05-09 21:46:44
    遗传算法(GA)
  • 基本遗传算法

    千次阅读 2022-04-09 10:43:10
    遗传算法可广泛应用于组合优化、机器学习、自适应控制、规划设计和人工生命等领域。 遗传算法基本思想 遗传算法基本思想: 在求解问题时从多个解开始,然后通过一定的法则进行逐步迭代以产生新的解。 遗传算法...
  • 异构并行算法设计 同一算法在不同的处理器上具有不同的性能瓶颈,这主要是因为不同处理器的设计理念不同,应用场景也有区别,因此将不同比例的晶体管用在了不同的单元上。比如图1展示了Intel X86处理器和NVIDIA ...
  • 文章目录1 引言2 基本思想及发展历史3 基本遗传算法详细步骤3.1 编码3.2 初始群体设定3.3 设计适应度函数3.4 遗传操作3.4.1 选择3.4.2 交叉3.4.3 变异4 基本遗传算法总结5 遗传算法改进5.1 双倍体遗传算法5.2 双种群...
  • 第二篇包括并行算法的一般设计策略基本设计技术和一般设计过程;第三篇包括矩阵运算、稠密与稀疏线性方程组的求解和快速傅里叶变换;第四篇包括并行程序设计基础、共享存储与分布存储系统 并行编程以及并行程序...
  • 14.2 并行算法 14.2.1 并行计算模型 14.2.2 简单并行分治法 14.2.3 串行子集和Brent定理 14.2.4 递归倍增 14.2.5 并行归并和排序 14.2.6 找出凸多边形的直径 14.3 在线算法 14.3.1 高速缓存算法 14.3.2 拍卖策略 ...
  • 算法设计的方法

    千次阅读 2016-03-01 21:57:31
    1.算法简介作用:要使计算机能完成人们预定的工作,首先必须为如何完成预定的工作设计一个算法,然后再根据算法编写程序。定义:简单的说,算法(Algorithm)是由有穷规则构成的为解决某一类问题的运算序列(方法或...
  • 并行计算机未来发展前景

    千次阅读 2016-11-24 20:37:47
    这些技术的发展促进了并行计算机的产生。到80年代蓬勃发展和百家争鸣,再到90年代体系结构框架趋于统一,并行计算机得到突破性的发展。现代计算机的发展历程可以分为2个时代:串行计算时代和并行计算时代。并行计算...
  • 算法分析与设计课程总结

    千次阅读 2017-10-12 15:52:55
    算法设计的整个过程,可以包含对问题需求的说明、数学模型的拟制、算法的详细设计算法的正确性验证、算法的实现、算法分析、程序测试和文档资料的编制。  算法设计的先驱者唐纳德。E。克努特对算法的特征做了如下...
  • 1.4 遗传算法基本用语 6 1.5 遗传算法的研究方向 7 1.6 基于遗传算法的应用 8 第二章 基本遗传算法及改进 11 2.1 遗传算法的运行过程 11 2.1.1 完整的遗传算法运算流程 11 2.1.2 遗传算法基本操作 13 2.2...
  • 1. 什么是蚁群算法? 蚁群算法的本身来源于一种生物的自然现象,即蚂蚁在寻找食物过程中发现路径的行为,是...2.蚁群算法基本原理 蚂蚁在觅食过程中能够在其经过的路上留下一种称之为信息素的物质,并在觅食过程中
  • 常见算法—贪心算法

    2020-07-01 22:15:58
    贪心算法一、基本概念二、基本思路三、存在的问题...贪心算法无固定的算法框架,算法设计的关键是贪心策略的选择,必须注意的是,贪心算法不是对所有问题都能得到整体最优解,选择贪心策略必须具备 无后效性(即某个状
  • 程序设计与基础算法

    千次阅读 2018-10-31 10:55:41
    算法(Algorithm)是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制。也就是说,能够对一定规范的输入,在有限时间内获得所要求的输出。一个算法的优劣...
  • 进程调度算法设计

    千次阅读 2019-08-06 19:10:29
    在进程管理中,进程调度是核心,因为在采用多道程序设计的系统中,往往有若干个进程同时处于就绪状态,当就绪进程个数大于处理器数目时,就必须依照某种策略决定哪些进程优先占用处理器。本实验模拟在单处理器情况下...
  • 学生通过该题目的设计过程,掌握常用页面置换算法的原理、软件开发方法并提高解决实际问题的能力。 二、设计内容 1.了解UNIX的命令及使用格式,熟悉UNIX/LINUX的常用基本命令,练习并掌握UNIX提供的vi编辑器来......

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 58,854
精华内容 23,541
热门标签
关键字:

并行算法的基本设计策略