并行计算方法ppt课件.ppt

《并行计算方法ppt课件.ppt》由会员分享，可在线阅读，更多相关《并行计算方法ppt课件.ppt（21页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、LOGO 并行计算算法并行计算算法并行计算机基础并行计算机基础并行算法的设计并行算法的设计并行数值算法算例并行数值算法算例1.1 1.1 并行计算并行计算并行计算并行计算(Parallel Computing)是指在并行计算机或分布式计算机等一些高性能计算系统上所做的计算，其硬件基础是高性能并行计算机。并行计算的主要目的是以最快的速度求解数字庞大且过程繁杂的计算问题。概念概念1.2 1.2 并行计算机分类并行计算机分类1、单指令多数据流（SIMD）型并行2、多指令多数据流（MIMD）型并行机： 并行向量处理机、大规模并行处理机、分存共享存储多处理机、对称多处理机、工作站机群并行计算机就是由多个

2、处理单元(处理器或计算机)组成的计算机系统，这些处理单元相互通信和协作，能快速、高效地求解大型复杂问题。1.3 1.3 并行计算机体系结构并行计算机体系结构1、总线结构 2、网格结构 3、超立方体结构并行计算机体系结构是指在所应用的并行处理系统中各个节点机之间的连接方式。1.4 1.4 基本性能指标基本性能指标1、 CPU和存储器： 工作负载：执行时间、指令数目、浮点运算数。 并行执行时间：计算时间+并行开销时间+相互通信时间 存储器的层次结构：容量、延迟、带宽2、 机器的成本，价格与性能/价格比3、 加速比性能：Amdahi定律、Gustafson定律、Sun和Ni定律2.1 2.1 并行算

3、法设计并行算法设计并行算法并行算法是一些可同时执行的诸多进程的集合，这些进程相互作用和协调动作从而达到给定问题的解。并行算法的复杂度：运行时间、处理器数目、并行算法的成本、总运算量2.2 2.2 设计策略技术设计策略技术1、并行算法设计 串行算法的直接并行化 设计新的算法 借用已有并行算法2、划分设计技术：均匀划分、方根划分、对数划分、功能划分3、分治设计技术：平衡树技术、倍增设计技术、流水线设计技术2.3 2.3 并行设计过程并行设计过程1、任务划分：数据划分、功能划分2、通信划分：局部/全局通信、结构化/非结构化、静态/动态、同步/异步3、任务组合4、处理器映射：负载平衡算法、任务调度算法

4、2.42.4并行计算编程环境并行计算编程环境1、分布传递并行编程：v 消息传递 MPIMPIv PVM并行虚拟机（Parallel Virtual Machine） 2.42.4并行计算编程环境并行计算编程环境2、共享存储并行编程v OpenMP 是一种面向共享内存以及分布式共享内存的多处理器多线程并行编程语言2.42.4并行计算实现过程并行计算实现过程并行计算实现过程并行计算实现过程3.13.1矩阵运算矩阵运算Creativity1、矩阵的划分： 带状划分：块带状划分、循环带状划分 棋盘划分：块棋盘划分、循环棋盘划分2、矩阵的转置、矩阵向量乘法、矩阵乘法、矩阵分解、求逆、求特征值等3.2 3

5、.2 线性方程组的求解线性方程组的求解Creativity1、直接求解 奇偶归约求解 有回代的列主元高斯消去 无回代的高斯-约旦法2、迭代算法 高斯-赛德尔迭代法 雅可比迭代法 超松弛迭代法 多重网格法3.3 3.3 稀疏矩阵向量乘稀疏矩阵向量乘法算例法算例Creativity1、坐标存储法4 4 稀疏矩阵向量乘稀疏矩阵向量乘法算例法算例Creativity2、矩阵向量串行算法4 4 稀疏矩阵向量乘稀疏矩阵向量乘法算例法算例Creativity3、矩阵向量的并行化分析4 4 稀疏矩阵向量乘稀疏矩阵向量乘法算例法算例Creativity4、矩阵向量并行算法4 4 稀疏矩阵向量乘稀疏矩阵向量乘法算例法算例Creativity5、4 4 稀疏矩阵向量乘稀疏矩阵向量乘法算例法算例Creativity6LOGO参考文献:并行计算-结构 算法 编程 M陈国良基于MPI的矩阵运算并行算法研究J 周灿