并行计算划分和分治策略.ppt

第四章划分和分治策略 划分 partitioning 将问题分为若干个独立的部分 分治法 divideandconquermethod 将一个大问题逐步分割成若干个原问题的子问题 用简单且相同的方法对这些子问题进行求解 然后将这些子问题的解组合成原问题的解 在分治法中分解问题和合并结果常使用递归技术来实现 递归分治法能使各个子问题并行化执行 即各个进程用来执行被分解的部分 通常数据的划分也同时局部化 划分策略PartitioningStrategies数据划分 datapartitioningordomaindecomposition 数据域并行 SIMD或SPMD 数据划分是并行计算中的主要策略功能划分 functionaldecomposition 控制并行 MIMD或MPMD 正如前面给出的一些例子的并行处理方法所示 我们总是将问题要处理的数据集尽可能均匀地分配给各个处理机 或进程 这是因为数据并行往往能够带来更高的效率 例 利用数据划分技术对数列求和 假设有p个处理机 数列元素个数为n A0 An p 1An p A2n p 1A2n p A p 1 n p An 1 序列求和方法 主从结构点到点通信 send recv 广播通信 broadcast 散射通信 scatter 分治法 master 每个处理器计算s个数之和 s n p for i 0 x 0 i p i x x s send slave recv 主从结构划分求和算法 send recv 利用send和recv例程进行通信的并行求和算法的执行时间 1 主进程将p段数据分别发送给各个从进程的时间 p tstart n p tdata 2 各从进程计算自己拥有的n p个数据局部和的时间 n p 13 主进程从p个从进程接收局部和的时间 p tstart tdata 4 主进程计算p个局部和的总和的时间 p整个算法的执行时间为 2ptstart n p tdata n p 1 p O n p master s n p bcast numbers s Pslave group sum 0 for i 0 i p i recv slave bcast numbers s Pmaster slave number 0 m 1 start slave number s end start s part sum 0 for i start i end i part sum numbers i send 主从结构划分求和算法 broadcast master s n p root Pmaster scatter numbers slave scatter numbers 主从结构划分求和算法 scatter 分治法 用数列求和来说明分治法的基本思想 intadd ints 顺序算法 if number s 2 return n1 n2 else Divide s s1 s2 part sum1 add s1 part sum2 add s2 return part sum1 part sum2 分治法是将大问题递归地分解为容易处理的小问题 并且保持解决小问题与解决大问题的方法是一致的 P0 P2 P0 P4 P0 P6 P4 P0 P1 P2 P3 P4 P5 P6 P7 分治法的并行实现 SPMD并行算法Divide conquer T pro id 组合T1和T2的结果作为T的结果 返回 else处理T 并将T的结果返回 算法的时间分析 假设有p 2k个处理机 共计算N个数的和计算时间 N p logp通信时间 Tcomm1 tstartup N 2tdata tstartup N 4tdata tstartup N ptdata ktstartup N p 1 p tdata O N Tcomm2 k tstartup tdata logp tstartup tdata 对于计算时间而言 其最大加速比可以达到p 但分割和合并操作使并行算法的加速比可能远远小于p M路分治法 用M路分治法对数列求和 顺序算法 intadd ints if number s 4 return n1 n2 n3 n4 else Divide s s1 s2 s3 s4 part sum1 add s1 part sum2 add s2 part sum3 add s3 part sum4 add s4 return part sum1 part sum2 part sum3 part sum4 划分 分治技术实例 应用1 以递归方法进行的一些排序算法应用2 数值积分应用3 N体问题 应用1 排序算法 顺序算法及其时间复杂性桶排序的并行化 快速排序的顺序算法 从小到大排列a1 a2 an已知数列元素的最大值end和最小值start quicksort list start end if start end partition list start end pivot quicksort list start pivot 1 quicksort list pivot 1 end 该算法的执行时间为 nlogn 桶排序的顺序算法假设被排序的数据在一个已知的区域 如 0到a 1 内均匀分布 将该区域平均分为m个子区域 即 0 a m 1 a m 2a m 1 m 1 a m a 1 构成m个桶 串行算法 对待排序的n个数依次判断它属于哪个桶 设每次判断需一次计算 则共计算n次 对m个桶内的约n m个数分别采用最好的排序算法 如quicksort 则时间复杂度为 m n m log n m nlog n m 桶排序算法仅在每个区域中的数据的个数大致相等时才会得到好的性能 桶排序顺序算法的执行时间 n m n mlog n m O nlog n m 未排序的数列 对桶内数列进行排序 桶排序并行算法1 未排序的数列 对桶内数列进行排序 该并行算法的执行过程 每个处理机拥有所有的数据副本 各处理机用O n 的时间将数据分给各个处理机负责的桶中 各处理机同时对自己拥有的数据利用顺序算法进行排序 然后合并数列 得到排好序的数列 并行算法的执行时间 n n plog n p 桶排序并行算法2将数列划分为p个区域 每个处理机拥有一个区域 通信时间 广播数据 tcomm1 tstartup ntdata每个处理机都有p个 小 桶 并将自己区域中的n p个数据分散到这些小桶中 计算时间 tcomp1 n p将小桶中的n p2个数据倒入p个大桶 通信时间 将p 1个小桶的内容发送给其它处理机 并从p 1个处理机接收属于该处理机的大桶的数据 tcomm2 2 p 1 tstartup n p2tdata 对大桶中的数据排序 计算时间 tcomp2 n p log n p 算法执行时间 n p n p log n p 2p 1 tstartup n 2n p 2n p2 tdata 已排好序的数列 各种算法的执行时间对比 串行算法 m n m log n m nlog n m 并行算法1 O n plog n p n 并行算法2 n p n p log n p 2p 1 tstartup n 2n p 2n p2 tdata O n plog n p n 如果原有数列在一个已知区域 0 a 1 均匀地分布 那么 我们才会得到高效率的桶排序的串行和并行算法 对于采用了p2个小桶的并行算法2中 腾空各个 p个 处理机拥有的p个小桶的内容是指将自己拥有的p 1个小桶的内容分别发送给其它p 1个处理机 在MPI中该操作可由一个群体操作例程来实现 MPI Alltoall void sendbuf intsendcount typesendtype void recvbuf intrecvcount typerecvdtype MPI Commcomm All to all操作示意图 应用2 数值积分 将积分区域分割为一系列矩形 利用这些矩形的面积近似求出积分区域的值 矩形面积 d f p d 2 将积分区域分割为一系列梯形 利用这些梯形的面积近似积分区域的值 矩形面积 d f p f q 2 当d越小 算法求出的近似值越精确 显然我们能很容易地将数值积分问题分解为多个相互独立的部分 每个部分由一个单独的进程完成计算 一般的静态分配的并行算法是将积分区域按处理机的个数p分为p块 然后每个处理机 进程 计算一块区域的面积 最后将其归并 得到整个区域的积分值 采用矩形方法 即计算每个小区间的中间点的函数值的矩形面积的并行算法 面积 df a d 2 df a d d 2 df a 2d d 2 df a n 1 d d 2 d f a d 2 f a d d 2 f a 2d d 2 f a n 1 d d 2 利用C MPI例程计算p值的程序见ComputePi doc文件 采用第二种方法 即计算每个小区间的梯形面积的计算公式 算法只需做少量修改 part sum 0 5 f start f end for x start d x end x x d calcspartialsumspart sum f x part sum d part sum 除以上计算数值积分方法 我们还可以用递归的分治法来解决问题 如用C Linda实现的计算p的程序 C Linda含有几个在 元组空间 上的操作 元组空间 tuplespace 并行编程环境中的虚拟存储器 由一组有序的元组构成 并行执行的进程通过共享数据元组进行交互 见ComputePi doc文件 work 1 0 400000 1 0 400000 work 1 0 400000 0 0000025 work 2 0 200000 0 0000025 work 3 200000 400000 0 0000025 work 1 0 400000 0 0000025 work 2 0 200000 0 0000025 work 3 200000 400000 0 0000025 work 4 0 100000 0 0000025 work 5 100000 200000 0 0000025 work 6 200000 300000 0 0000025 work 7 300000 400000 0 0000025 work 1 0 400000 0 0000025 work 2 0 200000 0 0000025 work 3 200000 400000 0 0000025 work 1 0 400000 1 0 400000 问题的描述 N体问题是利用牛顿的万有引力定律和运动定律模拟太空中星体的运动轨迹 万有引力定律 质量为ma和mb的两个物体间的引力为 应用3 N体问题 其中 G 6 67259 10 11米3 千克 秒2 是引力常数 r为两物体间的距离 应用3 N体问题 一个物体在受力的情况下 将根据牛顿第二定律产生加速度 F mam是物体的质量 F是物体所受的力 a是物体获得的加速度 实现细节 设模拟天体运动的时间间隔为 t 物体的质量为m 物体所受的力为 新的速度为 vt 1 vt分别为物体在t 1和t时刻的速度 当物体以速度v移动了 t时间后 其位置的变化为 xt 1 xt v tftrerrnsmndh N体计算问题模拟程序演示 N体计算问题顺序算法 for t 0 t tmax t foreachtimeperiod for i 0 i N i foreachbody F Force routine i computeforceonithbody v i new v i F dt m computenewvelocity pos i new pos i v i new dt andnewposition for i 0 i N i foreachbody pos i pos i new updatevelocity N体问题的并行算法顺序算法的时间复杂性为 O N2 将串行代码简单地并行化 会产生大量的信息交换 因为N体问题中计算每一个物体新的位置和新的速度都受其它N 1个物体信息 位置 的影响 并行算法的时间复杂性可以利用簇化方法减少 即一簇远距离的物体可以大略地作为一个簇的总质量位于该簇物体重心的单个远距离物体 这种簇化思想可以递归使用 Barnes Hut算法 创建8叉树假设在一个三维立方体空间中包含有N个星体1 将立方体分为8个子立方体 2 如果某个子立方体不含有星体 则删除该子立方体 以后不再考虑它 3 如果某立方体仅含有1个星体 则保留该子立方体 4 如果某立方体含有多于1个的星体 则继续递归地分割这个子立方体 直到每个子立方体仅含有一个星体为止 8叉树 每个节点都有8条边的树 树的叶子表示含有1个星体的单元 当树建立后 子立方体的总质量和该子立方体的重心将储存在各个节点中 Barnes Hut算法 for t 0 t tmax t foreachtimeperiod Build Octatree 建立8叉树 Total Mass Center 计算各簇的总质量和重心 Compute Force 遍历树计算物体所受的力 Update 更新物体的位置和速度 说明 Build Octatree 利用空间中的各物体原有的位置计算 Total Mass Center 是从叶子节点开始到根节点 计算每个子立方体总的质量和重心位置 非叶子节点 一簇 的质量通过其孩子的质量累加得到 而重心则通过孩子们的质量和重心合成得到 说明 续 Compute F