《中国科技大学并行计算课件5并行算法的一般设计方法》由会员分享，可在线阅读，更多相关《中国科技大学并行计算课件5并行算法的一般设计方法（14页珍藏版）》请在金锄头文库上搜索。
1、并 行 计 算 中国科学技术大学计算机科学与技术系国家高性能计算中心(合肥)2004年12月Date1现代密码学理论与实践之五第二篇 并行算法的设计 第四章 并行算法的设计基础 第五章 并行算法的一般设计方法 第六章 并行算法的基本设计技术 第七章 并行算法的一般设计过程Date2现代密码学理论与实践之五第五章 并行算法的一般设计方法 5.1 串行算法的直接并行化 5.2 从问题描述开始设计并行算法 5.3 借用已有算法求解新问题 Date3现代密码学理论与实践之五5.1串行算法的直接并行化 5.1.1 设计方法描述 5.1.2 快排序算法的并行化Date4现代密码学理论与实践之五 设计方法的
2、描述 方法描述 发掘和利用现有串行算法中的并行性，直接将串行算法改造为并行算法。 评注 由串行算法直接并行化的方法是并行算法设计的最常用方法之一； 不是所有的串行算法都可以直接并行化的； 一个好的串行算法并不能并行化为一个好的并行算法； 许多数值串行算法可以并行化为有效的数值并行算法。Date5现代密码学理论与实践之五5.1串行算法的直接并行化 5.1.1 设计方法描述 5.1.2 快排序算法的并行化Date6现代密码学理论与实践之五 快排序算法的并行化 算法5.2 PRAM-CRCW上的快排序二叉树构造算法 输入：序列(A1,An)和n个处理器 输出：供排序用的一棵二叉排序树 Begin (
3、1)for each processor i do (2)repeat for each processor iroot do (1.1)root=i if (AiAfi) (Ai=Afiifi) then (1.2)fi=root (2.1)LCfi=i (1.3)LCi=RCi=n+1 (2.2)if i=LCfi then exit else fi=LCfi endif end for else (2.3)RCfi=i (2.4)if i=RCfi then exit else fi=RCfi endif endif end repeat EndDate7现代密码学理论与实践之五第五章
4、并行算法的一般设计方法 5.1 串行算法的直接并行化 5.2 从问题描述开始设计并行算法 5.3 借用已有算法求解新问题 Date8现代密码学理论与实践之五 从问题描述开始设计并行算法 方法描述 从问题本身描述出发，不考虑相应的串行算法，设计一个全新的并行算法。 评注 挖掘问题的固有特性与并行的关系； 设计全新的并行算法是一个挑战性和创造性的工作； 利用串的周期性的PRAM-CRCW算法是一个很好的范例；Date9现代密码学理论与实践之五第五章 并行算法的一般设计方法 5.1 串行算法的直接并行化 5.2 从问题描述开始设计并行算法 5.3 借用已有算法求解新问题 Date10现代密码学理论与
5、实践之五5.3 借用已有算法求解新问题 5.3.1 设计方法描述 5.3.2 利用矩阵乘法求所有点对间最短路径Date11现代密码学理论与实践之五 设计方法的描述 方法描述 找出求解问题和某个已解决问题之间的联系； 改造或利用已知算法应用到求解问题上。 评注 这是一项创造性的工作； 使用矩阵乘法算法求解所有点对间最短路径是一个很好的范例。Date12现代密码学理论与实践之五5.3 借用已有算法求解新问题 5.3.1 设计方法描述 5.3.2 利用矩阵乘法求所有点对间最短路径Date13现代密码学理论与实践之五 利用矩阵乘法求所有点对间最短路径 计算原理 有向图G=(V,E)，边权矩阵W=(wi
6、j)nn，求最短路径长度矩阵D=(dij)nn，dij为vi到vj的最短路径长度。假定图中无负权有向回路，记d(k)ij为vi到vj至多有k-1个中间结点的最短路径长，Dk=(d(k)ij)nn，则 (1) d(1)ij=wij 当 ij (如果vi到vj之间无边存在记为) d(1)ij=0 当 i=j (2) 无负权回路 dijd(n-1)ij (3) 利用最优性原理：d(k)ij=min1lnd(k/2)il+d(k/2)lj 视：”+” “”， “min” “”，则上式变为 d(k)ij=1lnd(k/2)ild(k/2)lj (4) 应用矩阵乘法：D1 D2 D4 D2logn (= Dn) SIMD-CC上的并行算法：p139算法5.5Date14现代密码学理论与实践之五
