中国科技大学并行计算课件7并行算法的一般设计过程
50页1、并 行 计 算 中国科学技术大学计算机科学与技术系中国科学技术大学计算机科学与技术系国家高性能计算中心国家高性能计算中心( (合肥合肥) )20042004年年1212月月第二篇 并行算法的设计 第四章 并行算法的设计基础 第五章 并行算法的一般设计方法 第六章 并行算法的基本设计技术 第七章 并行算法的一般设计过程第七章 并行算法的一般设计过程 7.1 PCAM设计方法学 7.2 划分 7.3 通讯 7.4 组合 7.5 映射 7.6 小结 PCAM设计方法学设计并行算法的四个阶段 划分划分(Partitioning)(Partitioning) 通讯通讯(Communication)(Communication) 组合组合(Agglomeration)(Agglomeration) 映射映射(Mapping)(Mapping)划分:分解成小的任务,开拓并发性;分解成小的任务,开拓并发性;通讯:确定诸任务间的数据交换,监测划分的合理性;确定诸任务间的数据交换,监测划分的合理性;组合:依据任务的局部性,组合成更大的任务;依据任务的局部性,组合成更大的任务;映射:将每个任务分配到处理器上
2、,提高算法的性能。将每个任务分配到处理器上,提高算法的性能。2022/3/294国家高性能计算中心(合肥) PCAM设计过程2022/3/295国家高性能计算中心(合肥)第七章 并行算法的一般设计过程 7.1 PCAM设计方法学 7.2 划分 7.3 通讯 7.4 组合 7.5 映射 7.6 小结 7.2 划分 7.2.1 方法描述 7.2.2 域分解 7.2.3 功能分解 7.2.4 划分判据 划分方法描述充分开拓算法的并发性和可扩放性;先进行数据分解(称域分解),再进行计算功能的分解(称功能分解);使数据集和计算集互不相交;划分阶段忽略处理器数目和目标机器的体系结构;能分为两类划分: 域分解域分解( (domain decompositiondomain decomposition) ) 功能分解功能分解( (functional decompositionfunctional decomposition) )2022/3/298国家高性能计算中心(合肥)7.2 划分 7.2.1 方法描述 7.2.2 域分解 7.2.3 功能分解 7.2.4 划分判据域分解 划分的对象是数据,可以
3、是算法的输入数据、中间处理数据和输出数据;将数据分解成大致相等的小数据片;划分时考虑数据上的相应操作;如果一个任务需要别的任务中的数据,则会产生任务间的通讯;2022/3/2910国家高性能计算中心(合肥)域分解 示例:三维网格的域分解,各格点上计算都是重复的。下图是三种分解方法:2022/3/2911国家高性能计算中心(合肥)域分解 不规则区域的分解示例:2022/3/2912国家高性能计算中心(合肥)7.2 划分 7.2.1 方法描述 7.2.2 域分解 7.2.3 功能分解 7.2.4 划分判据功能分解 划分的对象是计算,将计算划分为不同的任务,其出发点不同于域分解;划分后,研究不同任务所需的数据。如果这些数据不相交的,则划分是成功的;如果数据有相当的重叠, 意味着要重新进行域分解和功能分解;功能分解是一种更深层次的分解。2022/3/2914国家高性能计算中心(合肥)功能分解 示例示例1 1:搜索树:搜索树示例示例2 2:气候模型:气候模型2022/3/2915国家高性能计算中心(合肥)7.2 划分 7.2.1 方法描述 7.2.2 域分解 7.2.3 功能分解 7.2.4 划
4、分判据划分判据 划分是否具有灵活性?划分是否避免了冗余计算和存储?划分任务尺寸是否大致相当?任务数与问题尺寸是否成比例?功能分解是一种更深层次的分解,是否合理?2022/3/2917国家高性能计算中心(合肥)第七章 并行算法的一般设计过程 7.1 PCAM设计方法学 7.2 划分 7.3 通讯 7.4 组合 7.5 映射 7.6 小结 7.3 通讯 7.3.1 方法描述 7.3.2 四种通讯模式 7.3.3 通讯判据 通讯方法描述通讯是PCAM设计过程的重要阶段;划分产生的诸任务,一般不能完全独立执行,需要在任务间进行数据交流;从而产生了通讯;功能分解确定了诸任务之间的数据流;诸任务是并发执行的,通讯则限制了这种并发性;2022/3/2920国家高性能计算中心(合肥)7.3 通讯 7.3.1 方法描述 7.3.2 四种通讯模式 7.3.3 通讯判据 四种通讯模式局部/全局通讯结构化/非结构化通讯静态/动态通讯同步/异步通讯2022/3/2922国家高性能计算中心(合肥)局部通讯通讯限制在一个邻域内2022/3/2923国家高性能计算中心(合肥)全局通讯通讯非局部的例如:All to A
《中国科技大学并行计算课件7并行算法的一般设计过程》由会员东***分享,可在线阅读,更多相关《中国科技大学并行计算课件7并行算法的一般设计过程》请在金锄头文库上搜索。
幼儿园大班科学活动《智能留言机》课件
幼儿园大班语言绘本阅读《手电筒看见了什么》PPT
幼儿园小班科学《教宝宝认识动物》课件
幼儿园中班语言《灰狼家的小饭桶们》教案
【国家审计报告】审计报告W-06审计处罚决定书
【企业财务管理办法】会计档案管理办法
【员工主动离职-风险防范】劳动争议判决书
【员工被动离职-后续工作】70-070员工违反有关商业秘密的约定可以索赔吗
【员工被动离职-辞退申请】第六节 员工任免通知书
【员工被动离职-后续工作】70-050因员工的原因使服务期无法完成可以索赔吗
企业岗位管理制度12办公室行为规范
企业岗位管理制度30离职人员薪资发放通知单
幼儿园春游活动美丽的公园教案
呼职院电力机车制动机讲义11高速列车和重载列车制动
武理工《运输管理》教案第1章 运输系统
中海大海洋化学讲义02海洋的形成和海水的组成——兼论地球上水的起源、变迁和循环
武理工船舶柴油机习题库及答案04燃油喷射和燃烧
厦大海洋生态学课件07海洋初级生产力
华北理工水声学课件05声波在目标上的反射和散射-1目标强度及常见声纳目标的目标强度的一般特征
武理工船舶结构与设备课件02船体结构与管系-4专用船特殊船体结构特点
2022-03-24 39页
2022-03-24 45页
2022-03-24 14页
2022-03-24 37页
2022-03-24 17页
2021-11-22 77页
2021-11-22 68页
2021-11-22 55页
2021-11-22 96页