并行算法设计曹振南.ppt

文档介绍：;
并行算法设计
1
主要内容
基本知识及现状
并行计算性能评测
并行算法的一般设计方法
并行算法的基本设计技术
并行算法的一般设计过程
例子
2
现代计算机的共同特点：并行性
3
现代计算机的共同特点：并行性
4
并行:古老的思想!
“... 并行计算并不是什么新的思想,只是将它扩展应用于计算机而已. 作者也不认为这种扩展应用会存在什么无法克服的困难. 但也不要期待有效的并行编程方法与技术能够在一夜之间诞生. 期间还需要有许多的工作和实验要做. 毕竟, 今天的编程技术(串行)是若干年来艰苦的探索才取得的. 现在编程工作似乎成了一种令人单调乏味的工作,事实上,并行编程的出现将会使重新恢复编程工作者们的探索精神 ...”
(Gill, S. (1958), “Parallel Programming,” The Computer Journal, vol. 1, April, pp. 2-10.)
Parallel Programming with MPI
by Peter Pacheco(2000)
5
综述——为什么要做并行计算
从系统的角度：集成系统资源，以满足不断增长的对性能和功能的要求
从应用的角度：适当分解应用，以实现更大规模或更细致的计算
6
并行计算的功能?
降低单个问题求解的时间.
增加问题求解规模.
提高吞吐率(多机同时执行多个串行程序).
7
并行计算?
资料来源:
Tim Mattson Intel Co. Com. Science Lab.
Rudolf Eigenmann Purdue Uni. School of Elec. and Comp. Eng.
分而治之!
8
并行计算现状(硬件)
共享内存SMP并行计算机
对称多处理器或共享内存处理器
多个处理器通过系统总线或者交叉开关共享一个或者多个内存模块
优点：使用简单，维护方便
缺点：受系统总线带宽限制，只能支持少量处理器（十几个）
并行编程方式：通常OpenMP，也可用消息传递(PVM/MPI)及HPF
代表机型：SGI PowerChanlenge;SUN E10000等
9
并行计算现状(硬件)
分布内存MPP型计算机
Massively Paralleled Processors的简称
指由大量具有局部内存的计算节点通过高速系统网络连接而成的并行处理系统
MPP系统的系统网络通常具有某种拓扑结构（Tree,Mesh,Torus,Hypercuber）
10