并行算法的一般设计策略ppt课件.ppt

1 第四章并行算法的一般设计策略 2 设计并行算法一般有3种策略 1 检查和开拓现有串行算法中固有的并行性 直接将其并行化 该方法并不是对所有问题总是可行的 但对很多应用问题仍不失为一种有效的方法 2 从问题本身的描述出发 根据问题的固有属性 从头设计一个全新的并行算法 这种方法有一定难度 但所设计的并行算法通常是高效的 3 借助已有的并行算法求解新问题 3 4 1串行算法的直接并行化 方法描述发掘和利用现有串行算法中的并行性 直接将串行算法改造为并行算法 评注由串行算法直接并行化的方法是并行算法设计的最常用方法之一 并非所有的串行算法都可以并行化 一个好的串行算法并不能并行化为一个好的并行算法 相反一个不好的串行算法则有可能产生很优秀的并行算法 例如枚举排序不是一种好的串行算法 但是将其直接并行化后可以得到比较好的并行算法 显著优点 无需考虑算法的稳定性 收敛性等复杂问题 4 积分算法的直接并行化 的计算 5 计算 的串行C代码 defineN1000000main doublelocal pi 0 0 w longi w 1 0 N for i 0 i N i local i 0 5 w pi pi 4 0 1 0 local local printf piis f n pi w 6 k个处理器并行地计算部分和 7 串行算法并行化 1并行排序2矩阵运算3组合优化 8 1并行排序 并行排序研究的必要性 排序是计算机所需要经常完成的操作 由于排序后的数据常常比无序的数据更容易处理 比如查找的效率更高 所以很多算法要求数据是排序的 大数据量的排序在单个处理器上串行执行需要消耗大量的时间 这就提出了并行排序的需求 排序的分类 内部排序和外部排序常用的排序算法大多是基于比较 Comparison based 的排序 已经证明 这类排序算法的最低时间复杂度是 其中n是待排序的元素数目 因此如果使用n个处理器基于顺序排序算法的最好并行时间复杂性为 9 并行排序的几个关键问题 串行排序算法的并行化需要把待排序的元素分布到各个处理器上 在这过程中有几个问题需要解决 1 数据如何分配到不同的处理器上2 不同处理器上的元素如何进行大小比较 10 问题1 数据如何分配到不同的处理器 1 可以把所有数据放在一个结点上 其它结点从此结点取数据并把处理结果再回送给此结点 很多情况下要求源数据和处理结果数据都分布在不同的结点上 这就要考虑数据的分布问题 2 一个直观的办法是把所有参与排序的处理器和数据编号 源数据按照其编号取模分布到相应的处理器上 排序结果在各个处理器上均匀分布 满足小编号处理器上的每个元素均小于大编号处理器上的每个元素 11 问题2 不同处理器上的元素如何进行大小比较 比较操作和位置交换操作是排序算法中的基本操作 它们在串行程序中都很容易实现 因为要比较大小或交换位置的两个元素都在存储空间中 而在并行算法中 这些操作并不是想象的那么容易 因为两个元素分别位于不同的结点上 考虑一种极端的情况 待排序的元素与处理器的个数一样多 这样每个处理器上存储一个待排序元素 假定在算法执行过程中 两个处理器Pi和Pj要比较它们的元素ai和aj 比较结束后 Pi上要存储两个元素中较小的一个 而Pj则存储较大的一个 如何完成比较呢 12 Message PassingCompareandExchangeVersion1P1sendsAtoP2 whichcomparesAandBandsendsbackBtoP1ifAislargerthanB otherwiseitsendsbackAtoP1 13 AlternativeMessagePassingMethodVersion2ForP1tosendAtoP2andP2tosendBtoP1 Thenbothprocessesperformcompareoperations P1keepsthelargerofAandBandP2keepsthesmallerofAandB NOTE DifferentprocessorsoperatingatdifferentprecisioncouldConceivablyproducedifferentanswersifrealnumbersarebeingcompared 注意避免死锁 14 再来看每个处理器上存储多个待排序元素的情况 设处理器个数为p 待排序元素数目为n 则每个处理器上平均有n p个元素 定义每个处理器上的所有元素为一个超元素 定义超元素之间的大小关系 当一个超元素E1中的所有元素都不大于另一个超元素E2中的任何元素时 定义为E1 E2 同理定义等于 小于等于 等关系 与普通元素不同的是 两个超元素之间可能不是 中的任何一个 容易验证 超元素之间的 关系满足传递性 来看两个编号相邻的处理器之间如何进行元素比较 与每个处理器上一个元素的情形类似 每个处理器把超元素发给对应的处理器 每个处理器在接受到对方的超元素后 合并两个超元素并排序 归并排序 然后Pi取值较小的一半 而Pj则取值较大的一半 整个过程分四步 通信 比较 合并 拆分 15 pprocessorsandnnumbers n pnumbersassignedtoeachprocessor MergingTwoSublists Version1 第一步 第二步 16 MergingTwoSublists Version2 17 枚举排序 枚举排序是一种最简单的排序算法 该算法的具体思想是 假设按关键字递增排序 对每一个待排序的元素统计小于它的所有元素的个数 从而得到该元素最终处于序列中的位置 假定待排序的n个数存在a 1 a n 中 首先将a 1 与a 2 a n 比较 记录比其小的数的个数 令其为k a 1 就被存入有序的数组b 1 b n 的b k 1 位置上 然后将a 2 与a 1 a 3 a n 比较 记录比其小的数的个数 依此类推 时间复杂度为O n2 18 枚举排序串行算法 输入 a 1 a n 输出 b 1 b n Beginfori 1tondo 1 k 1 2 forj 1tondoifa i a j thenk k 1endifendfor 3 b k a i endforEnd 19 枚举排序的并行算法 对该算法的并行化是很简单的 假设对一个长为n的输入序列使用n个处理器进行排序 只需每个处理器负责完成对其中一个元素的定位 然后将所有的定位信息集中到主进程中 由主进程负责完成所有元素的最终排位 20 枚举排序并行算法 输入 无序数组a 1 a n 输出 有序数组b 1 b n Begin 1 P0播送a 1 a n 给所有Pi 2 forallPiwhere1 i npara do 2 1 k 1 2 2 forj 1tondoif a i a j or a i a j andi j thenk k 1endifendfor 3 P0收集k并按序定位End 步骤 的时间复杂度为O n 步骤 中主进程完成的数组元素重定位操作的时间复杂度为O n 通信复杂度分别为O n 同时 中的通信复杂度为O n2 所以总的计算复杂度为O n 总的通信复杂度为O n2 21 冒泡排序串行算法 串行冒泡排序算法包括两个循环 每次操作比较两个相邻的元素 然后通过交换使之符合指定的排序 以下是串行冒泡排序算法 voidBUBBLE SORT n fori n 1downto1doforj 1toidocompare exchange aj aj 1 22 冒泡排序的步骤 23 可以通过一些手段来提高其性能 比如当没有发现交换时便结束循环等 不过这并不改变算法运行的时间复杂度O n2 冒泡排序顺次比较相邻的元素 这在本质上是一个串行的过程 很难并行化 将顺次的比较过程并行化将导致算法错误 得不到预想的结果 考虑到内循环的下一次迭代的 冒泡 动作可以在前一次迭代完成之前开始 只要下一次 冒泡 动作不影响前一次迭代 所以可以开发流水线并行算法 24 流水线并行 25 一维线性网络中的奇偶置换冒泡排序 设待排序的元素数目为n 以n为偶数来说明奇偶置换排序 奇偶置换排序用n个阶段完成对n个元素的排序 每一个阶段需要n 2个比较 交换操作 这n个阶段分成两类 分别称为奇操作阶段和偶操作阶段 设是待排序的序列 在每个奇操作阶段 奇数索引的元素与自己的右邻居进行比较并在必要时交换 同样 在每个偶操作阶段 偶数索引的元素与自己的右邻居进行比较和交换 经过n个阶段进行这样的操作后 整个序列便处于有序状态 26 对8个数进行奇偶互换排序 27 voidODD EVEN n for i 1 i n i ifiisoddthenfor j 0 j n 2 1 j compare exchange a2j 1 a2j 2 ifiiseventhenfor j 1 j n 2 1 j compare exchange a2j a2j 1 串行奇偶置换冒泡排序程序 28 串行奇偶置换冒泡排序的并行化 voidODD EVEN PAR n id processor slabelfor i 1 i n i ifiisoddthenifidisoddthencompare exchange min id 1 elsecompare exchange max id 1 ifiiseventhenifidiseventhencompare exchange min id 1 elsecompare exchange max id 1 29 归并排序 MergesortAclassicalsequentialsortingalgorithmusingdivide and conquerapproach Unsortedlistfirstdividedintohalf Eachhalfisagaindividedintotwo Continueduntilindividualnumbersareobtained Thenpairsofnumberscombined merged intosortedlistoftwonumbers Pairsoftheselistsoffournumbersaremergedintosortedlistsofeightnumbers Thisiscontinueduntiltheonefullysortedlistisobtained 30 Mergesort的并行化使用树状进程分配的归并排序 Tcomp 2p 2 logpTcomm 2 logp tstartup 2ntdata 31 奇偶归并排序 奇偶归并排序将两个有序序列归并为一个有序序列 对于给定的两个序列a n 和b n 该算法描述如下 1 每个序列的奇数下标索引的元素 即a1 a3 an 1和b1 b3 bn 1被归并为一个有序序列c1 c2 cn 2 每个序列的偶数下标索引的元素 即a2 a4 an和b2 b4 bn被归并为一个有序序列d1 d2 dn 3 最后的有序序列e1 e2 e2n通过以下方法得到 e2i min ci 1 di e2i 1 max ci 1 di 32 Odd EvenMergingofTwoSortedLists e2i min ci 1 di e2i 1 max ci 1 di 每个序列的奇 偶数下标索引的元素分别被归并为一个有序序列 33 快速排序的并行化 Tcomp n n 2 n 4 2nTcomm logp tstartup ntdata 34 在专用网络Hypercube超立方体上的排序Hypercubenetworkhasstructuralcharacteristicsthatofferscopeforimplementingefficientdivide and conquersortingalgorithms suchasquicksort 35 超立方体上的并行化 基本思路 一个d维的超立方体可以看作是由两个d 1维的超立方体互联而成 利用这一点 可以把一个d维的超立方体存储的一个序列划分成两个子序列而分别存放到两个d 1维的超立方体上 使得每个d 1维立方体的每个处理器都跟另外一个立方体的某处理器直接相连 这样 一个大于界的子序列与小于界的子序列可以分别放在不同的超立方体上 36 Supposealistofnnumbersplacedononenodeofad dimensionalhypercube Listcanbedividedintotwopartsaccordingtothequicksortalgorithmbyusingapivotdeterminedbytheprocessor withonepartsenttotheadjacentnodeinthehighestdimension Thenthetwonodescanrepeattheprocess 1 整个序列在一个处理器上 37 Example3 dimensionalhypercubewiththenumbersoriginallyinnode000 38 数据最初放在节点000时的超立方体快速排序算法 Finally thepartssortedusingasequentialalgorithm allinparallel Ifrequired sortedpartscanbereturnedtooneprocessorinasequencethatallowsprocessortoconcatenatesortedliststocreatefinalsortedlist 39 2 最初数据散布在所有处理器上 假设待排序数最初均匀地 不按任何特殊顺序地分布在节点上 一个2d个节点的超立方体由两个2d 1个节点的超立方体组成 它们通过每个立方体中第d维节点之间的链路互联 快速排序并行算法的步骤 首先将超立方体看成两个子立方体 位于高端子立方体中的处理器的地址首位为1 位于低端子立方体中的处理器的地址首位为0 成对的地址分别为0 xxx和1xxx的处理器称为 伙伴 其中x是相同的 40 具体步骤 1 一个处理器 如p0 选择 或计算 一个合适的轴元素 并通过广播把它送到立方体中所有其它处理器 2 低端子立方体中的处理器将大于该轴元素的数传送给他们位于高端子立方体中的伙伴处理器 高端子立方体中的处理器将小于该轴元素的数传送给他们位于低端子立方体中的伙伴处理器 3 每个处理器将收到的序列和本身的序列拼接 给定一个d维超立方体 经过这些步骤以后 低端d 1维子立方体中的数都小于或等于轴元素 而高端d 1维子立方体中的数都大于轴元素 4 两个d 1维子立方体重复递归调用第2 3步 其中每个子立方体中的一个进程为该子立方体选择轴元素并通过广播传送到子立方体中的其他进程 递归调用d次后终止 5 为了完成排序 每个处理器中的数需要串行进行排序 最后按数字顺序访问处理器即可从处理器中检索数 41 42 2矩阵运算 转置 乘法 矩阵运算是数值计算中最重要的一类运算 特别是在线性代数和数值分析中 它是一种最基本的运算 矩阵的划分 条带状划分和棋盘划分为了对一个矩阵进行并行操作 必须将其进行划分并映射到不同的处理器上 尤其是科学计算中矩阵的规模一般都很庞大的情况下更是如此 条带状划分 StripedPartitioning 条带状划分就是把矩阵按照行或列分成几部分 分别映射到各个处理器 如果分到每个处理器的各行或列是连续的 则称为块带状划分 Block Striped 相对的 如果是按照行号或者列号取模而进行的矩阵划分则称为循环带状划分 Cyclic Striped 43 4个处理器上16 16矩阵的均匀条带状划分和映射 a 列方向上的块带状划分 b 行方向的循环带状划分 44 棋盘划分 CheckerboardPartitioning 棋盘划分把矩阵划分为若干个子矩阵并映射到不同的处理器上 每个处理器都不包含完整的行和列 和条带状划分类似 棋盘划分也可以分为块棋盘划分和循环棋盘划分 45 16个处理器上8 8矩阵的均匀块棋盘划分和映射 46 2 1矩阵的转置 转置 Transposition 是基本的矩阵运算 一个矩阵A的转置记为AT 它是将矩阵A的元素沿对角线互换而得到的 矩阵转置的串行算法很简单 只需要把上三角 不包括对角线 的元素循环一遍 每个元素与其对称位置的元素交换位置即可 整个过程只需要一个单位的多余空间 时间复杂度为O n2 47 单处理器上矩阵转置算法 输入 矩阵An n输出 矩阵An n的转置ATn nBeginfori 2tondoforj 1toi 1do交换a i j 和a j i endforendforEnd 48 棋盘划分的矩阵转置 二维网格互联结构上的矩阵转置设处理器数目p n2 则整个n n的矩阵分成p个大小为的子块 这些子块自然影射到网格互联结构的p个处理器上 算法可以分两步来完成 第一步 将各个子块看作一个整体进行子块转置 这一步由各处理器互相通信 第二步 各处理器分别对自己的内部子块进行局部转置 49 16个处理器上块棋盘划分的8 8矩阵的转置 子块间转置 子块内转置 50 为了避免对应子块交换数据时处理器发生死锁 可令下三角子块先向与之对应的上三角子块发送数据 然后从上三角子块接收数据 上三角子块先将数据存放在缓冲区buffer中 然后从与之对应的下三角子块接收数据 最后再将缓冲区中的数据发送给下三角子块 51 算法块棋盘划分的矩阵转置算法输入 矩阵An n输出 矩阵An n的转置ATn nBegin对所有处理器my rank my rank 0 p 1 同时执行如下的算法 1 计算子块的行号v my rank sqrt p 计算子块的列号u my rankmodsqrt p 2 if u v then 对存放下三角块的处理器 2 1 将所存的子块发送到其对角块所在的处理器中 2 2 接收其对角块所在的处理器中发来的子块else 对存放上三角块的处理器 2 3 将所存的子块在缓冲区buffer中做备份 2 4 接收其对角块所在的处理器中发来的子块 2 5 将buffer中所存的子块发送到其对角块所在的处理器中endif 3 fori 1tomdo 处理器内部局部转置 forj 1toido交换a i j 和a j i endforendforEnd 52 53 2 2矩阵向量乘法 一个矩阵与向量相乘 结果得到一个向量 矩阵向量相乘的串行算法具有O n2 的时间复杂度 单处理器上矩阵 向量乘算法输入 An n Bn 1输出 Cn 1Beginfori 0ton 1doc i 0forj 0ton 1doc i c i a i j b j endforendforEnd 54 矩阵 向量乘法的并行算法 矩阵 向量乘法同样可以有带状划分 StripedPartitioning 和棋盘划分 CheckerBoardPartitioning 两种并行算法 以下仅讨论行带状划分矩阵 向量乘法 列带状划分矩阵 向量乘法是类似的 设处理器个数为p 对矩阵A按行划分为p块 每块含有连续的m行向量 这些行块依次记为A0 A1 Ap 1 分别存放在标号为0 1 p 1的处理器中 同时将向量B广播给所有处理器 各处理器并行地对存于局部数组a中的行块Ai和向量B做乘积操作 55 行带状划分的矩阵 向量乘并行算法输入 An n Bn 1输出 Cn 1Begin对所有处理器my rank my rank 0 p 1 同时执行如下的算法 fori 0tom 1doc i 0 0forj 0ton 1doc i c i a i j b j endforendforEnd假设一次乘法和加法运算时间为一个单位时间 不难得出行带状划分的矩阵 向量乘算法并行计算时间Tp n2 p 若处理器个数和向量维数相当 则其时间复杂度为O n 56 矩阵相乘及其串行算法 由矩阵乘法定义容易给出其串行算法 若一次乘法和加法运算时间为一个单位时间 则显然其时间复杂度为O mnk 单处理器上矩阵相乘算法输入 Am n Bn k输出 Cm kBeginfori 0tom 1doforj 0tok 1doc i j 0forr 0ton 1doc i j c i j a i r b r j endforendforendforEnd 57 简单的矩阵并行分块乘法算法 矩阵乘法也可以用分块的思想实现并行 即分块矩阵乘法 BlockMatrixMultiplication 将矩阵A按行划分为p块 p为处理器个数 设 每块含有连续的u行向量 这些行块依次记为A0 A1 Ap 1 分别存放在标号为0 1 p 1的处理器中 对矩阵B按列划分为p块 记 每块含有连续的v列向量 这些列块依次记为B0 B1 Bp 1 分别存放在标号0 1 p 1为的处理器中 将结果矩阵C也相应地同时进行行 列划分 得到p p个大小为u v的子矩阵 记第i行第j列的子矩阵为Cij 显然有Cij Ai Bj 其中 Ai大小为u n Bj大小为n v 58 矩阵相乘并行算法中的数据交换 59 开始 各处理器的存储内容如上图所示 此时各处理器并行计算Cii Ai Bi 其中i 0 1 p 1 此后第i号处理器将其所存储的B的列块送至第i 1号处理器 第0号处理器将B的列块送至第p 1号处理器中 形成循环传送 各处理器中的存储内容如图 b 所示 它们再次并行计算Cij Ai Bj 这里j i 1 modp B的列块在各处理器中以这样的方式循环传送p 1次并做p次子矩阵相乘运算 就生成了矩阵C的所有子矩阵 编号为i的处理器的内部存储器存有子矩阵Ci0 Ci1 Ci p 1 为了避免在通信过程中发生死锁 奇数号及偶数号处理器的收发顺序被错开 使偶数号处理器先发送后接收 而奇数号处理器先将B的列块存于缓冲区buffer中 然后接收编号在其后面的处理器所发送的B的列块 最后再将缓冲区中原矩阵B的列块发送给编号在其前面的处理器 60 矩阵并行分块乘法算法 输入 Am n Bn k 输出 Cm kBegin对所有处理器my rank my rank 0 p 1 同时执行如下的算法 1 目前计算C的子块号l i my rank modp 2 forz 0tou 1doforj 0tov 1doc l z j 0fors 0ton 1doc l z j c l z j a z s b s j endforendforendfor 3 计算左邻处理器的标号mm1 p my rank 1 modp计算右邻处理器的标号mp1 my rank 1 modp 61 4 if i p 1 then 4 1 if my rankmod2 0 then 编号为偶数的处理器 i 将所存的B的子块发送到其左邻处理器中 ii 接收其右邻处理器中发来的B的子块endif 4 2 if my rankmod2 0 then 编号为奇数的处理器 i 将所存的B子块在缓冲区buffer中做备份 ii 接收其右邻处理器中发来的B的子块 iii 将buffer中所存的B的子块发送到其左邻处理器中endifendifEnd 62 3图论及组合优化 图论在计算机科学 信息科学 人工智能 网络理论 系统工程 控制论 运筹学和经济管理等领域有着广泛的应用 但很多图论问题虽易表达 却难以求解 其中有相当多的图论问题均属NP完全问题 本节主要介绍工程实用简单图论问题的并行算法 63 3 1最小生成树 一个无向连通图G的生成树是指满足如下条件的G的子图T T和G顶点数相同 T有足够的边使得所有顶点连通 同时不出现回路 如果对G的每条边指定一个权值 那么 边权总和最小的生成树称为最小代价生成树 记为MCST MinimumCostSpanningTree 常简称为最小生成树 记为MST 最小生成树问题就是给定G 找出G的一个最小生成树T的问题 64 最小生成树串行算法 Sollin算法 SollinAlgorithm 是众多用于求解MST问题的算法之一 其原理为 算法开始时 图中的N个顶点视为一片森林 每个顶点视为一棵树 算法主循环的流程中 森林里每棵树同时决定其连向其它树的最小邻边 并将这些边加入森林中 实现树的合并 循环到森林中只剩一棵树时终止 由于森林中树的数目每次至少减少一半 所以只要 N次循环就可以找出MST 算法中以D i 为顶点i所在的树的编号 edge i 和closet i 为树i连向其它树的最小邻边和其长度 则Sollin算法的形式描述见下述算法 其时间复杂度为O N2 N 65 SollinMST算法 输入 无向图G的边权矩阵W输出 G的最小生成树的边集合TprocedureSollin MSTBegin 以下所有顶点初始化为一棵孤立的树 1 fori 0toN 1doD i iendfor 2 T初始化为空集 66 3 while T N 1do 以下为各树寻找连向其它树的最小边权 3 1 for每棵树idocloset i endfor 3 2 for图G中每条边 v u doifD v D u andw v u closet D v then closet D v w v u edge D v v u endifendfor 以下是树的合并 3 3 for每棵树ido v u edge i ifD v D u thenT T v u 树D v 和D u 合并endifendforendwhileEnd 67 最小生成树并行算法 基本思路是由多个处理器同时负责为多个树查找最短边 为了方便并行处理 各树寻找外连最短边的的任务