并行计算基础知识.ppt

数据反相关P1：A＝B×CP2：C＝E+DP1通过变量C数据相关于P2。为保证语义正确性，必须等P1将变量C读出后，P2方可向变量C进行写入操作，即必须先读后写。也不可并行化数据输出相关P1：A＝B+CP2：A＝D×E为保证语义正确性，必须保证P1先写入A，然后允许P2再写入A。除了上述3种相关外，还存在一种特殊情况，即两个程序段的输入变量互为输出变量。此时，两者必须并行执行，方可保证语义的正确性。这就要求硬件机构能保证两者进行同步读写。但若两个处理机各带有局部存储器，则可降低同步要求。相关性与可并行化伯恩斯坦准则I1∩O2＝Φ，即P1的输入变量集与P2的输出变量集不相交；I2∩O1＝Φ，即P2的输入变量集与P1的输出变量集不相交；O1∩O2＝Φ，即P1和P2的输出变量集不相交可并行处理如何将串行程序改为并行为理解创建一个并行程序中的步骤，让我们首先定义三个重要的概念:任务，进程和处理器。任务任务是程序要完成的一个工作，其内容和大小是随意的，它是并行程序所能处理的并发性最小的单元;即一个任务只能由一个处理器执行，处理器之间的并发性只能在任务之间开发。进程进程(我们也称为线程)是一个完成任务的实体。一个并行程序由许多合作的进程构成，每个完成程序中任务的一个子集。通过某种分配机制，任务被分配给进程。进程完成其任务的方式是通过在机器的物理处理器上执行主要内容并行计算环境并行算法基础什么问题可以并行化串行程序如何改为并行程序为什么需要并行计算机问题:科学和工程问题的数值模拟与仿真计算密集数据密集网络密集三种混合要求:在合理的时限内完成计算任务秒级 制造业分钟级 短时天气预报(当天)小时级 中期天气预报(3~10日)尽可能快 长期天气预报(气候)可计算 湍流模拟什么任务适合在超级计算环境内运行？一般来说，计算量极大而使PC不能满足要求或者根本不能计算的任务是适合在超级计算环境中运行的。比如，（1）需要分布式并行处理的科学计算任务，包括：由于对计算资源要求过大而使现在的硬件条件无法满足要求的计算任务，通过将串行源代码改编为并行源代码来进行计算，或者有通行的并行计算程序（商业或非商业）；（2）虽然可以计算但是时间过长的问题等。并行计算机的分类并行向量机（PVP）对称多处理共享存储多处理机（SMP）大规模并行处理机（MPP）工作站（微机）机群（COW）分布式共享存储多处理机（DSM）COW(ClusterofWorkstation)一个节点可以是一台PC或SMP；各节点一般由商品化的网络互连；机群节点通过使用标准网络协议（TCP/IP）来通信。使用的是千兆网。每个节点一般有本地磁盘；节点上的网络接口是松散耦合到I/O总线上；每个节点有一个完整的操作系统,但是通过中间层实现了单一系统映像（SSI）。单一系统映像单一系统映像（SingleSystemImage，SSI）并不是指系统中仅有唯一的操作系统映像驻留在内存，而只是感觉上，像一个单一系统。其基本特征是单一系统、单一控制、对称性、位置透明。采用SSI的主要目的，是使机群的使用、控制和维护似乎和一台工作站一样。单一系统映像包括单一入口点、单一文件层次结构、单一I/O空间、单一网络、单一作业管理系统、单一存储空间和单一进程空间。定制网络P/CMBMBLDNICIOBP/CMBMBLDNICIOB并行机软件环境操作系统方面：RatHat9.0程序设计语言：Fortran77、Fortran90、C/C++等什么是并行算法算法是解题的精确描述，是一组有穷的规则，它规定了解决某一特定类型问题的一系列运算。并行计算时可同时求解的诸进程的集合，这些进程相互作用和协调动作，并最终获得问题的求解并行算法就是对并行计算过程的精确描述并行算法的分类非数值计算并行算法数值计算并行算法，基于矩阵运算、多项式求解、线性方程组求解等代数关系运算的计算问题。进程1发送信息进程2接收信息传统的串行计算，分为“指令”和“数据”两个部分，并在程序执行时“独立地申请和占有”内存空间，且所有计算均局限于该内存空间。并行计算将进程相对独立的分配于不同的节点上，由各自独立的操作系统调度，享有独立的CPU和内存资源（内存可以共享）；进程间相互信息交换通过消息传递；进程1进程2进程间通信现代操作系统提供基本的系统调用函数，允