精华内容
下载资源
问答
  • 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

    展开全文
  • 并行计算复习第二篇 并行计算理论基础:并行算法设计Ch5 并行算法与并行计算模型5.1 并行算法的基础知识1.并行算法的表达(1)par-don个节点并行完成for循环(每个节点不同,和i相关):for i = 1 to n par-do ... ...

    并行计算复习

    第二篇 并行计算理论基础:并行算法设计


    Ch5 并行算法与并行计算模型

    5.1 并行算法的基础知识

    1.并行算法的表达

    (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
    2.并行算法的复杂度
    • 运行时间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))时间内执行完毕
    

    5.2 并行计算模型

    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采取隐式同步,而不显式同步障


    Ch6 并行算法基本设计策略

    6.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)

    6.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)时间完成,需要算法正确性证明

    6.2 借用法

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

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

    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))


    Ch7 并行算法常用设计技术

    6.1 划分设计技术

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

    1. 把给定问题划分成p个几乎等尺寸的子问题
    2. 用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个最小者

    6.2 分治设计技术

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

    (1)双调归并网络

    双调序列:若序列x[0],…,x[n-1]是双调序列,则存在一个0<=k<=n-1使得x[0]>=…>=x[k]<=x[k+1]<=…<=x[n-1]或序列循环移动可以得到此关系

    Batcher定理:双调序列对0<=i<=n/2-1,比较所有x[i]和x[i+n/2]得到的小序列MIN和大序列MAX仍然是双调序列

    Batcher双调归并排序算法:

    //输入双调序列X得到非降有序序列Y
    procedure Bitonic-Merge(x) {
        for i = 0 to n/2 - 1 par-do
            s[i] = min(x[i], x[i+n/2])
            l[i] = max(x[i], x[i+n/2])
        endfor
    
        Bitonic-Merge(s)
        Bitonic-Merge(l)
    
        output s followed by l
    }

    6.3 平衡树设计技术

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

    (1)求最大值

    SIMD-TC(SM)上O(logn)的树上求最大值算法:

    //带求最大值的n个元素放在A[n, ..., 2n-1]中,最大值放在A[1]中
    //n=2^m
    for k = m-1 to 0 do
        for j = 2^k to 2^(k+1)-1 par-do
            A[j]=max(A[2j],A[2j+1])
        endfor
    endfor

    SIMD-CRCW上常数时间求最大值算法:

    //输入A[1...p]共p个元素
    //B[1..p][1..p],M[1..p]为中间处理用的布尔数组, 如果M[i]=1, 则A[i]为最大值
    
    for i = 1 to p, j = 1 to p par-do   //W(n)=O(p^2)换取时间O(1)
        if A[i] >= A[j] then
            B[i,j] = 1
        else
            B[i,j] = 0
        endif
    endfor
    
    for i = 1 to p par-do
        M[i] = B[i,1]∧ B[i,2]∧... ∧B[i,p] 
        //向量操作保证O(1)完成,则该并行段也是O(1)
        //若M[i]=1,则是A[i]最大值
    endfor
    (2)计算前缀和

    定义二元结合运算*,则n个元素x[1,…,n]的前缀和是如下定义的n个部分和:

    s[i]=x[1]*x[2]*x[i],i=1,…,n

    串行计算n个元素前缀和需要O(n)的时间(利用s[i] = s[i-1] * x[i])

    下面给出SIMD-TC上的求前缀和O(logn)的算法:

    for j = 1 to n par-do
        B[0, j] = A[j]  //平衡树底层是n个元素    
    endfor                                  //O(1)
    
    for h = 1 to logn do                    //正向遍历,父节点存所有字节点之和
        for j = 1 to n/2^h par-do
            B[h,j]=B[h-1,2j-1]*B[h-1,2j]    //父节点存子节点之和
        endfor                              //O(1)
    endfor                                  //共logn层,则总时间O(logn)
    
    for h = logn to 0 do
        for j = 1 to n/2^h par-do
            if j % 2 == 0 then      //该节点是右儿子
                C[h,j]=C[h+1,j/2]   //右儿子等于父节点的值
            else if j == 1 then
                C[h,j]=B[h,1]       //每一层第一个节点等于B树上对应值
            else                    //该节点是左儿子
                C[h,j]=C[h+1,(j-1)/2]*B[h,j]    //叔节点和\*自身和
            endif
        endfor
    endfor

    6.4 倍增设计技术

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

    (1)表序问题

    n个元素的序列L,每个元素分配一个处理器,给定k求出L[k]的rank(k)值,rank(k)等于其到表尾的距离

    每个元素有一个指向下一个元素的指针next(k)

    下面给出SIMD-EREW上求元素表序的算法:

    for k in L par-do
        p(k) = next(k)
        if p(k) != k then
            distance(k)=1
        else
            distance(k)=0
        endif
    endfor                  //O(1)完成distance初始化
    
    repeat t = ceil(logn) times
        for k in L par-do
            if p(k)!=p(p(k)) then //不是到数第2个
                distance(k) += distance(p(k))   //把next的dis加到自己上来
                p(k)=p(p(k))    //next倍增
            endif
        endfor
    
        for k in L par-do
            rank(k)=distance(k)     //为什么每次都去赋值rank不最后赋值一次?
        endfor
    
    endrepeat               //O(logn)
    
    (2)求森林的根

    森林是一组有根有向树,找森林的根就是求出所有节点所在的树的根节点

    可以用倍增技术去修改每个节点的后继(后继即是父节点),下面是SIMD-CREW上的求森林根算法:

    for i = 1 to n par-do
        s[i] = p[i]
        while s[i] != s[s[i]] do    //该节点不是根
            s[i] = s[s[i]]          //指向父节点
        endwhile                    //这个while不需要同步吗?
    endfor                          //O(logn)

    6.5 流水线技术

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

    (1)五点的DFT计算

    计算DFT时引入Horner法则把任务划分成流水段:
    这里写图片描述

    O(n)的时间即可完成DFT计算

    (2)4流水线编程实例

    老师举出一个可流水化的矩阵赋值的例子,意义不是很大,略

    展开全文
  • 第二篇为并行计算理论基础:并行算法,分为上篇和下篇,其中上篇为并行算法设计,包括并行算法的基础知识与并行计算模型、并行算法基本设计策略、常用设计技术和一般设计过程;下篇为并行数值算法,包括稠密矩阵运算...
  • 并行计算及并行算法

    万次阅读 多人点赞 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编程

    展开全文
  • 算法---->并行算法

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

    并行算法

    一、并行算法

    什么是并行算法? 它可理解为: 适合于在某类并行计算机上求解问题和处理数据的算法, 是一些可同时执行的诸进程的集合, 这些进程相互作用和协调作用, 从而达到对给定问题的求解。

    二、并行计算机

    并行处理就是把一个传统串行处理的任务分解开来, 并将其分配给多个处理器同时处理, 即在同一时间间隔内增加计算机的操作数量。为并行处理所设计的计算机称为并行计算机。

    三、Flynn 分类法

    它首先按指令流的重数将机器分为二类: SI ( SingleInstruction Stream)单指令流; MI (Multiple Instruction Stream)多指令流。

    其次, 按操作数流的重数加以区分:SD (Single Data Stream)

    单数据流;MD (Multiple Data Stream) 多数据流。这样, 就有4 种可能的组合, 即SISD,SIMD, MISD, MIMD。

    1. SISD: SISD计算机代表如今使用的大多数串行计算机, 是单指令流对单数据流进行操作。
    2. SIMD SIMD 计算机是所谓的阵列机, 它有许多个处理单元(PE) , 由同一个控制部件管理, 所有PE 都接收控制部件发送的相同指令, 对来自不同数据流的数据集合序列进行操作。
    3. MISD: MISD 计算机从概念上讲, 则有多个PE, 接收不同的指令, 对相同数据进行操作, 一般认为MISD机目前尚无实际代表, 此类结构很少受到人们的注意。
    4. MIMD: MIMD 计算机包括多处理机和多计算机两类, 它们都由可各自执行自己程序的多处理器组成。其中, 多处理机以各处理器共享公共存储器为特征, 而多计算机以各处理器经通信链路传递信息为特征。它们与SIMD计算机的根本区别在于:SIMD 机中每台处理器只能 执行中央处理器的指令, 而MIMD机中每台处理器仅接受中央处理器分给它的任务, 它执行自己的指令, 所以可达到指令、任务并行。

    四、并行计算机分类

    根据Flynn 分类法, 通用的并行计算机分为SIMD机和MIMD机两大类, 它们是并行算法的物质基础。这两大类还可进一步细分,SIMD 模型可细分为基于共享存储的SIMD 模型和基于互连网络的SIMD模型;MIMD 模型主要可细分为基于共享存储的MIMD 模型和基于异步通信的互连网络模型。

    4.1、SIMD 共享存储模型

    SIMD 共享存储模型是假定有有限或无限个功能相同的处理器, 每个处理器拥有简单的算术运算和逻辑判断能力, 在理想的情况下假定存在一个容量无限大的共享存储器, 在任何时刻, 任意一个处理器均可通过共享存储器的共享单元同其它任何处理器互相交换数据。

    由于实际情况是共享存储器的容量是有限的, 因此在同一时刻, 当多个处理器访问同一单元时就会发生冲突。根据模型解决冲突的能力,SIMD 共享存储模型又可进一步分为

    (1) 不容许同时读和同时写。即每次只允许一个处理器读和写一个共享单元, 这种模型简记为SIMD-EREWPRAM。

    (2) 容许同时读, 但不容许同时写。即每次允许多个处理器同时读一个共享单元的内容, 但每次只允许一个处理器向某个共享单元写内容, 这种计算模型简记为SIMD-CREW PRAM。

    (3) 允许同时读和写。即每次容许任意多个处理器同时读和同时写同一个共享存储单元, 这种计算模型简记为SIMD-CRCWPRAM。

    4.2、SIMD 互连网络模型

    在SIMD 互连网络模型中, 每个处理器在控制器控制下或处于活动状态, 或处于不活动状态。活动状态的处理器都执行相同的指令, 处理器之间的数据交换是通过互联网络进行的。根据互连网络的连接方式,SIMD 互连网络模型又分为两类。一类是处理器-处理器之间直接互连(称为闺房式)  另一类是处理器-存储器之间直接互连(称为舞厅式) ,

    4.3、MIMD共享存储模型

    在共享存储的MIMD 计算模型中, 所有的处理器共享一个公共的存储器, 每个处理器各自完成自己的任务, 各处理器之间的通信是通过共享存储器中的全局变量来实现的。在这种模型上开发的算法称之为异步并行算法。

    4.4、MIMD 互连网络模型

    在基于互连网络的MIMD 计算模型中, 处理器之间不存在共享存储器, 每个处理器从各自存储器中存取指令和数据。各处理器之间用通信网络以信息方式交换数据。在此模型上设计的算法称为分布式算法。

    在基于互连网络的模型中,由于数据分布存储,信息通过互连网络进行传递,因此算法与处理器互联的拓扑结构紧密相关,

    五、一些常用的互连网络的拓扑结构

    5.1. 一维线性连接

    此连接方式是所有并行机中处理器之间一种最简单的互连方式。其中每个处理器只与其左右近邻相连(头尾处理器除外) ,

    5.2.二维网孔连接

    在此连接方式中处理器之间按二维阵列形式排列, 每个处理器仅与4 个相邻处理器(若有的话) 互连,

    5.3. 超立方连接

    对于N =2K个处理器, 可将其组织成一个k-维超立方连接。首先, 处理器按0 ,1 , 2 , ⋯ ,2K-1 依次编号, 然后, 处理器之间按下述方式连接: 处理器i 与处理器j 有线连接当且仅当i与j 的二进制表示中仅一位不同。下图给出了k =4 的四维超立方连接方式。

    5.4. 树形连接方式

    树形连接方式是利用二叉树这种常用的数据结构组织而成的。对于一棵有d 级( 编号由根至叶为0 到d -1 ) 的满二叉树, 每个结点表示一个处理器, 因此, 对于一个具有d级的树形连接方式, 共有n =2d- 1个处理器组成。在此结构中, 处理器的工作方式通常是: 叶子结点对数据进行计算, 而内部结点仅负责叶子结点间的通信及简单的逻辑运算。下图为出d =4 的树形连接结构。

    5.5. 洗牌-交换连接方式

    洗牌-交换是一类非常有用的互连结构。对于n =2k处理器, 将它们按0 ,1 , 2 , ⋯ , 2k - 1编号, 设处理器i的二进制表示为ik -1 , ik - 2 , ⋯ , i1 , i0 。

    下面定义洗牌与交换二个连接函数:

    SH ( ik - 1 ik -2 ⋯i0 ) =ik - 2 ik -3 ⋯i0 ik -1

    EX ( ik - 1 ik -2 ⋯i1 i0 ) =ik - 1 ik -2 ⋯i1 i0

    其中, i0 = 1- i0 。在此连接方式中, 处理器i 与二进制表示为ik -2 ik - 3 ⋯i0 ik -1 或ik -1 ik - 2 ⋯i1 i0的处理器相连。下图给出了n = 23的洗牌-交换连接结构, 其中实线表示EX 函数, 虚线表示SH 函数。

    六、并行算法的复杂性

    在SIMD 计算模型上的并行算法, 其复杂性是指, 在最坏情况下, 算法的运行时间T(n)和所需的处理机的数目P(n), 其中n 为问题的规模, 其复杂性度量是确定T(n)和P(n)的上界。

    在MIMD 计算模型上, 对于基于共享存储的并行算法, 其复杂性度量与SIMD模型上的并行算法基本一致。

    而对于异步通信的分布式计算模型,其算法复杂性衡量标准主要有两个,一个是在最坏情况下算法的运算时间, 另一个是在最坏情况下算法的通信复杂性,即在最坏情况下算法在整个执行期间所传送的消息总数目。在分析算法的运算时间时, 必须考虑通信时间, 由于处理机之间传递的消息到达目的地的时间通常不易确定。例如, 一则消息可能因通信链路被占用而需先等待。因此要想精确地分析算法的运算时间就变得非常困难。目前, 估计算法的运算时间都是假定邻接处理机之间的通信可在O(1)时间内完成这一假定基础上得出的, 不考虑信息的等待时间。在基于异步通信的分布式计算机模型中,并行算法复杂性是以通信复杂性为主要衡量标准,其次才是算法的运算时间。

    七、并行算法的性能评价

    7.1、并行算法的成本C(n)

    并行算法的成本C(n) 定义为并行算法的运算时间T (n)与并行算法所需处理机数目P(n)的乘积, 即

    C(n) = T(n)·P(n)

    7.2、加速(又称加速比)Sp(n)

    对一个求解问题, 令Ts(n)是最快的串行算法在最坏的情况下的运算时间, Tp(n) 是求解此问题的某一并行算法在最坏情况下的运算时间, 则此并行算法的加速Sp(n) 可定义为

    Sp(n) = Ts(n)/Tp(n)

    由定义可看出, 并行算法的加速反映了该算法的并行性对运算时间的改善程度。Sp(n)越大, 则并行算法越好。由于任何并行算法都能在一台串行机上模拟实现, 因此Tp(n)·P (n)≥Ts(n), 从而

    1≤Sp(n)≤P(n)当Sp(n)= P(n) 时, 则具有这样加速比的并行算法为最优的并行算法。由于在通常情况下,一个问题不可能分解成P(n)个具有相同执行步数并且可以并行执行的子问题, 因此, 要达到Sp (n)=P(n)几乎是不可能的。

    7.3、并行算法的效率Ep(n)

    并行算法的效率可定义为算法的加速与处理机数目之比, 即

    Ep(n) = Sp(n)/ P(n)

    并行算法的加速不能反应处理机的利用率, 一个并行算法的加速可能很大, 但处理机的利用率却可能很低。并行算法的效率反映了在执行算法时处理机的利用情况。由于1≤Sp (n)≤P(n), 故0 <Ep(n)≤1

    若一个并行算法的效率等于1 , 则说明在执行此算法的过程中每台处理机的能力得到了充分发挥。此时, Sp(n)=P(n), 因此, 此并行算法的串行模拟是求解问题的最佳串行算法。当然, 要达到Ep (n)= 1 几乎是不可能的。

    八、并行算法设计

    对于某一求解问题, 在设计并行算法时, 一般可采用3 种途径:

    (1) 把已有的串行求解算法进行改造, 挖掘开发串行算法中固有的并行性, 使之适合于在并行计算机上运行。

    (2) 从求解问题本身出发, 分析和改造求解问题中运算操作之间的相互关系和数据的相关性, 将问题划分成若干个能彼此并行执行的子问题。在此途径中, 应尽量采用一些像分治策略那样具有并行思想的设计策略。

    (3) 借鉴和改造求解类似问题的并行算法, 产生求解本问题的并行算法。

    在设计并行算法时, 要注意以下几点。

    (1 ) 并行算法依赖于计算模型: 一个并行算法的性能在不同的计算模型上差别很大。这有时候是由于通信开销所致, 但有时候是由于别的因素所致。例如, 为了实现同步, 在MIMD计算模型上需要通过很费时间的软件来实现。因此,小粒度(同步之间执行很少步运算)算法不适合在MIMD共享存储模型上运行

    (2 ) 在存储分布模型上必须考虑通信成本: 在基于存储共享的计算模型上, 由于处理机之间的通信是通过全局共享存储变量完成的, 因此通信开销可忽略不计。在存储分布计算模型上, 数据通过互连网络从一个处理机传送到另一个处理机的开销可能很大( 须经很多中

    间结点) , 因此, 有时候算法的通信复杂性比计算复杂性还要高, 也就是说, 通信所花费的时间比实际处理、变换所花费的时间还要长。

    (3 ) 算法与数据的存储分布有关: 在互连网络计算模型中, 算法与数据分布密切相关,例如, 在单指令流的互连网络模型中, 数据存储分布的好坏直接影响算法的并行性; 在多指令流的互连网络模型中, 数据存储分布的好坏直接影响算法的通信开销。

    九、并行算法描述

    (1)

    for each i1 ,  i2 , ⋯ , ik :  P pardo

      ……

    endfor

     

    此语句表示编号为i1 , i2 , ⋯ , ik 的处理机, 若满足谓词P 为真, 则执行循环体的指令序列。要

    用于描述SIMD 模型中的并行算法。

    (2)

    upon r eceiving  M message from u do

          ……

    此语句表示执行结点一旦收到来自结点u的消息M后, 就执行相应的操作。

    (3)

    send M message  to k

    此语句表示执行结点把信息M传送给k。

    展开全文
  • 并行程序的编程模型、运行环境、调试环境等都要比串行程序复杂...并行算法研究要以硬件,即并行计算机为依托,并行计算机性能的发挥要依靠优秀并行算法设计的实现。所以本文,并行算法研究现状及其相关问题的综述,将
  • 三对角系统并行算法的研究概况

    千次阅读 2009-12-18 10:07:00
    【摘 要】在科学和工程计算中,许多问题往往归结为三对角线性方程组的求解,其并行算法的研究具有重要意义。文章全面总结了当前求解三对角线性方程组的两类并行算法:直接解法和迭代解法,并介绍了其特点。【关键词...
  • 第二篇包括并行算法的一般设计策略基本设计技术和一般设计过程;第三篇包括矩阵运算、稠密与稀疏线性方程组的求解和快速傅里叶变换;第四篇包括并行程序设计基础、共享存储与分布存储系统 并行编程以及并行程序...
  • 用C++ 17并行算法实现更好的性能 作者:Billy 2018年9月11日 这篇文章是微软的C++产品团队和其他客人回答我们从客户那里收到的问题的一系列常规文章的一部分。这些问题可以是任何C++相关的:MSVC工具集,标准语言和库...
  • 第二篇包括并行算法的一般设计策略基本设计技术和一般设计过程;第三篇包括矩阵运算、稠密与稀疏线性方程组的求解和快速傅里叶变换;第四篇包括并行程序设计基础、共享存储与分布存储系统 并行编程以及并行程序...
  • 第二篇包括并行算法的一般设计策略基本设计技术和一般设计过程;第三篇包括矩阵运算、稠密与稀疏线性方程组的求解和快速傅里叶变换;第四篇包括并行程序设计基础、共享存储与分布存储系统 并行编程以及并行程序...
  • 第一章 1、并行计算的定义和主要目的 定义:并行计算是指同时对多个任务或多条指令、或对多个数据项进行处理。完成此项处理的计算机系统称为并行计算机系统,它是将多个处理器(可以几个、几十...(2)有效算法设计 (3
  • 并行遗传算法解决TSP问题

    千次阅读 2018-01-17 20:33:35
    并行遗传算法解决TSP问题一、问题描述旅行商问题(TSP)可简单描述为:一位销售商从n个城市中的某一城市出发,不重复地走完其余n-1个城市并回到原出发点,在所有可能路径中求出路径长度最短的一条。旅行商的路线可以...
  • 并行遗传算法及其应用

    千次阅读 2009-03-16 13:26:00
    1、遗传算法(GA)概述 GA是一类基于自然选择和遗传学原理的有效搜索方法,它从一个种群开始,利用选择、交叉、变异等遗传算子对种群进行不断进化,最后得到全局最优解。生物遗传物质的主要载体是染色体,在GA中...
  • 因此,本文基于异构负载的特点,基于可分负载理论,采用LIFO的通信策略,单纯形通信模型,基于Needleman-Wunsch的双序列全局比对并行算法进行设计,提出了该策略。划分分数数据矩阵,确定最佳的迭代次数并分配给子...
  • 下面开始介绍一些在Alpha-Beta算法中引入并行化的方法和算法. 6.1 并行求值(Parallel Evaluation) 游戏的博弈程序经常要在搜索深度和叶结点的求值复杂度之间进行平衡.一些博弈程序,使用简化的估值函数,以获得更...
  • 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...
  • 算法设计的方法

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

    千次阅读 2017-10-12 15:52:55
    算法设计的整个过程,可以包含对问题需求的说明、数学模型的拟制、算法的详细设计算法的正确性验证、算法的实现、算法分析、程序测试和文档资料的编制。  算法设计的先驱者唐纳德。E。克努特对算法的特征做了如下...
  • 算法设计与分析基础

    千次阅读 2016-12-21 11:59:15
    To All Of You:一个人在接受科技教育时能得到的最珍贵的收获是能够终身受用的通用智能工具。在讨论算法的书籍中,一般会采用两种...其缺点在于,由于过于强调问题的类型,它忽略了对算法设计技术的讨论。2.第二种方
  • 并行编程的设计模式

    千次阅读 2014-12-04 10:06:20
    这篇文章是对这段时间学习并行编程中的设计模式的一个总结。有不当之处,希望得到大家的批评、指正。 首先,所谓“并行编程中的设计模式”(patterns in parallel programming)仍处于不断的被发现、发掘的阶段。...
  • 在Alpha-Beta算法被广泛运用后,对该算法的很多改进算法也相继被提出.这些改进算法主要在以下几个方面对Alpha-Beta算法进行改进[7]: 1. 择序(ordering).在搜索博弈树时,内部结点有多个可能的移动.择序指的是搜索...
  • 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 拍卖策略 ...
  • 插入排序算法介绍 算法逻辑 伪代码 复杂度
  • 进程调度算法设计

    千次阅读 2019-08-06 19:10:29
    在进程管理中,进程调度是核心,因为在采用多道程序设计的系统中,往往有若干个进程同时处于就绪状态,当就绪进程个数大于处理器数目时,就必须依照某种策略决定哪些进程优先占用处理器。本实验模拟在单处理器情况下...
  • Intel TBB提供的大多数并行算法支持泛型。但是这些受支持的类型必须实现必要的概念方法。并行算法可以嵌套, 例如,一个parallel_for的内部可以调用另一个parallel_for。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 51,431
精华内容 20,572
关键字:

并行算法的基本设计策略