单击此处编辑母版标题样式,,单击此处编辑母版文本样式,,第二级,,第三级,,第四级,,第五级,,,*,并 行 计 算 基 础 知 识,,赵俊锋,,,西北工业大学理学院,,zhaojf,_77@,sina,.com,,,主要内容,,并行计算环境,,并行算法基础,,什么问题可以并行化,,串行程序如何改为并行程序,,,为什么需要并行计算机,,问题: 科学和工程问题的数值模拟与仿真,,计算密集,,数据密集,,网络密集,,三种混合,,要求:在合理的时限内完成计算任务,,秒级 制造业,,分钟级 短时天气预报(当天),,小时级 中期天气预报(3~10日),,尽可能快 长期天气预报(气候),,可计算 湍流模拟,,,,什么任务适合在超级计算环境内运行？,一般来说，计算量极大而使,PC,不能满足要求或者根本不能计算的任务是适合在超级计算环境中运行的比如，,,,,（1）需要分布式并行处理的科学计算任务，包括：由于对计算资源要求过大而使现在的硬件条件无法满足要求的计算任务，通过将串行源代码改编为并行源代码来进行计算，或者有通行的并行计算程序（商业或非商业）；,,（2）虽然可以计算但是时间过长的问题等并行计算机的分类,并行向量机（,PVP）,,对称多处理共享存储多处理机（,SMP）,,大规模并行处理机（,MPP）,,工作站（微机）机群（,COW）,,分布式共享存储多处理机（,DSM）,,,COW(,Cluster of Workstation,),,一个节点可以是一台,PC,或,SMP；,,各节点一般由商品化的网络互连；机群节点通过使用标准网络协议（,TCP/IP）,来通信。
使用的是千兆网每个节点一般有本地磁盘；,,节点上的网络接口是松散耦合到,I/O,总线上；,,每个节点有一个完整的操作系统,但是通过中间层实现了单一系统映像（,SSI）单一系统映像,单一系统映像（,Single System Image,，,SSI,）,并不是指系统中仅有唯一的操作系统映像驻留在内存，而只是感觉上，像一个单一系统其基本特征是单一系统、单一控制、对称性、位置透明采用,SSI,的主要目的，是使机群的使用、控制和维护似乎和一台工作站一样单一系统映像包括单一入口点、单一文件层次结构、单一,I/O,空间、单一网络、单一作业管理系统、单一存储空间和单一进程空间定 制 网 络,P/C,M,B,MB,LD,NIC,IOB,P/C,M,B,MB,LD,NIC,IOB,,,,并行机软件环境,,操作系统方面：,RatHat9.0,,程序设计语言：,Fortran 77、 Fortran 90、C/C++,等,,,什么是并行算法,,算法是解题的精确描述，是一组有穷的规则，它规定了解决某一特定类型问题的一系列运算并行计算时可同时求解的诸进程的集合，这些进程相互作用和协调动作，并最终获得问题的求解,,并行算法就是对并行计算过程的精确描述,,,并行算法的分类,,非数值计算并行算法,,数值计算并行算法，基于矩阵运算、多项式求解、线性方程组求解等代数关系运算的计算问题。
进程 1,,,,发送信息,进程 2,,,,接收信息,,传统的,串行计算,，,分为“指令”,,和“数据”两个部分，并在程序,,执行时“独立地申请和占有”内,,存空间，且所有计算均局限于,,该内存空间并行计算,将,进程相对独立的,,分配于不同的节点上，由,,各自独立的操作系统调度，,,享有独立的,CPU,和内存资源,,（内存可以共享）；进程间,,相互信息交换通过消息传递,；,,,进程 1,,,,,,进程 2,,,,,,进程间通信,,现代操作系统提供基本的系统调用函数，允许位于同一台处理机或不同处理机的多个进程之间相互交流信息，操作具体表现为三种形式：通信、同步和聚集以上的三种形式统称为进程间通信，操作的具体数据对象为消息，具体的操作为消息传递通信,,进程间的数据传递称为进程间通信在同一台处理机中，通信可以读/写操作系统提供的共享数据缓存区来实现不同处理机中，通信可以通过网络来实现同步,,同步是使位于相同或不同处理机中的多个进程之间的相互等待的操作，它要求进程的所有操作均必须等待到达某一控制状态之后才并行聚集,,聚集将位于相同后不同处理机中的多个进程的局部结果综合起来，通过某种操作，例如最大值、最小值、累加和，产生一个新的结果，存储在某个指定的或者所有的进程变量中。
共享存储,的模型和语言(适于,PVP, SMP, DSM),,X3H5,,Pthread,,OpenMP,,消息传递,的模型和语言(适于,MPP, Cluster, COW),,MPI (,Fortran, C,,Gamess,,,Vasp,),,PVM (,Fortran, C,),,数据并行,的模型和语言(适于在,MPP/Cluster,上实现,SPMD,应用),,Fortran 90,,HPF(High Performance Fortran),并行编程环境,,MPI(Message Passing Interface),,在当前所有的消息传递软件中, 最重要最流行的是,MPI,,它能运行在所有的并行平台上程序设计语言支持,C, Fortran,等,MPI,已经成为一种标准，,,它以与语言独立的形式来定义这个接口库, 这个定义不包含任何专用于某个特别的制造商、操作系统或硬件的特性. 由于这个原因,,MPI,在并行计算界被广泛地接受.,,,MPI,标准的实现包括,MPICH、LAM、IBM MPL,等多个版本，最常用和稳定的是,MPICH它,提供了与,C、Fortran,语言的绑定。
我们可以将,MPI,看成一个“库” ，目前使用的消息传递库是,MPICH 1.2,，,共有上百个接口，在,FORTRAN 77,和,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 –o exam exam.f,,mpirun,–,np,4 exam,,其中，,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+D,,P1,通过变量,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,=,A B,,其中,A,和,B,分别是,m k,和,k,,n,矩阵,,,C,是,m,,n,矩阵,.,不失一般性,,,假设,m,=,m,,p,,,k,=,k,,p,和,n,=,n,,p,串行程序,double a[N][N],b[N][N],c[N][N];,,for (i=0; i 矩阵,A,在各自进程中保持不变，,B,在处理机中每次循环向前移动一个处理机对应于前面所提到的四个步骤，矩阵乘法并行算法可做如下表述：,,1、将问题（矩阵乘法）分成,p,个任务，即将,C,的求解分成,p,块2、每个进程对应一个,C,块的求解组织进程间的通讯即将,B,的各个子块,send(),到各个进程通过,mpirun,运行,将进程映射到处理器上并行描述,,for,i,= 0,to,p,－,1,do,,l,＝,i,+,myid,mod,p,,C,l,,=,A,*,B,, mp1,＝,myid,+1 mod,p,, mm1,＝,myid,-1 mod,p,,if,i,！,=,p－,,1,, send(,B,, mm1),,recv,(,B,, mp1),,End,for,,,,,谢谢！,,。
