并行算法分析

基本指标

并行算法分析 VS 串行算法分析

1. 串行算法评价:算法时间复杂度表示为输入规模的函数
2. 并行算法评价:除了输入规模之外,还应考虑处理器数目、**处理器相对运算速
   度、通信速度**
3. 评价标准
   
   • 运行时间
   • 加速比:并行算法比串行算法快多少?

并行程序设计的复杂性

1. 足够的并发度(Amdahl定律)
2. 并发粒度
   独立的计算任务的大小
3. 局部性
   对临近的数据进行计算
4. 负载均衡
   处理器的工作量相近
5. 协调和同步
   谁负责?处理频率?

并行算法的额外开销

除了串行算法要做的之外的工作
1. 进程间通信:最大开销,大部分并行算法都需要
2. 进程空闲:负载不均、同步操作、不能并行 化的部分
3. 额外计算

• 最优串行算法难以并行化,将很差的串行算法并行化,并行算法计算量>最优串行算法

• 最优串行算法并行化也会产生额外计算:并行快 速傅立叶变换,旋转因子的重复计算

性能评价标准

1. 运行时间
   串行算法:TS,算法开始到结束的时间流逝
   并行算法:TP,并行算法开始到最后一个进 程结束所经历时间

2. 并行算法总额外开销
   To=pTP – TS

3. 加速比
   S=TS/TP

效率

• 理想并行算法,S=p
• 难实现,不是100%时间都用于有效计算
• 求和例子,部分时间处理器处于空闲
• 效率(Efficiency):度量有效计算时间
• 理想情况=1,正常0~1
• E=S/p
• 求和例子
  E= Q(n/logn)/n= Q(1/logn)

代价

• cost,并行算法运行时间×处理器数量
• 所有处理器用来求解问题的时间总和
• E=TS/cost,p=1时,cost=TS
• 代价最优,cost-optimal:代价与最优串 行算法运行时间渐进相等——E= Q(1)
• 代价也称为工作量(work),处理器时 间积(processor-time product)

可扩展性

可扩展性是高性能并行机和并行算法追求的主要目标,其主要作用:
❑ 度量并行系统性能的方法之一
❑ 度量并行体系结构在不同系统规模下的并行
处理能力
❑ 度量并行算法内在的并行性
❑ 利用系统规模和问题规模已知的并行系统性 能来预测规模增大后的性能:scale down,
适合开发、调试,不适合性能预测

最后

以上就是光亮春天为你收集整理的并行算法分析并行算法分析的全部内容，希望文章能够帮你解决并行算法分析并行算法分析所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。