《并行计算划分和分治策略分析》由会员分享，可在线阅读，更多相关《并行计算划分和分治策略分析（45页珍藏版）》请在金锄头文库上搜索。
1、第四章划分和分治策略 划分 partitioning 将问题分为若干个独立的部分 分治法 divideandconquermethod 将一个大问题逐步分割成若干个原问题的子问题 用简单且相同的方法对这些子问题进行求解 然后将这些子问题的解组合成原问题的解 在分治法中分解问题和合并结果常使用递归技术来实现 递归分治法能使各个子问题并行化执行 即各个进程用来执行被分解的部分 通常数据的划分也同时局部化 划分策略PartitioningStrategies数据划分 datapartitioningordomaindecomposition 数据域并行 SIMD或SPMD 数据划分是并行计算中的主要
2、策略功能划分 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
3、 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
4、 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
5、 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个数的和计算时间
6、 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
7、 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
8、 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 桶排序算法仅在每个区域中的数据的个数大致相等时才会得到好的性能 桶排序顺序
9、算法的执行时间 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个数据分散到这些小桶中 计算时间
10、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 tstar
11、tup 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操作示
12、意图 应用2 数值积分 将积分区域分割为一系列矩形 利用这些矩形的面积近似求出积分区域的值 矩形面积 d f p d 2 将积分区域分割为一系列梯形 利用这些梯形的面积近似积分区域的值 矩形面积 d f p f q 2 当d越小 算法求出的近似值越精确 显然我们能很容易地将数值积分问题分解为多个相互独立的部分 每个部分由一个单独的进程完成计算 一般的静态分配的并行算法是将积分区域按处理机的个数p分为p块 然后每个处理机 进程 计算一块区域的面积 最后将其归并 得到整个区域的积分值 采用矩形方法 即计算每个小区间的中间点的函数值的矩形面积的并行算法 面积 df a d 2 df a d d 2
13、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
14、含有几个在 元组空间 上的操作 元组空间 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 1000
15、00 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 67
16、259 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 t 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 将串行代码简单地并行化 会产生大量的信息
