06 并行算法的基本设计技术.ppt

并行计算
中国科学技术大学计算机科学与技术系
国家高性能计算中心(合肥)
2003年9月
2017/11/10
1
现代密码学理论与实践之五
第二篇并行算法的设计 第四章并行算法的设计基础 第五章并行算法的一般设计方法 第六章并行算法的基本设计技术 第七章并行算法的一般设计过程
2017/11/10
2
现代密码学理论与实践之五
第六章并行算法的基本设计技术 划分设计技术 分治设计技术 平衡树设计技术 倍增设计技术 流水线设计技术
2017/11/10
3
现代密码学理论与实践之五
划分设计技术 均匀划分技术 方根划分技术 对数划分技术 功能划分技术
2017/11/10
4
现代密码学理论与实践之五
均匀划分技术
划分方法
n个元素A[1..n]分成p组,每组A[(i-1)n/p+1..in/p],i=1~p
示例:MIMD-SM模型上的PSRS排序
begin
(1)均匀划分:将n个元素A[1..n]均匀划分成p段,每个pi处理
A[(i-1)n/p+1..in/p]
(2)局部排序:pi调用串行排序算法对A[(i-1)n/p+1..in/p]排序
(3)选取样本:pi从其有序子序列A[(i-1)n/p+1..in/p]中选取p个样本元素
(4)样本排序:用一台处理器对p2个样本元素进行串行排序
(5)选择主元:用一台处理器从排好序的样本序列中选取p-1个主元,并
播送给其他pi
(6)主元划分:pi按主元将有序段A[(i-1)n/p+1..in/p]划分成p段
(7)全局交换:各处理器将其有序段按段号交换到对应的处理器中
(8)归并排序:各处理器对接收到的元素进行归并排序
end.
2017/11/10
5
现代密码学理论与实践之五
均匀划分技术
PSRS排序过程。N=27,p=3,PSRS排序如下:
2017/11/10
6
现代密码学理论与实践之五
划分设计技术 均匀划分技术 方根划分技术 对数划分技术 功能划分技术
2017/11/10
7
现代密码学理论与实践之五
方根划分技术
划分方法
n个元素A[1..n]分成A[(i-1)n^(1/2)+1..in^(1/2)],i=1~n^(1/2)
示例:SIMD-CREW模型上的 Valiant归并(1975年发表)
//有序组A[1..p]、B[1..q], (假设p<=q), 处理器数
begin
(1)方根划分: A,B分别按;
(2)段间比较: A划分元与B划分元比较(至多对),
确定A划分元应插入B中的区段;
(3)段内比较: A划分元与B相应段内元素进行比较,并插入适当的位置;
(4)递归归并: B按插入的A划分元重新分段,与A相应段(A除去原划分元)
构成了成对的段组,对每对段组递归执行(1)~(3),直至A
组为0时,递归结束; 各组仍按分配处理器;
end.
2017/11/10
8
现代密码学理论与实践之五
方根划分技术
2017/11/10
9
现代密码学理论与实践之五
方根划分技术
2017/11/10
10
现代密码学理论与实践之五