并行计算方法题稿.ppt

LOGO 并行计算算法 并行计算机基础 并行算法的设计 并行数值算法算例 1.1 并行计算 并行计算(Parallel Computing) 是指在并行计算机或分布式计算机等一些高性能计算系统上所做的计算，其硬件基础是高性能并行计算机。并行计算的主要目的是以最快的速度求解数字庞大且过程繁杂的计算问题。 概念 1.2 并行计算机分类 1、单指令多数据流（SIMD）型并行 2、多指令多数据流（MIMD）型并行机： 并行向量处理机、大规模并行处理机、分存共享存储多处理机、对称多处理机、、工作站机群 并行计算机 就是由多个处理单元(处理器或计算机)组成的计算机系统，这些处理单元相互通信和协作，能快速、高效地求解大型复杂问题。 1.3 并行计算机体系结构 1、总线结构 2、网格结构 3、超立方体结构 并行计算机体系结构是指在所应用的并行 处理系统中各个节点机之间的连接方式。 1.4 基本性能指标 1、 CPU和存储器： 工作负载：执行时间、指令数目、浮点运算数。 并行执行时间：计算时间+并行开销时间+相互通信时间 存储器的层次结构：容量、延迟、带宽 2、 机器的成本，价格与性能/价格比 3、 加速比性能：Amdahi定律、Gustafson定律、Sun和Ni定律 2.1 并行算法设计 并行算法 是一些可同时执行的诸多进程的集合，这些进程相互作用和协调动作从而达到给定问题的解。 并行算法的复杂度： 运行时间、处理器数目、并行算法的成本、总运算量 2.2 设计策略技术 1、并行算法设计 串行算法的直接并行化 设计新的算法 借用已有并行算法 2、划分设计技术：均匀划分、方根划分、对数划分、功能划分 3、分治设计技术：平衡树技术、倍增设计技术、流水线设计技术 2.3 并行设计过程 1、任务划分：数据划分、功能划分 2、通信划分：局部/全局通信、结构化/非结构化、静态/动态、同步/异步 3、任务组合 4、处理器映射：负载平衡算法、任务调度算法 2.4并行计算编程环境 1、分布传递并行编程： 消息传递 MPI PVM并行虚拟机（Parallel Virtual Machine） 2.4并行计算编程环境 2、共享存储并行编程 OpenMP 是一种面向共享内存以及分布式共享内存的多处理器多线程并行编程语言 2.4并行计算实现过程 并行计算实现过程 3.1矩阵运算 Creativity 1、矩阵的划分： 带状划分：块带状划分、循环带状划分 棋盘划分：块棋盘划分、循环棋盘划分 2、矩阵的转置、矩阵向量乘法、矩阵乘法、矩阵分解、求逆、求特征值等 3.2 线性方程组的求解 Creativity 1、直接求解 奇偶归约求解 有回代的列主元高斯消去 无回代的高斯-约旦法 2、迭代算法 高斯-赛德尔迭代法 雅可比迭代法 超松弛迭代法 多重网格法 3.3 稀疏矩阵向量乘法算例 Creativity 1、坐标存储法 4 稀疏矩阵向量乘法算例 Creativity 2、矩阵向量串行算法 4 稀疏矩阵向量乘法算例 Creativity 3、矩阵向量的并行化分析 4 稀疏矩阵向量乘法算例 Creativity 4、矩阵向量并行算法 4 稀疏矩阵向量乘法算例 Creativity 5、 4 稀疏矩阵向量乘法算例 Creativity 6 参考文献: 并行计算-结构 算法 编程 [M]陈国良 基于MPI的矩阵运算并行算法研究[J] 周灿 * * LOGO * *