文档介绍：并行计算
中国科学技术大学计算机科学与技术系
国家高性能计算中心(合肥)
2003年9月
2017/11/10
1
现代密码学理论与实践之五
第二篇并行算法的设计 第四章并行算法的设计基础 第五章并行算法的一般设计方法 第六章并行算法的基本设计技术 第七章并行算法的一般设计过程
2017/11/10
2
现代密码学理论与实践之五
第五章并行算法的一般设计方法 串行算法的直接并行化 从问题描述开始设计并行算法 借用已有算法求解新问题
2017/11/10
3
现代密码学理论与实践之五
设计方法描述 快排序算法的并行化
2017/11/10
4
现代密码学理论与实践之五
设计方法的描述
方法描述
发掘和利用现有串行算法中的并行性,直接将串行算法改造为并行算法。
评注
由串行算法直接并行化的方法是并行算法设计的最常用方法之一;
不是所有的串行算法都可以直接并行化的;
一个好的串行算法并不能并行化为一个好的并行算法;
许多数值串行算法可以并行化为有效的数值并行算法。
2017/11/10
5
现代密码学理论与实践之五
设计方法描述 快排序算法的并行化
2017/11/10
6
现代密码学理论与实践之五
快排序算法的并行化
PRAM-CRCW上的快排序二叉树构造算法
输入:序列(A1,…,An)和n个处理器
输出:供排序用的一棵二叉排序树
Begin
(1)for each processor i do (2)repeat for each processor i<>root do
()root=i if (Ai<Afi)∨(Ai=Afi∧i<fi) then
()fi=root ()LCfi=i
()LCi=RCi=n+1 ()if i=LCfi then exit else fi=LCfi endif
end for else
()RCfi=i
()if i=RCfi then exit else fi=RCfi endif
endif
end repeat
End
2017/11/10
7
现代密码学理论与实践之五
第五章并行算法的一般设计方法 串行算法的直接并行化 从问题描述开始设计并行算法 借用已有算法求解新问题
2017/11/10
8
现代密码学理论与实践之五
从问题描述开始设计并行算法
方法描述
从问题本身描述出发,不考虑相应的串行算法,设计一个全新的并行算法。
评注
挖掘问题的固有特性与并行的关系;
设计全新的并行算法是一个挑战性和创造性的工作;
利用串的周期性的PRAM-CRCW算法是一个很好的范例;
2017/11/10
9
现代密码学理论与实践之五
第五章并行算法的一般设计方法 串行算法的直接并行化 从问题描述开始设计并行算法 借用已有算法求解新问题
2017/11/10
10
现代密码学理论与实践之五