欢迎来到天天文库
浏览记录
ID:38338504
大小:1.28 MB
页数:44页
时间:2019-06-10
《并行计算划分和分治策略27430》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
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:/*
3、每个处理器计算s个数之和*/s=n/p;for(i=0,x=0;i
4、别发送给各个从进程的时间: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、ster);/*slave_number:0..m-1*/start=slave_number*s;end=start+s;part_sum=0;for(i=start;i6、_sum=0;for(i=0;i7、art_sum1=add(s1);part_sum2=add(s2);return(part_sum1+part_sum2);}}分治法是将大问题递归地分解为容易处理的小问题,并且保持解决小问题与解决大问题的方法是一致的。P0P2P0P4P0P6P4P0P1P2P3P4P5P6P7分治法的并行实现:SPMD并行算法Divide_conquer(T,pro_id,&k)//假设有n=2k个处理器{if8、T9、>given_limit/*10、T11、表示任务T的规模*/{divide(T,T
6、_sum=0;for(i=0;i
7、art_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
此文档下载收益归作者所有