并行计算基础知识.

并行计算基础知识赵俊锋西北工业大学理学院[e-mail]主要内容并行计算环境并行算法基础什么问题可以并行化串行程序如何改为并行程序为什么需要并行计算机问题:科学和工程问题的数值模拟与仿真计算密集数据密集网络密集三种混合要求:在合理的时限内完成计算任务秒级制造业分钟级短时天气预报(当天)小时级中期天气预报(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进程间通信现代操作系统提供基本的系统调用函数，允许位于同一台处理机或不同处理机的多个进程之间相互交流信息，操作具体表现为三种形式：通信、同步和聚集。以上的三种形式统称为进程间通信，操作的具体数据对象为消息，具体的操作为消息传递。通信进程间的数据传递称为进程间通信。在同一台处理机中，通信可以读/写操作系统提供的共享数据缓存区来实现。不同处理机中，通信可以通过网络来实现。同步同步是使位于相同或不同处理机中的多个进程之间的相互等待的操作，它要求进程的所有操作均必须等待到达某一控制状态之后才并行。聚集聚集将位于相同后不同处理机中的多个进程的局部结果综合起来，通过某种操作，例如最大值、最小值、累加和，产生一个新的结果，存储在某个指定的或者所有的进程变量中。共享存储的模型和语言(适于PVP,SMP,DSM)X3H5,PthreadOpenMP消息传递的模型和语言(适于MPP,Cluster,COW)MPI(Fortran,C,Gamess,Vasp)PVM(Fortran,C)数据并行的模型和语言(适于在MPP/Cluster上实现SPMD应用)Fortran90HPF(HighPerformanceFortran)并行编程环境MPI(MessagePassingInterface)在当前所有的消息传递软件中,最重要最流行的是MPI,它能运行在所有的并行平台上。程序设计语言支持C,Fortran等。MPI已经成为一种标准，它以与语言独立的形式来定义这个接口库,这个定义不包含任何专用于某个特别的制造商、操作系统或硬件的特性.由于这个原因,MPI在并行计算界被广泛地接受.MPI标准的实现包括MPICH、LAM、IBMMPL等多个版本，最常用和稳定的是MPICH。它提供了与C、Fortran语言的绑定。我们可以将MPI看成一个“库”，目前使用的消息传递库是MPICH1.2，共有上百个接口，在FORTRAN77和C语言中可以直接对这些函数进行调用。多个进程通过调用这些函数（类似调用子程序），进行通信；Include文件C语言应用程序应有#include“mpi.h”Fortran语言应用程序应有#include‘mpif.h’MPI并行编程模式单程序多数据流模式（SPMD）多程序多数据流模式（MPMD）为了降低使用和维护并行应用软件的复杂度，一般采用SPMD模式MPI程序的SPMD执行模式一个程序同时启动多份,形成多个独立的进程，在不同的处理机上运行，拥有独立的内存空间，进程间通信通过调用MPI函数来实现；SPMD模式：单程序多数据流可执行代码运行复制多份并独立执行，形成多个独立的进程进程一（内存）进程二（内存）进程三（内存）消息传递（交换数据、同步、规约）协同例一进程0发送一个整数给进程1；进程1将该数加1，传递给进程2；进程2再将该数加1，再传递给进程3；依次类推，最后，进程N-1将该数传递给进程0，由进程1负责广播该数给所有进程，并打印输出。进程1传递信息进程3传递信息进程2传递信息进程0传递信息编译运行命令mpif77–oexamexam.fmpirun–np4exam其中，exam.f指需要编译的源文件，－o表示生成输出文件，exam指输出文件名，－np表示进程数。使用mpicc和mpif77省略了有关MPI的路径设置什么可以并行能否将顺序执行的程序转换成语义等价的、可并行执行的程序，主要取决于程序的结构形式，特别是其中的数据相关性。P1：A＝B+CP2：D＝A×B其中，变量A是导致P1和P2发生数据相关的原因。为了保证程序执行的语义正确性，变量A必须是先在P1中写入后方可从P2中读出，即必须先写后读。显然，P1和P2不能并行执行。数据相关数据反相关P1：A＝B×CP2：C＝E+DP1通过变量C数据相关于P2。为保证语义正确性，必须等P1将变量C读出后，P2方可向变量C进行写入操作，即必须先读后写。也不可并行化数据输出相关P1：A＝B+CP2：A＝D×E为保证语义正确性，必须保证P1先写入A，然后允许P2再写入A。除了上述3种相关外，还存在一种特殊情况，即两个程序段的输入变量互为输出变量。此时，两者必须并行执行，方可保证语义的正确性。这就要求硬件机构能保证两者进行同步读写。但若两个处理机各带有局部存储器，则可降低同步要求。相关性与可并行化伯恩斯坦准则I1∩O2＝Φ，即P1的输入变量集与P2的输出变量集不相交；I2∩O1＝Φ，即P2的输入变量集与P1的输出变量集不相交；O1∩O2＝Φ，即P1和P2的输出变量集不相交可并行处理如何将串行程序改为并行为理解创建一个并行程序中的步骤，让我们首先定义三个重要的概念:任务，进程和处理器。任务任务是程序要完成的一个工作，其内容和大小是随意的，它是并行程序所能处理的并发性最小的单元;即一个任务只能由一个处理器执行，处理器之间的并发性只能在任务之间开发。进程进程(我们也称为线程)是一个完成任务的实体。一个并行程序由许多合作的进程构成，每个完成程序中任务的一个子集。通过某种分配机制，任务被分配给进程。进程完成其任务的方式是通过在机器的物理处理器上执行进程与处理器的区别并行化的观点，：处理器是物理资源，进程是抽象，或者虚拟化多处理器的一种方便的方式:我们通过进程，而不是处理器来写并行程序;将进程映射到处理器是下一步。在一次程序的执行中，进程数不一定要等于处理器数。如果进程多，一个处理器有可能要执行多个进程;如果进程少，某些处理器则要闲置串行程序并行化的几个步骤从一个串行程序得到一个并行程序的工作由四个步骤构成：1.将计算的问题分解成任务2.将任务分配给进程3.在进程之间组织必要的数据访问，通信，和同步。4.将进程映射或绑定到处理器在以上的几个步骤中，并没有考虑并行的效率问题。考虑到消息传递的开销是计算开销的10倍以上，一般来说，如果在应用的一部分中，计算的时间是分钟级的而数据传输的时间是秒级的，那么这一部分可以并行执行。估计并行的效率例二：矩阵相乘C=AB其中A和B分别是mk和kn矩阵,C是mn矩阵.不失一般性,假设m=mp,k=kp和n=np。串行程序doublea[N][N],b[N][N],c[N][N];for(i=0;iN;i++)for(j=0;jN;j++)for(k=0;kN;k++)c[i][j]+=a[i][k]*b[k][j];并行实现先将矩阵分块110110,,,,,PTTPTTBBBBAAAA将存放在中，使数据在处理机中不重复。矩阵A在各自进程中保持不变，B在处理机中每次循环向前移动一个处理机。1,,0,,,pjCBAjiii和iP110110110,,pppBBBAAACCC对应于前面所提到的四个步骤，矩阵乘法并行算法可做如下表述：1、将问题（矩阵乘法）分成p个任务，即将C的求解分成p块。2、每个进程对应一个C块的求解。组织进程间的通讯。即将B的各个子块send()到各个进程。通过mpirun运行,将进程映射到处理器上。并行描述fori=0top－1dol＝i+myidmodpCl=A*B,mp1＝myid+1modp,mm1＝myid-1modpifi！=p－1,send(B,mm1),recv(B,mp1)Endfor谢谢！