中国科技大学并行计算课件5并行算法的一般设计方法
14页1、并 行 计 算 中国科学技术大学计算机科学与技术系国家高性能计算中心(合肥)2004年12月Date1现代密码学理论与实践之五第二篇 并行算法的设计 第四章 并行算法的设计基础 第五章 并行算法的一般设计方法 第六章 并行算法的基本设计技术 第七章 并行算法的一般设计过程Date2现代密码学理论与实践之五第五章 并行算法的一般设计方法 5.1 串行算法的直接并行化 5.2 从问题描述开始设计并行算法 5.3 借用已有算法求解新问题 Date3现代密码学理论与实践之五5.1串行算法的直接并行化 5.1.1 设计方法描述 5.1.2 快排序算法的并行化Date4现代密码学理论与实践之五 设计方法的描述 方法描述 发掘和利用现有串行算法中的并行性,直接将串行算法改造为并行算法。 评注 由串行算法直接并行化的方法是并行算法设计的最常用方法之一; 不是所有的串行算法都可以直接并行化的; 一个好的串行算法并不能并行化为一个好的并行算法; 许多数值串行算法可以并行化为有效的数值并行算法。Date5现代密码学理论与实践之五5.1串行算法的直接并行化 5.1.1 设计方法描述 5.1.2 快排序算法的并
2、行化Date6现代密码学理论与实践之五 快排序算法的并行化 算法5.2 PRAM-CRCW上的快排序二叉树构造算法 输入:序列(A1,An)和n个处理器 输出:供排序用的一棵二叉排序树 Begin (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现代密码学理论与实践之五第五章 并行算法的一般设计方法 5.1 串行算法的直接并行化 5.2 从问题描述开始设计并行算法 5.3 借用已有算法求解新问题 Date8现代密码学理论与实践之五 从问题描述开始设计并行算法 方法描述 从问
3、题本身描述出发,不考虑相应的串行算法,设计一个全新的并行算法。 评注 挖掘问题的固有特性与并行的关系; 设计全新的并行算法是一个挑战性和创造性的工作; 利用串的周期性的PRAM-CRCW算法是一个很好的范例;Date9现代密码学理论与实践之五第五章 并行算法的一般设计方法 5.1 串行算法的直接并行化 5.2 从问题描述开始设计并行算法 5.3 借用已有算法求解新问题 Date10现代密码学理论与实践之五5.3 借用已有算法求解新问题 5.3.1 设计方法描述 5.3.2 利用矩阵乘法求所有点对间最短路径Date11现代密码学理论与实践之五 设计方法的描述 方法描述 找出求解问题和某个已解决问题之间的联系; 改造或利用已知算法应用到求解问题上。 评注 这是一项创造性的工作; 使用矩阵乘法算法求解所有点对间最短路径是一个很好的范例。Date12现代密码学理论与实践之五5.3 借用已有算法求解新问题 5.3.1 设计方法描述 5.3.2 利用矩阵乘法求所有点对间最短路径Date13现代密码学理论与实践之五 利用矩阵乘法求所有点对间最短路径 计算原理 有向图G=(V,E),边权矩阵W=(wij)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现代密码学理论与实践之五
《中国科技大学并行计算课件5并行算法的一般设计方法》由会员东***分享,可在线阅读,更多相关《中国科技大学并行计算课件5并行算法的一般设计方法》请在金锄头文库上搜索。
幼儿园大班科学活动《智能留言机》课件
幼儿园大班语言绘本阅读《手电筒看见了什么》PPT
幼儿园小班科学《教宝宝认识动物》课件
幼儿园中班语言《灰狼家的小饭桶们》教案
【国家审计报告】审计报告W-06审计处罚决定书
【企业财务管理办法】会计档案管理办法
【员工主动离职-风险防范】劳动争议判决书
【员工被动离职-后续工作】70-070员工违反有关商业秘密的约定可以索赔吗
【员工被动离职-辞退申请】第六节 员工任免通知书
【员工被动离职-后续工作】70-050因员工的原因使服务期无法完成可以索赔吗
企业岗位管理制度12办公室行为规范
企业岗位管理制度30离职人员薪资发放通知单
幼儿园春游活动美丽的公园教案
呼职院电力机车制动机讲义11高速列车和重载列车制动
武理工《运输管理》教案第1章 运输系统
中海大海洋化学讲义02海洋的形成和海水的组成——兼论地球上水的起源、变迁和循环
武理工船舶柴油机习题库及答案04燃油喷射和燃烧
厦大海洋生态学课件07海洋初级生产力
华北理工水声学课件05声波在目标上的反射和散射-1目标强度及常见声纳目标的目标强度的一般特征
武理工船舶结构与设备课件02船体结构与管系-4专用船特殊船体结构特点
2022-03-29 50页
2022-03-24 39页
2022-03-24 45页
2022-03-24 37页
2022-03-24 17页
2021-11-22 77页
2021-11-22 68页
2021-11-22 55页
2021-11-22 96页