文档介绍：并行计算
中国科学技术大学计算机科学与技术系
国家高性能计算中心(合肥)
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
现代密码学理论与实践之五
并行算法的表达
描述语言
可以使用类Algol、类Pascal等;
在描述语言中引入并行语句。
并行语句示例
Par-do语句
for i=1 to n par-do
……
end for
for all语句
for all Pi, where 0≤i≤k
……
end for
2017/11/10
7
现代密码学理论与实践之五
并行算法的基础知识 并行算法的定义和分类 并行算法的表达 并行算法的复杂性度量 并行算法中的同步和通讯
2017/11/10
8
现代密码学理论与实践之五
并行算法的复杂性度量
串行算法的复杂性度量
最坏情况下的复杂度(Worst-plexity)
期望复杂度(plexity)
并行算法的几个复杂性度量指标
运行时间t(n):包含计算时间和通讯时间,分别用计算时间步和选路时间步作单位。n为问题实例的输入规模。
处理器数p(n)
并行算法成本c(n): c(n)=t(n)p(n)
总运算量W(n): 并行算法求解问题时所完成的总的操作步数。
2017/11/10
9
现代密码学理论与实践之五
并行算法的复杂性度量
Brent定理
令W(n)是某并行算法A在运行时间T(n)内所执行的运算
量,则A使用p台处理器可在t(n)=O(W(n)/p+T(n))时间
内执行完毕。
W(n)和c(n)密切相关
P=O(W(n)/T(n))时,W(n)和c(n)两者是渐进一致的
对于任意的p,c(n)›W(n)
2017/11/10
10
现代密码学理论与实践之五