软件体系结构-并行计算.doc

计算机系统结构大作业 论文题目专 业 计算机科学与技术（软件工程） 指导教师 蔡启先 班 级 学 号 姓 名 日 期 广西工学院计算机学院并行计算介绍并行计算就是用多个处理器去共同完成一个计算任务，其目的是最大程度地减少任务完成的墙钟时间（即实际的物理时间，而不是CPU时间等。并行处理往往会增加总的CPU时间，因为与串行程序相比并行程序会增加一些并行指令）。在理想情况下，当我们用N个处理器去完成一个特定的计算任务时，我们希望所用的时间应该是单个处理器计算时间的1/N。这是并行计算的理想状态，称为线性加速，通常很难达到。当然也有特殊情况，即使用N个处理器计算，速度比单处理器处理提高N倍以上，称之为超线性加速。算法是解题的精确描述，是一组有穷的规则，它规定了解决某一特定类型问题的一系列运算。并行计算时可同时求解的诸进程的集合，这些进程相互作用和协调动作，并最终获得问题的求解。传统地，串行计算是指在单个计算机（具有单个中央处理单元）上执行软件写操作。CPU 逐个使用一系列指令解决问题，但其中只有一种指令可提供随时并及时的使用。并行计算是在串行计算的基础上演变而来，它努力仿真自然世界中的事务状态：一个序列中众多同时发生的、复杂且相关的事件。 并行计算的特点为利用并行计算，通常计算问题表现为以下特征： （1）将工作分离成离散部分，有助于同时解决； （2）随时并及时地执行多个程序指令； （3）多计算资源下解决问题的耗时要少于单个计算资源下的耗时。并行计算是相对于串行计算来说的，所谓并行计算分为时间上的并行和空间上的并行。 时间上的并行就是指流水线技术，而空间上的并行则是指用多个处理器并发的执行计算。 一般来说，计算量极大而使PC不能满足要求或者根本不能计算的任务是适合在超级计算环境中运行的。比如， （1）需要分布式并行处理的科学计算任务，包括：由于对计算资源要求过大而使现在的硬件条件无法满足要求的计算任务，通过将串行源代码改编为并行源代码来进行计算，或者有通行的并行计算程序（商业或非商业）；（2）虽然可以计算但是时间过长的问题等并行算法的实现并行算法行列划分算法通过分析矩阵相乘的过程，可以发现矩阵A的第i 行与矩阵B的第j列对应元素乘积的累加和即为矩阵C的第i行第j列元素，而这个过程与i值的顺序是无关的。上述矩阵的串行算法中，其3层循环均可并行化。由粒度大小分析可知，总应试图选取最外层循环并行化6。假定有P台处理器，其并行算法如下：设A，B都是nn矩阵，采用行列划分的方法将A，B分块，。如下形式。(2)由上式，C的值转化为P2个低级矩阵的乘积，每个乘积是独立的，可以并行计算。简单起见，不妨设n可被P整除，即A，B可均匀地分为P块，上述矩阵乘积可以用下面的并行算法7。(1) 数据存储。将Ai，Bi分别存入处理机i（i=1，2，p）的矩阵Ai，Bi中，其中Ai为n/pn矩阵，Bi 为nn/p矩阵，并令k=1；(2) 信息轮换传送。处理机i将Bi 中元素传送到第i+1台处理机（i=1，2，p-1）；第p台处理机将Bp中的元素传送到第1台处理机。即：若i+1p，则j=1；否则j=i+1，将处理机i中Bi的元素传送给处理机j，其中j=1，2，p；(3) 数据的并行计算。每台处理机并行计算AiBi，并根据Ai，Bi中元素在A，B中的位置，将结果存入其工作矩阵Ci中相应单元，Ci是一个n/pn矩阵；(4) 信息接收。每台处理机接收上一台处理机送来的信息，并存入其Bi中，覆盖Bi中原来的信息。即：若i-11，则j=p；否则j=i-1 ，处理机i接收处理机j传送来的信息；(5) 如果np，则令n=n+1，再goto(2)，并行计算AiBi，如果n=p，则各处理机并行计算AiBi，运行结束。第k次并行计算结果处理器i12PK=1A1B1A2B2APBPK=2A1BPA2B1APBP-1K=pA1B2A2B3APB1 矩阵相乘并行计算过程算法有P个进程，每个进程计算C矩阵的n/p行。计算一行所需的时间为O(n2)，所以每个进程的计算复杂度为O(n2*(n/p)=O(n3/p)；又由于各进程刚好同步一次，所以同步的开销为O(p)。因此，整个算法的时间复杂度为O(n3/p)+p)。可见，此方法能较大地节约计算机的工作单元，提高计算速度和效率。本文中采用的是行列划分算法实现矩阵相乘的并行化的，此外还有几种数据划分的方法，行行划分算法、列列划分算法、列行划分算法、cannon算法，这里就以行行划分和Cannon算法为例进行简单介绍。并行算法行行划分算法这里将矩阵A和B均划分为行块子矩阵，矩阵A的划分同行列划分中的相同，B的划分如下：(3) Ci为Ai相对应的C的第i个块，进一步把Ai按列分块与B的行分块相对应，记(4) (5)从而有 串行算法与并行算法的性能比较 在MPI并行环境中进行实验， MPI (Message PassingInterface 消息传递接口)作为目前最重要的并行编程工具，提供了丰富的消息传递库函数，极大方便了并行算法的实现。我们通过实验得到了矩阵并行计算的时间和串行计算的时间。如下表2所示。下面以实例来说明并行算法相对于串行算法的效率改进。表2 中共有8 组数据，每组数据表示两个随机生成的100 100阶矩阵的相乘。其中计算时间由 MPI提供的 MPI_Wtime 库函数求得(单位为秒)，并行计算使用了10个结点共开启100个进程完成。从表中可以看出，虽然进程间通信需要一定的时间，并行算法相对于串行算法在性能上有了很大改进。组数串行计算时间（s）并行计算时间（s）串行计算时间/并行计算时间10.0075980.0009118.3402920.0075390.0008668.7055430.0075550.0009358.1675740.0076030.0008558.8924050.0077030.0009278.3074460.0076550.0009038.4773070.0076420.0008758.7337180.0075660.0008658.74682 并行程序设计环境在当前并行机上，比较流行的并行编程环境可以分为三类：消息传递、共享存储和数据并行，它们的典型代表、可移植性、并行粒度、并行操作方式、数据存储模式、数据分配方式、学习难度、可扩展性等方面的比较如下：特征消息传递共享存储数据并行典型代表MPI、PVMOpenMPHPF可移植性所有流行并行机SMP.DSMSMP、DSN、MPP并行粒度进程级大粒度进程级细粒度进程级细粒度并行操作方式异步异步松散同步数据存储模式分布式存储共享存储共享存储数据分配方式显式隐式半隐式学习入门难度较难容易偏易可扩展性好较差一般由上表可以看出：(1)共享存储并行编程基于县城级细粒度并行，仅被SMP和DSM并行机所支持，可移植性不如消息传递并行编程。但是，由于它们支持数据的共享存储，所以并行编程的难度较小，但一般情形下，当处理机个数较多时，其并行性能明显不如消息传递编程。(2)消息传递并行编程基于大粒度的进程级并行，具有最好的可移植性，几乎被当前流行的各类并行机所支持，且具有很好的可扩展性。但是，消息传递并行编程只能支持进程间的分布存储模式，即各个进程只能直接访问其局部内存空间，而对其他进程的局部内存空间，而对其他进程的局部内存空间的访问只能通过消息传递来实现。因此，学习和使用消息传递并行编程的难度均大于共享存储和数据并行两种编程模式。 MPI简介对比MPI（ Message Passing Interface ）是一种基于消息传递的并行程序设计标准，它明确定义了一整套用户接口，而对于具体实现，除了给出了建议以外，并没有太多的限制。由于它在标准化方面所进行的努力，它已经成为了消息传递并行程序程序设计的代表和事实上的标准。在MPI标准的制定过程中，制定者希望MPI能够达到下面的三个目标：较高的通信性能较好的程序可移植性可以满足消息传递程序设计的各种要求由于MPI是一个库而不是一种程序语言，因此对MPI的使用必须和特定的程序语言结合起来进行。通常情况下，对一个MPI的实现，对FORTRAN和C语言的支持是基本的要求。在实际的系统中，MPI以程序库的形式出现，通过库函数接口给用户提供MPI规范定义的功能。这样的库被称为MPI实现。所有MPI的名字都有前缀“MPI_”，不管是常量、变量还是函数调用的名字都是这样。而在用户程序中自己定义的常量、变量、过程和函数调用不要以“MPI_”开头，以免造成错误。FORTRAN形式的MPI调用，一般全为大写（虽然FORTRAN语法不区分大小写），而C形式的MPI调用，则为MPI_Xxxx_xxx的形式（如上边的MPI_Comm_rank()）。所有MPI的FORTRAN子程序在最后的参数中都有一个返回代码，对于成功的函数调用，返回代码包含的值为MPI_SUCCESS，对于失败的函数调用，其错误代码依赖于具体的MPI实现。一些MPI操作是函数，没有这个参数，对MPI的C语言绑定，这个返回代码由函数的返回值直接给出，而不再作为参数。 总结多核处理器的普及与并行计算机的发展极大地促进了并行程序设计的发展，越来越多的领域尤其是高性能计算与进程通信等领域都使用了并行计算的实现方法。并介绍了几种矩阵相乘的并行算法。最后本文使用并行编程的一种重要工具MPI 实现了一种矩阵相乘的并行算法。通过对原问题进行建模分析，找出其计算的并行性，从而