对串行机而言, 解法 = 唯一串行算法+计算程序(通用)
对并行机而言, 解法 = 某种并行算法+有针对性的计算程序(很难通 用)
J人
稀少而初级的并行编程人员 vs. 成熟而经验丰富的串行程序员
2004年4月
12/149
第12页/共27页
一些途径
充分利用顺序程序开发的经验、方法和工具，特别是顺序 领域中的问题求解、算法设计方法，这是简化并行程序开 发的重要手段。
并行程序开发的困难主要在于问题的并行求解，而不是并 行程序设计语言。“从事并行程序设计实践的人往往把精 力耗费在为变量分配内存、为循环体寻求并行上，却忽略 对问题本身的分析。其实能否并行的决定因素是应用问题 本身。”
在并行算法的设计阶段最大限度地开发出问题本身固有的 并行性才是提高计算效率的根本手段。只有粗粒度的并行 ，才能具有高的计算通信比，而粗粒度的并行只能在算法 设计阶段开发出来
2004年4月
11/149
第11页/共27页
??
编程环境
落后的并行编译器、调试器 vs. 通用先进的串行编程环境. 自动并行编译器远远满足不了程序并行化的要求.
3算法
并行模型的多样化(并行计算机系统结构的多样性) vs. 串行编程中 的唯一模型: 冯.诺依曼模型
问题的并行求解的困难在于问题的多样性和求解过程中所需的创 造性劳动，使得这一过程难以进行自动化
10
第10页/共27页
并行计算软件环境及现状
操作系统：UNIX、LINUX、Windows NT
在SMP,DSM并行机上编译系统通常具有一定的对用户程 序(C/Fortran) 进程自动并行化的能力,但经常需要人工干 预 (通过编译制导,命令行选项等) 以达到理想的并行效率. 且并行主要针对循环进行 (属于细粒度并行);
2004年4月
13/149
第13页/共27页
并行编程环境
常见的并行编程环境 消息传递、共享存储、数据并行
特征
消息传递
共享数据
数据并行
典型代表 可移植性 存储方式 学习难度 可扩展性
MPI，PVM 所有流行并行机 分布式存储 较难 好
OpenMP SMP，DSM 共享存储 容易 较差
HPF SMP，DSM，MPP 共享存储 偏易 一般
并行计算机体系 结构示意图 内存模块位于 结点内部
9
第9页/共27页
操作系统与编程语言
并行计算机主流操作系统：UNIX / Linux
AIX（IBM） HPUX（HP） Solaris（SUN） IRIX（SGI） Linux
编程语言
Fortran 77/90/95 C/C++
2004年4月
5/149
第5页/共27页
并行计算的特点
为利用并行计算，通常计算问题表现为以下特征：
（1）将工作分离成离散部分，有助于同时解决；
（2）随时并及时地执行多个程序指令；
（3）多计算资源下解决问题的耗时要少于单个计算 资源下的耗时。
并行计算是相对于串行计算来说的，并行计算分为 时间上的并行和空间上的并行。 时间上的并行就是指流 水线技术，而空间上的并行则是指用多个处理器并发的 执行计算。
2004年4月
2/149
第2页/共27页
现代计算机的共同特点 ：
并行性
2004年4月
3/149
第3页/共27页
如何实现并行计算?
分而治之!
Hale Waihona Puke 2004年4月4/149第4页/共27页
分而治之
并行化的主要方法:分而治之
根据问题的求解过程，把任务分成若干子任务(任 务级并行或功能并行)
根据处理数据的方式，形成多个相对独立的数据区 ，由不同的处理器分别处理(数据并行)
三种并行编程环境主要特征一览
14
第14页/共27页
实现并行编程常见方法
1.线程模型（OpenMP,POSIX) 2.消息传递模型（PVM，MPI）
PVM:Parallel Virtual Machine Computing MPI:Message Passing Interface
3.数据并行模型（HPF）
SISD
SIMD
第7页/共27页
MIMD
并行计算机体系结构
组成要素
结点（node）：一个或多个处理器组成 互联网络（interconnetct network）：连接结点 内存（memory）：多个存储模块组成
8
第8页/共27页
并行计算机体系结构
并行计算机体系 结构示意图 内存模块与结点分离
第15页/共27页
三者可混合使用:
如对以SMP为节点的Cluster来说 , 可以在节点间进行消息传递,在 节点内进行共享变量编程.
第16页/共27页
并行算法
并行算法
适合在并行机上实现的算法 好的并行算法应充分发挥并行机计算机的潜在性能
并行算法分类
按运算对象：数值并行算法、非数值并行算法 按并行进程执行顺序：
第6页/共27页
并行计算机的分类
并行计算科学中主要研究的是空间上的并行问题。 空间上 的并行导致了两类并行机的产生，按照Flynn的说法分为： 单指令流多数据流（SIMD）和多指令流多数据流（MIMD Multiple Instruction Stream Multiple Data Stream ）。我 们常用的串行机也叫做单指令流单数据流（SISD）。
同步并行算法、异步并行算法、独立并行算法 按计算任务：
细粒度并行算法（基于向量和循环级并行） 中粒度并行算法（基于较大的循环级并行） 大粒度并行算法（基于子任务级并行）
17
第17页/共27页
并行的层次
在分布式内存并行机上尚无通过高效的自动并行工具,主 要依靠人工编写并行程序;
并行算法的设计及并行程序的编制已成为目前特约大规模 并行计算机应用的主要障碍.
并行编程现状
: 并行软件开发远远落后于并行系统体系结构的发展。缺少合适的 并行软件是阻碍主流用户社会接纳并行计算的原因。
: 与串行软件相比，并行软件数量少，功能原始。
什么是并行计算?
并行计算: 由运行在多个部件上的小任务合作来求解一个 规模很大的计算问题的一种方法
例: 在曙光2000上用8个节点计算的Mandelbrot集结果 (Mandelbrot为分形理论创始人)
zi1 zi2 c
2004年4月
1/149
第1页/共27页
现代计算机的共同特点： 并行性