第4章—并行计算的基本设计技术.ppt

文档介绍：并行算法的基本设计技术
PA的一般设计方法
PA的基本设计过程
PA的常用设计技术
PA的一般设计方法
串行算法直接并行化
借用法
全新的方法
串行算法直接并行化
串行算法并非都可并行化
好的串行算法不一定直接是好的并行算法
很多数值运算都可直接并行化
串行算法直接并行化步骤
检测和开发现有程序内在的并行性
并行编码并行实现
借用法
找问题与原有方法之间的关系
设计相似算法
有丰富的经验基础
借用法
实例:
矩阵乘
组合优化原理
求现有点队的最短路径,节点i和节点j之间的距离用dijk表示
全新的方法
根据一个给定问题的描述,重新设计或发明一个并行算法
一般可以得到较好的并行算法
是一个具有挑战性和创新性工作
设计者应有较好的理解能力和设计背景
PA的基本设计过程
problem
P: partitioning
C: communication
A: Agglomeration
P1
P2
P3
M: mapping
划分(P)
目的
开发并行性的可行性
方法
数据分解+功能分解
规划
常用的数据,通信频率的进程分为一组
判据(Check list 的设计问题)