文档介绍：并行计算
中国科学技术大学计算机科学与技术系
国家高性能计算中心(合肥)
2003年9月
2017/11/10
1
现代密码学理论与实践之五
第二篇并行算法的设计 第四章并行算法的设计基础 第五章并行算法的一般设计方法 第六章并行算法的基本设计技术 第七章并行算法的一般设计过程
2017/11/10
2
现代密码学理论与实践之五
第七章并行算法的一般设计过程 PCAM设计方法学 划分 通讯 组合 映射 小结
2017/11/10
3
现代密码学理论与实践之五
PCAM设计方法学
设计并行算法的四个阶段
划分(Partitioning)
munication)
组合(Agglomeration)
映射(Mapping)
划分:分解成小的任务,开拓并发性;
通讯:确定诸任务间的数据交换,监测划分的合理性;
组合:依据任务的局部性,组合成更大的任务;
映射:将每个任务分配到处理器上,提高算法的性能。
2017/11/10
4
现代密码学理论与实践之五
PCAM设计过程
2017/11/10
5
现代密码学理论与实践之五
第七章并行算法的一般设计过程 PCAM设计方法学 划分 通讯 组合 映射 小结
2017/11/10
6
现代密码学理论与实践之五
划分 方法描述 域分解 功能分解 划分判据
2017/11/10
7
现代密码学理论与实践之五
划分方法描述
充分开拓算法的并发性和可扩放性;
先进行数据分解(称域分解),再进行计算功能的分解(称功能分解);
使数据集和计算集互不相交;
划分阶段忽略处理器数目和目标机器的体系结构;
能分为两类划分:
域分解(domain position)
功能分解(functional position)
2017/11/10
8
现代密码学理论与实践之五
划分 方法描述 域分解 功能分解 划分判据
2017/11/10
9
现代密码学理论与实践之五
域分解
划分的对象是数据,可以是算法的输入数据、中间处理数据和输出数据;
将数据分解成大致相等的小数据片;
划分时考虑数据上的相应操作;
如果一个任务需要别的任务中的数据,则会产生任务间的通讯;
2017/11/10
10
现代密码学理论与实践之五