第十六章 并行算法.ppt

《第十六章 并行算法.ppt》由会员分享，可在线阅读，更多相关《第十六章 并行算法.ppt（38页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第十六章第十六章 并行算法并行算法n 并行处理技术就是只把一个处理任务分配给多并行处理技术就是只把一个处理任务分配给多个处理器同时处理，这样可以使得在一个时刻计个处理器同时处理，这样可以使得在一个时刻计算机的计算量增加算机的计算量增加n倍。为并行处理所涉及的计算倍。为并行处理所涉及的计算机称为并行计算机，随着网络的发展，我们可以机称为并行计算机，随着网络的发展，我们可以利用网络上各个点的资源联合进行分布式计算。利用网络上各个点的资源联合进行分布式计算。所谓分布式计算是一门计算机科学，它研究如何所谓分布式计算是一门计算机科学，它研究如何把一个需要非常巨大的计算能力才能解决的问题把一个需要非常巨大

2、的计算能力才能解决的问题分成许多小的部分，然后把这些部分分配给许多分成许多小的部分，然后把这些部分分配给许多计算机进行处理，最后把这些计算结果综合起来计算机进行处理，最后把这些计算结果综合起来得到最终的结果。得到最终的结果。2022/12/231第十六章第十六章 并行算法并行算法目录目录16.1 并行计算机并行计算机 16.2 并行算法的基本概念并行算法的基本概念 16.3 并行算法的描述并行算法的描述 16.4 SIMD-SM上的非线性方程求根同步并行算上的非线性方程求根同步并行算法法 16.5 SIMD-SM上的同步并行求和算法上的同步并行求和算法 16.6 SIMD-CC超立方机器上的同

3、步并行求和算超立方机器上的同步并行求和算法法 16.7 MIMD-SM上的异步并行求和算法上的异步并行求和算法 2022/12/23216.1 并行计算机并行计算机n串行机和并行机都是依据指令对数据进行操作，串行机和并行机都是依据指令对数据进行操作，Flynn分类法就分类法就是根据指令流和数据流的个数将计算机分为是根据指令流和数据流的个数将计算机分为4类：类：(1)单指令流单数据流（单指令流单数据流（Single Instruction Stream,Single Data Stream），简写成），简写成SISD，它是指单指令流对单数据流进行，它是指单指令流对单数据流进行操作；操作；(2)多

4、指令流单数据流（多指令流单数据流（Multiple Instruction Stream,Single Data Stream），简写成），简写成MISD,它有很多个处理器，但是由一个它有很多个处理器，但是由一个控制部件管理，一个数据流被传送给一组处理器，通过处理器上控制部件管理，一个数据流被传送给一组处理器，通过处理器上不同指令操作最终得到处理结果；不同指令操作最终得到处理结果；(3)单指令流多数据流（单指令流多数据流（Single Instruction Stream,Multiple Data Stream），简写成），简写成SIMD，是指多个处理器接收不同的指，是指多个处理器接收不同的

5、指令对相同数据进行操作令对相同数据进行操作；(4)多指令流多数据流（多指令流多数据流（Multiple Instruction Stream,Multiple Data Stream），简写成），简写成MIMD，它使用多个控制器来异步地控，它使用多个控制器来异步地控制多个处理器，从而实现空间上的并行性制多个处理器，从而实现空间上的并行性。2022/12/23316.1 并行计算机并行计算机nMIMD与与SIMD计算机的区别计算机的区别：SIMD计算机中每台处理器只能执行中央处理器的指计算机中每台处理器只能执行中央处理器的指令，而令，而MIMD计算机中每台处理器只是接受中央处理计算机中每台处理器

6、只是接受中央处理器分配的任务，每台处理器各自执行自己的指令，从器分配的任务，每台处理器各自执行自己的指令，从而达到空间上的并行性。而达到空间上的并行性。n图图16.1、16.2、16.3、16.4分别依次表示了分别依次表示了SISD、MISD、SIMD和和MIMD的结构情况。的结构情况。控制器控制器处理器处理器存储器存储器指令流指令流数据流数据流图图16.1 SISD2022/12/23416.1 并行计算机并行计算机控制器控制器1控制器控制器2控制器控制器3处理器处理器1存储器存储器处理器处理器2指令流指令流处理器处理器3指令流指令流指令流指令流数据流数据流图图16.2 MISD 2022/

7、12/23516.1 并行计算机并行计算机控制器控制器处理器处理器1处理器处理器2处理器处理器n数据流数据流1数据流数据流n数据流数据流2 公共存储器公共存储器指令流指令流图图16.3 SIMD2022/12/23616.1 并行计算机并行计算机控制器控制器1控制器控制器2控制器控制器n处理器处理器1处理器处理器2处理器处理器n 公共存储器公共存储器指令流指令流1指令流指令流2指令流指令流n数据流数据流1数据流数据流2数据流数据流n图图16.4 MIMD 2022/12/23716.1 并行计算机并行计算机n根据根据Flynn分类法，并行计算机主要分为分类法，并行计算机主要分为SIMD和和MI

8、MD两类。两类。nSIMD模型还可细分为给予共享存储的模型还可细分为给予共享存储的SIMD模型和基于互连模型和基于互连网络的网络的SIMD模型。模型。nMIMD模型也可细分为基于共享存储的模型也可细分为基于共享存储的MIMD模型和基于异步模型和基于异步通信的互连网络模型。通信的互连网络模型。nSIMD共享存储型的每个处理器都是有独立算术运算能力和共享存储型的每个处理器都是有独立算术运算能力和逻辑判断能力的，然后每个处理器之间的信息交流都是通过逻辑判断能力的，然后每个处理器之间的信息交流都是通过一个共享存储器，比如处理器一个共享存储器，比如处理器i要送一个数据给处理器要送一个数据给处理器j，那，

9、那么首先要把该数据写到存储器上的某个地址，处理器么首先要把该数据写到存储器上的某个地址，处理器j再从这再从这个地址中读这个数据，但是因为共享存储器的容量是有限的，个地址中读这个数据，但是因为共享存储器的容量是有限的，如果在同一时刻，多个处理器一起访问同一处理单元时就会如果在同一时刻，多个处理器一起访问同一处理单元时就会发生冲突，所以共享存储模型根据解决冲突的能力还可以分发生冲突，所以共享存储模型根据解决冲突的能力还可以分为为3类：类：(1)EREW(Exclusive-Read Exclusive-Write),即不允许有即不允许有两个处理器同时读或写一个共享单元；两个处理器同时读或写一个共享

10、单元；2022/12/23816.1 并行计算机并行计算机 (2)CRCW(Concurrent-Read Exclusive-Write)可允许同时可允许同时读，但不允许同时写，即允许两个处理器同时读一个共享单元，读，但不允许同时写，即允许两个处理器同时读一个共享单元，但只允许一个处理器写某个共享单元；但只允许一个处理器写某个共享单元；(3)ERCW(Exclusive-Read Concurrent-Write)不允许同时不允许同时读，但允许同时写；读，但允许同时写；(4)CRCW(Concurrent-Read Concurrent-Write)允许同时允许同时读和同时写；读和同时写；n

11、共享存储的共享存储的MIMD计算模型中所有的处理器也是共享一个公共计算模型中所有的处理器也是共享一个公共的存储器，处理器之间的信息交流也是通过公共存储器来完成的存储器，处理器之间的信息交流也是通过公共存储器来完成的。的。n在基于互连网络的在基于互连网络的MIMD计算模型中，每个处理器都各自有自计算模型中，每个处理器都各自有自己的存储器的（数据都是来自各自的存储器的），信息是通过己的存储器的（数据都是来自各自的存储器的），信息是通过互连网络进行交流的，在这种模型上设计的算法与互连网络的互连网络进行交流的，在这种模型上设计的算法与互连网络的拓扑结构有关，我们介绍几种比较常见的拓扑结构。拓扑结构有关

12、，我们介绍几种比较常见的拓扑结构。2022/12/23916.1 并行计算机并行计算机1、一维线性结构、一维线性结构 这是最简单的连接方式，其中这是最简单的连接方式，其中N个处理器用个处理器用N-1条条链路连成一行，每个处理器只与其左右紧邻的处理相链路连成一行，每个处理器只与其左右紧邻的处理相连接。如图连接。如图16.5所示：所示：2、二维网格结构、二维网格结构 处理器之间按二维阵列形式排列，每个处理器仅与处理器之间按二维阵列形式排列，每个处理器仅与4个相邻处理器连接，个相邻处理器连接，16个处理器，相应的二维网格个处理器，相应的二维网格结构如图结构如图16.6图图16.5 一维线性结构一维线

13、性结构 2022/12/231016.1 并行计算机并行计算机n二维网格结构是一种常用的并行机，特别适用于处理二维二维网格结构是一种常用的并行机，特别适用于处理二维问题。问题。图图16.6 二维网格结构二维网格结构2022/12/231116.1 并行计算机并行计算机3、超立方连接结构、超立方连接结构 一般来说，一个一般来说，一个n-立方体由立方体由N=2n个结点组成，它们个结点组成，它们分布在分布在n维上，每维有两个结点，特别地，当维上，每维有两个结点，特别地，当n=3时就是人们时就是人们所熟悉的立方体。处理器在按照超立方体结构连接时要以下所熟悉的立方体。处理器在按照超立方体结构连接时要以下

14、式方式连接：当处理器式方式连接：当处理器i个处理器个处理器j有线连接时当且仅当有线连接时当且仅当i与与j的的二进制表示中仅一位不同。二进制表示中仅一位不同。4-立方体可通过将立方体可通过将2个个3-立方体的相应结点互连组成，立方体的相应结点互连组成，如图如图16.7。图图16.7超立方连接结构超立方连接结构2022/12/231216.1 并行计算机并行计算机4、树形连接方式、树形连接方式 二叉树具有很多优良性质，树形连接方式就是利用二叉树这二叉树具有很多优良性质，树形连接方式就是利用二叉树这种常用的数据结构组织而成的，一颗种常用的数据结构组织而成的，一颗4层层15个结点的树形连接个结点的树形

15、连接方式结构如图方式结构如图16.8。图图16.8树形连接方式树形连接方式 2022/12/231316.1 并行计算机并行计算机5、洗牌、洗牌-交换连接方式交换连接方式 洗牌洗牌-交换是一种非常有用的互连网络，假设交换是一种非常有用的互连网络，假设N=2n，交换置换实现二，交换置换实现二进制地址编号中第进制地址编号中第0位位填不同的输入端和输出端之间的连接，其表位位填不同的输入端和输出端之间的连接，其表达式为：达式为：EX（xn-1xn-2x1x0）=xn-1xn-2x1 洗牌置换是将输入端分成数目相等的两半，前一半和都一般按序一个洗牌置换是将输入端分成数目相等的两半，前一半和都一般按序一个

16、隔一个地从头至尾一次与输出端相连，其表达式为：隔一个地从头至尾一次与输出端相连，其表达式为：SH（xn-1xn-2x1x0）=xn-2x1x0 xn-1 图图16.9为处理器数为处理器数N=8的洗牌的洗牌-交换万罗，其中虚线表示置换，实线表交换万罗，其中虚线表示置换，实线表示洗牌。示洗牌。01234567图图16.9 处理器数处理器数N=8的洗牌的洗牌-交换交换 返回目录返回目录2022/12/231416.2 并行算法的基本概念并行算法的基本概念n并行算法就是在某类可以同时执行并行算法就是在某类可以同时执行n个进程的并行计算个进程的并行计算机上求解问题，并且这些进程之间可以互相交换信息，机上

17、求解问题，并且这些进程之间可以互相交换信息，从而可以更快地完成某个问题的求解。从而可以更快地完成某个问题的求解。n可以从不同的角度将并行算法分为数值算法和非数值可以从不同的角度将并行算法分为数值算法和非数值算法，算法，SIMD并行算法和并行算法和MIMD并行算法等等。并行算法等等。n数值并行算法是指基于代数运算的一类计算问题的求数值并行算法是指基于代数运算的一类计算问题的求解算法，如矩阵运算、多项式求值等等。解算法，如矩阵运算、多项式求值等等。n非数值并行算法是指基于关系运算的一类计算问题的非数值并行算法是指基于关系运算的一类计算问题的求解算法，如排序、搜索等。求解算法，如排序、搜索等。n算法

18、复杂性和算法的评价算法复杂性和算法的评价：并行算法可以用不同的标准度量，对我们来说最主要并行算法可以用不同的标准度量，对我们来说最主要的是算法与求解问题规模之间的关系，所以对于并行的是算法与求解问题规模之间的关系，所以对于并行算法除了研究运行时间还要研究执行该算法所需的处算法除了研究运行时间还要研究执行该算法所需的处理器的数目。理器的数目。2022/12/231516.2 并行算法的基本概念并行算法的基本概念 设设T是运行时间，是运行时间，n是处理器的规模，那么是处理器的规模，那么T与与n之间的关之间的关系为系为T=T(n).其中其中T包含了两部分的时间，其中一部分是指通信包含了两部分的时间，

19、其中一部分是指通信时间，即处理器之间通过互联网络传递消息到达目的地的时间。时间，即处理器之间通过互联网络传递消息到达目的地的时间。消息很可能由于通信链路被占用而需要等待较长的时间，但我消息很可能由于通信链路被占用而需要等待较长的时间，但我们通常假设处理器之间的通信可以在们通常假设处理器之间的通信可以在O(1)的时间内完成，还有的时间内完成，还有一部分的时间为数据在处理器进行运算的时间，就是通常所说一部分的时间为数据在处理器进行运算的时间，就是通常所说的算法的运行时间。的算法的运行时间。n性能指标性能指标 1、并行算法的代价、并行算法的代价C（n）并行算法的代价定义为并行算法的运算时间并行算法的

20、代价定义为并行算法的运算时间T（n）与并行算）与并行算法所需的处理器数目法所需的处理器数目P（n）的乘积，即）的乘积，即 C（n）=T（n）P（n）它相当于在最坏情况下求解一个问题所有它相当于在最坏情况下求解一个问题所有P（n）台所执行的）台所执行的总的运行时间。如果在该并行算法的执行代价的数量级为最坏总的运行时间。如果在该并行算法的执行代价的数量级为最坏情况下床性求解此问题的所需的运行时间，那么称这样的并行情况下床性求解此问题的所需的运行时间，那么称这样的并行算法为代价最优的并行算法。算法为代价最优的并行算法。2022/12/231616.2 并行算法的基本概念并行算法的基本概念2、加速比、

21、加速比Sp（n）假设假设Ts（n）是最快是串行算法在最坏情况下的执行时）是最快是串行算法在最坏情况下的执行时间，间，Tp（n）为并行算法在最坏情况下的运行时间，那么加速）为并行算法在最坏情况下的运行时间，那么加速比可以定义为比可以定义为 Sp（n）=Ts（n）/Tp（n）Sp（n）表示并行算法对求解该问题的运行时间的改进程度，）表示并行算法对求解该问题的运行时间的改进程度，Sp（n）越大表示并行算法越好。在理想的情况下，用）越大表示并行算法越好。在理想的情况下，用P（n）台处理器去并行求解问题等于用一台处理器求解同一）台处理器去并行求解问题等于用一台处理器求解同一个问题乘以个问题乘以P（n）台

22、。事实上，这两者之间是不可能相等的，）台。事实上，这两者之间是不可能相等的，这其中有很多因素，比如说在进行并行算法过程中数据需要经这其中有很多因素，比如说在进行并行算法过程中数据需要经过一个互连网络才能到达另一个处理器，在经过互连网络时会过一个互连网络才能到达另一个处理器，在经过互连网络时会消耗掉一部分的时间，因此消耗掉一部分的时间，因此 T（n）P（n）Ts（n），），从而有从而有 1 Sp（n）P（n）2022/12/231716.2 并行算法的基本概念并行算法的基本概念3、并行算法的效率、并行算法的效率Ep（n）并行算法的效率可以定义为算法的加速比与处理器数目之并行算法的效率可以定义为算

23、法的加速比与处理器数目之比，即比，即 Ep（n）=Sp（n）/P（n）0 Ep（n）1 并行算法有好的加速比不一定该处理器的利用率就很高，并行算法有好的加速比不一定该处理器的利用率就很高，特别是在处理器数目不固定的情况下，因此并行算法的加速特别是在处理器数目不固定的情况下，因此并行算法的加速比不能很好地反应出处理器的利用率。所以人们引入了并行比不能很好地反应出处理器的利用率。所以人们引入了并行算法效率的概念，算法效率的概念，Ep（n）可以反应出处理器的利用率。）可以反应出处理器的利用率。当当Ep（n）=1时，则时，则Sp（n）=P（n），），说明每台处理器都得到了充分的发挥，所以次并行算法的说

24、明每台处理器都得到了充分的发挥，所以次并行算法的串行模拟为最佳串行算法，事实上串行模拟为最佳串行算法，事实上Ep（n）=1几乎是不可能几乎是不可能的。的。返回目录返回目录2022/12/231816.3 并行算法的描述并行算法的描述n并行算法的算法描述与串行算法一样，但是并行算法并行算法的算法描述与串行算法一样，但是并行算法除了可以使用串行算法的语句、函数和过程调用以外，除了可以使用串行算法的语句、函数和过程调用以外，还引入了并行操作特有的并行执行语句。还引入了并行操作特有的并行执行语句。（1）do step i to step j in parallel begin step i;step

25、i+1;step j;end 此语句表示编号为此语句表示编号为i，i+1，j的处理器并行地的处理器并行地执行算法步骤执行算法步骤step i，step i+1，step j。2022/12/231916.3 并行算法的描述并行算法的描述（2）for i=j to k parallel do begin End 此语句的意思与（此语句的意思与（1）相似表示处理器）相似表示处理器i,i+1,，k并行地执并行地执行算法步骤行算法步骤begin end里的语句。这里的里的语句。这里的“rallel do”0也也可以写成可以写成“do in parallel”。（3）upon receiving M m

26、essage from u do 此语句表示执行结点一旦收到来自此语句表示执行结点一旦收到来自u结点的消息结点的消息M后就执行后就执行相应的操作。相应的操作。（4）send M message to k此语句表示执行结点把消息此语句表示执行结点把消息M传送给传送给k。（3）（）（4）两个语句是描述互连网络模型中并行算法的通信功能。）两个语句是描述互连网络模型中并行算法的通信功能。返回目录返回目录2022/12/232016.4 SIMD-SM上的非线性方程求根同步并行算法上的非线性方程求根同步并行算法n日常生活中存在着一些计算量非常大的数值计算问题（例如天日常生活中存在着一些计算量非常大的数值

27、计算问题（例如天气预报问题），这种计算问题无法在串行机器上很快地得出结气预报问题），这种计算问题无法在串行机器上很快地得出结果，我们只有把这种计算问题应用在并行计算机上才有可能在果，我们只有把这种计算问题应用在并行计算机上才有可能在较短的时间内获得满足实际应用的需要。本小节我们主要介绍较短的时间内获得满足实际应用的需要。本小节我们主要介绍在在SIMD-SM机器上的非线性方程求根同步并行算法。机器上的非线性方程求根同步并行算法。n在科学领域内，人们时常会遇到求解在科学领域内，人们时常会遇到求解 f(x)=0（1.1）求解等计算题。像这类问题，我们无法对大部分方程精确求求解等计算题。像这类问题，我

28、们无法对大部分方程精确求解，而只能使用近似算法来求解。解，而只能使用近似算法来求解。n我们可以把方程（我们可以把方程（1.1）的根解释成函数）的根解释成函数f(x)的图像和的图像和x轴的交轴的交点。点。f(x)的图像和的图像和x轴的交点可以有一个、多个甚至无穷多个，轴的交点可以有一个、多个甚至无穷多个，或者是没有交点。或者是没有交点。n平分法算法平分法算法：1)如果一个连续函数的图像在如果一个连续函数的图像在a点和点和b点上取到的函数值符号点上取到的函数值符号相反，那么该函数在这两点之间至少要和相反，那么该函数在这两点之间至少要和x轴相交一次；轴相交一次；2022/12/232116.4 SI

29、MD-SM上的非线性方程求根同步并行算法上的非线性方程求根同步并行算法 2)开始的时候有一个区间开始的时候有一个区间a1,b1，在其端点上，在其端点上，f(x)的符号相反；的符号相反；3)计算计算f(x)在中点在中点c1=(a1+b1)/2上的值上的值；若若f(c1)=0，则，则c1为方程为方程f(x)=0的根的根 若若f(a1)与与f(c1)异号，即异号，即f(a1)f(c1)0，则令，则令a2,b2=a1,c1;若若f(b1)与与f(c1)异号，即异号，即f(b1)f(c1)0，则令，则令a2,b2=c1,b1。4)依次做下去，则发现依次做下去，则发现f(cn)=0时，或区间时，或区间an

30、,bn足够小时，比如足够小时，比如|an-bn|=c do begin s=(a0-b0)/(p(n)+1)；y0=f(a);yp(n)+1=f(b);for i=1 to p(n)do in parallel begin yk=f(a+k*s);if(yk+1*yk0)then begin a=a+(k-1)*s;b=a+k*s;end end;if(yp(n)*yp(n)+1 0)then a=a+p(n)*s;end end 2022/12/232316.4 SIMD-SM上的非线性方程求根同步并行算法上的非线性方程求根同步并行算法n该并行算法的总迭代次数为该并行算法的总迭代次数为O(l

31、og p(n)+1b0-a0)，因此该并行算法的复杂，因此该并行算法的复杂性为：性为：T（n）=O(log p(n)+1b0-a0)n所以并行算法的执行代价为：所以并行算法的执行代价为：C（n）=P(n)T(n)=O(P(n)*log p(n)+1b0-a0)返回目录返回目录2022/12/232416.5 SIMD-SM上的同步并行求和算法上的同步并行求和算法n因为因为SIMD-SM共享存储器的的容量是有限的，如果在共享存储器的的容量是有限的，如果在同一时刻，多个处理器一起访问同一处理单元时就会同一时刻，多个处理器一起访问同一处理单元时就会发生冲突，所以共享存储模型根据解决冲突的能力还发生冲

32、突，所以共享存储模型根据解决冲突的能力还可以分为可以分为3类，其中的一类类，其中的一类EREW(Exclusive-Read Exclusive-Write)计算模型是不允许有两个处理器同计算模型是不允许有两个处理器同时读或写一个共享单，但是现实中我们又需要同时处时读或写一个共享单，但是现实中我们又需要同时处理同一存储单元的数据，所以我们必须解决这个问题。理同一存储单元的数据，所以我们必须解决这个问题。nSIMD-SM上的同步并行求和算法的过程中要用到一个上的同步并行求和算法的过程中要用到一个数据播送算法。假设在数据播送算法。假设在p个处理器上要同时处理共享个处理器上要同时处理共享存储器的同一

33、单元的数据存储器的同一单元的数据X，以下是在，以下是在SIMD-SM共享共享存储器中这样解决读写冲突的算法：存储器中这样解决读写冲突的算法：2022/12/232516.5 SIMD-SM上的同步并行求和算法上的同步并行求和算法n算法算法16.2 在在SIMD-SM上的数据播送算法上的数据播送算法begin 处理器处理器P1读取读取X然后将然后将X复制给共享存储器复制给共享存储器中的中的A1;for i=0 to log P-1 do for j=2i+1 to 2i+1 do in parallel 处理器处理器Pj读取读取Aj-2i然后将其复制给共然后将其复制给共享存储里中的享存储里中的A

34、j;end这个算法的时间复杂性为这个算法的时间复杂性为O(log p).n例例16.1 假设有假设有8个处理器要同时读取共享存储器中的个处理器要同时读取共享存储器中的某一存储单元数据某一存储单元数据100。2022/12/232616.5 SIMD-SM上的同步并行求和算法上的同步并行求和算法 根据算法根据算法16.2解这一例题的具体过程如下：解这一例题的具体过程如下：（1）首先定义一个长度为）首先定义一个长度为8的共享存储数组的共享存储数组A，它的初始值，它的初始值为空，然后将处理器为空，然后将处理器P1读取数据读取数据100并将并将100写入到写入到A1中；中；（2）接着，让处理器）接着，

35、让处理器P2读取数组读取数组A1中的数据然后将其写入中的数据然后将其写入A2中；中；（3）然后，处理器）然后，处理器P3和和P4分别并行地读取数据分别并行地读取数据A1和和A2并将其写入并将其写入A3A4中；中；（4）之后，处理器）之后，处理器P5、P6、P7、P8分别并行地读取数据分别并行地读取数据A1、A2、A3、A4并将其写入并将其写入 A5、A6、A7、A8 中。中。P1 P2 P3 P4 P5 P6 P7 P8 A1 A2 A3 A4 A5 A6 A7 A8初始初始 100步骤步骤1 100步骤步骤2 100 100步骤步骤3 100 100 100 100 2022/12/2327

36、16.5 SIMD-SM上的同步并行求和算法上的同步并行求和算法n在在SIMD-SM上的并行求和算法，它充分结合了数据上的并行求和算法，它充分结合了数据播送算法思想和上次累加结果的思想来进行下次的播送算法思想和上次累加结果的思想来进行下次的并行累加求和操作。具体算法如算法并行累加求和操作。具体算法如算法16.3n算法算法16.3 在在SIMD-SM上的并行求和算法上的并行求和算法begin for i=0 to log n-1 do for j=2i+1 to n do in parallel begin 处理器处理器Pj从共享存储器中读取从共享存储器中读取Aj-2i;处理器处理器Pj执行执行

37、Aj=Aj+Aj-2i;end end 从算法从算法16.3可以看出这个算法的时间复杂性是可以看出这个算法的时间复杂性是O(log n)。2022/12/232816.5 SIMD-SM上的同步并行求和算法上的同步并行求和算法n例例16.2 假设假设n=8,原始数据为原始数据为X=1,3,5,7,9,2,4,6,，试利用并行算法试利用并行算法16.3求这求这8个数据的之和。个数据的之和。(1)首先将这首先将这8个数据放在共享存储数组个数据放在共享存储数组A中。中。(2)当第一层循当第一层循i=0时，做第二层时，做第二层for循环循环j从从2开始，开始，当当j=2时，时，P2从共享存储数组中读取

38、从共享存储数组中读取A1,然后然后P2执执行加法操作行加法操作A2=A1+A2;(3)接着接着j=3时，时，P3从共享存储数组中读取从共享存储数组中读取A2，然，然后后P3执行加法操作执行加法操作A3=A3+A2,依次执行下去，依次执行下去，直到直到j=n。(4)然后跳出第二层循环继续做第一层循环然后跳出第二层循环继续做第一层循环i=1，做，做第二层循环第二层循环j=3，P3从共享存储器数组中读取从共享存储器数组中读取A1,P3执行加法操作执行加法操作A3=A3+A1,然后然后j=4，P4做做A4=A4+A2。2022/12/232916.5 SIMD-SM上的同步并行求和算法上的同步并行求和

39、算法 P1 P2 P3 P4 P5 P6 P7 P8 初始初始 1 3 5 7 9 2 4 6步骤步骤0 1 4 8 12 16 11 6 10步骤步骤1 1 4 9 16 24 23 22 21 步骤步骤2 1 4 9 16 25 27 31 37 因此经过因此经过3步操作之后，既可以得到步操作之后，既可以得到8个数据之个数据之和且存储在处理器和且存储在处理器P8上。上。返回目录返回目录2022/12/233016.6 SIMD-CC超立方机器上的同步并行求和算法超立方机器上的同步并行求和算法n假设在假设在n-维超立方模型上，维超立方模型上，n=2m,n个原始数据为个原始数据为X=x0，x1

40、，xn-1，其中，其中m为正整数，每个处理器为正整数，每个处理器Pi都可以存储局部变都可以存储局部变量量ai，下面在此模型上构造一个并行求和算法，使得算法结束，下面在此模型上构造一个并行求和算法，使得算法结束时时a0就是总和就是总和 。n对超立方体节点用二进制进行编号，要求每相邻的结点之间只对超立方体节点用二进制进行编号，要求每相邻的结点之间只有且仅有一位不同。然后将这些结点分为两类，一类是最高位有且仅有一位不同。然后将这些结点分为两类，一类是最高位的编号为的编号为0，则另一类是最高位的编号为，则另一类是最高位的编号为1，然后可以利用超立，然后可以利用超立方模型中结点相邻关系可建立二类处理器集

41、合中元素的一一对方模型中结点相邻关系可建立二类处理器集合中元素的一一对应关系，然后可以根据这种对应关系构造并行算法。应关系，然后可以根据这种对应关系构造并行算法。n算法的思想是：算法的思想是：（1）对于）对于n个处理器，首先将最最高位编号为个处理器，首先将最最高位编号为1的处理器的数的处理器的数据传送至最高位编号为据传送至最高位编号为0的处理器并进行局部求和；的处理器并进行局部求和；2022/12/233116.6 SIMD-CC超立方机器上的同步并行求和算法超立方机器上的同步并行求和算法（2）接着在）接着在n/2个处理器上，将次高位编号为个处理器上，将次高位编号为1的处理器上的数据的处理器上

42、的数据传送至次高位编号为传送至次高位编号为0的处理器并惊醒局部求和；的处理器并惊醒局部求和；（3）然后在）然后在n/4个处理器上，再将此次高位编号为个处理器上，再将此次高位编号为1的处理器上的的处理器上的数据传送至此次高位编号为数据传送至此次高位编号为0的处理器上并进行局部求和；的处理器上并进行局部求和；（4）依次进行下去直到所有的总和结果存储在处理器）依次进行下去直到所有的总和结果存储在处理器P0上。上。n例例16.3 设设X=1，2，3，4，5，6，7，8，9，7，2，3，4，5，9，6，n=16，则在，则在SIMD-CC机器上并行求取机器上并行求取16个数据之和的过程如个数据之和的过程如

43、图图16.101234567897234596图图16.10（a）2022/12/233216.6 SIMD-CC超立方机器上的同步并行求和算法超立方机器上的同步并行求和算法109579111614图图16.10（b）2022/12/233316.6 SIMD-CC超立方机器上的同步并行求和算法超立方机器上的同步并行求和算法19202121图图16.10（c）2022/12/233416.6 SIMD-CC超立方机器上的同步并行求和算法超立方机器上的同步并行求和算法4041图图16.10（d）返回目录返回目录2022/12/233516.7 MIMD-SM上的异步并行求和算法上的异步并行求和算

44、法n假设共享存储器多处理机系统有假设共享存储器多处理机系统有P个处理器，其编号为个处理器，其编号为P1，P2，Pp-1,由一个全局变量由一个全局变量total-sum存储数据的总和，存储数据的总和，每个处理器每个处理器Pi分配一个并发进程都有各自的局部变量分配一个并发进程都有各自的局部变量local-sum，该局部变量是用来存储部分数据的子和，然后将所求，该局部变量是用来存储部分数据的子和，然后将所求得的得的local-sum加到全局变量加到全局变量total-sum中。中。n很明显可以看出此算法存在存储冲突。假如说当一个进程把所很明显可以看出此算法存在存储冲突。假如说当一个进程把所求得的部分

45、数据子和求得的部分数据子和local-sum加到全局变量加到全局变量total-sum中时中时有另一个进程也要把部分的数据子和加进去，那么就会产生资有另一个进程也要把部分的数据子和加进去，那么就会产生资源冲突，这种冲突会很频繁的发生，因为全局变量总和的相加源冲突，这种冲突会很频繁的发生，因为全局变量总和的相加操作需要异步进行。操作需要异步进行。n我们通常所用的解决冲突的办法是当要访问全局变量时先首先我们通常所用的解决冲突的办法是当要访问全局变量时先首先对它进行加锁，使得其他进程无法同时使用这个资源，当访问对它进行加锁，使得其他进程无法同时使用这个资源，当访问结束后立即解锁以免耽误其他进程对其进

46、行的操作。结束后立即解锁以免耽误其他进程对其进行的操作。nMIMD-SM机器上的异步并行求和其实是一个进程和机器上的异步并行求和其实是一个进程和P个并发个并发子进程组成，每个子进程分别求出分配给他的子进程组成，每个子进程分别求出分配给他的n/p个数据的子个数据的子和。和。2022/12/233616.7 MIMD-SM上的异步并行求和算法上的异步并行求和算法n 算法算法16.5 MIMD-SM机器上的异步并行求和算法机器上的异步并行求和算法 begin /开始主进程开始主进程 total_sum=0;for i=1 to p do in parallel begin sub_sum(i,loc

47、al_sum);lock(total_sum);/对全局变量对全局变量total_sum加锁加锁 total _sum=total _sum+local_sum;unlock(total_sum);end endprocedure sub_sum(i,local_sum)/并发子进程并发子进程 begin local_sum=0；for j=i to n step p do local_sum=local_sum+xj;return local_sum;end2022/12/233716.7 MIMD-SM上的异步并行求和算法上的异步并行求和算法n上述算法在最坏情况下的运算时间，该运算时间有以

48、下几部分上述算法在最坏情况下的运算时间，该运算时间有以下几部分组成：组成：（1）生成进程所需要的时间：生成）生成进程所需要的时间：生成p个子进程需要时间为个子进程需要时间为O(p);（2）局部求和所需要的时间：每个子进程都需要对）局部求和所需要的时间：每个子进程都需要对n/p个数个数据求和，所以局部求和时间为据求和，所以局部求和时间为O(n/p);（3）求取总和所需要的时间：因为在任何一个时间只能由一）求取总和所需要的时间：因为在任何一个时间只能由一个进程执行总和的操作，相当于个进程执行总和的操作，相当于p个处理器串行地对全局变量个处理器串行地对全局变量total-sum进行加锁、解锁操作，所以需要的时间为进行加锁、解锁操作，所以需要的时间为O(p);（4）进程同步所需要的时间：进程是异步并行执行的，所以）进程同步所需要的时间：进程是异步并行执行的，所以在最坏情况下在最坏情况下p个并发进程同步结束需要的时间为个并发进程同步结束需要的时间为O(p)。因此上述算法在最坏情况下的运算时间为，执行代价为：因此上述算法在最坏情况下的运算时间为，执行代价为：C(n)=P(n)T(n)=pO(n/p+p)=O(n+p2)返回目录返回目录2022/12/2338