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

《并行计算划分和分治策略.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第四章划分和分治策略划分(partitioning)：将问题分为若干个独立的部分。分治法(divideandconquermethod)：将一个大问题逐步分割成若干个原问题的子问题，用简单且相同的方法对这些子问题进行求解，然后将这些子问题的解组合成原问题的解。在分治法中分解问题和合并结果常使用递归技术来实现。递归分治法能使各个子问题并行化执行，即各个进程用来执行被分解的部分。通常数据的划分也同时局部化。划分策略PartitioningStrategies数据划分(datapartitioningordomaindecomposition)----数据域并行(SIMD或S

2、PMD)数据划分是并行计算中的主要策略功能划分(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)分治

3、法master:/*每个处理器计算s个数之和*/s=n/p;for(i=0,x=0;i

4、行时间：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

5、:bcast(numbers,s,Pmaster);/*slave_number:0..m-1*/start=slave_number*s;end=start+s;part_sum=0;for(i=start;i

6、bers,&s,Pgroup,root);part_sum=0;for(i=0;i

7、(n1+n2);else{Divide(s,s1,s2);part_sum1=add(s1);part_sum2=add(s2);return(part_sum1+part_sum2);}}分治法是将大问题递归地分解为容易处理的小问题，并且保持解决小问题与解决大问题的方法是一致的。P0P2P0P4P0P6P4P0P1P2P3P4P5P6P7分治法的并行实现：SPMD并行算法Divide_conquer(T,pro_id,&k)//假设有n=2k个处理器{if

8、T

9、>given_limit/*

10、T

11、表示任务T的规模*/{divide(T,T