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

《计算机系统结构》大作业 论文题目 专 业 计算机科学与技术（软件工程） 指导教师 蔡启先 班 级 学 号 姓 名 日 期 广西工学院计算机学院 并行计算介绍 并行计算就是用多个处理器去共同完成一个计算任务，其目的是最大程度地减少任务完成的墙钟时间（即实际的物理时间，而不是CPU时间等。并行处理往往会增加总的CPU时间，因为与串行程序相比并行程序会增加一些并行指令）。在理想情况下，当我们用N个处理器去完成一个特定的计算任务时，我们希望所用的时间应该是单个处理器计算时间的1/N。这是并行计算的理想状态，称为线性加速，通常很难达到。当然也有特殊情况，即使用N个处理器计算，速度比单处理器处理提高N倍以上，称之为超线性加速。 算法是解题的精确描述，是一组有穷的规则，它规定了解决某一特定类型问题的一系列运算。并行计算时可同时求解的诸进程的集合，这些进程相互作用和协调动作，并最终获得问题的求解。 传统地，串行计算是指在单个计算机（具有单个中央处理单元）上执行软件写操作。CPU 逐个使用一系列指令解决问题，但其中只有一种指令可提供随时并及时的使用。并行计算是在串行计算的基础上演变而来，它努力仿真自然世界中的事务状态：一个序列中众多同时发生的、复杂且相关的事件。 并行计算的特点 为利用并行计算，通常计算问题表现为以下特征： 　　（1）将工作分离成离散部分，有助于同时解决； 　　（2）随时并及时地执行多个程序指令； 　　（3）多计算资源下解决问题的耗时要少于单个计算资源下的耗时。 并行计算是相对于串行计算来说的，所谓并行计算分为时间上的并行和空间上的并行。 时间上的并行就是指流水线技术，而空间上的并行则是指用多个处理器并发的执行计算。 一般来说，计算量极大而使PC不能满足要求或者根本不能计算的任务是适合在超级计算环境中运行的。比如， （1）需要分布式并行处理的科学计算任务，包括：由于对计算资源要求过大而使现在的硬件条件无法满足要求的计算任务，通过将串行源代码改编为并行源代码来进行计算，或者有通行的并行计算程序（商业或非商业）； （2）虽然可以计算但是时间过长的问题等 并行算法的实现 并行算法——行列划分算法 通过分析矩阵相乘的过程，可以发现矩阵A的第i 行与矩阵B的第j列对应元素乘积的累加和即为矩阵C的第i行第j列元素，而这个过程与i值的顺序是无关的。[6]。假定有P台处理器，其并行算法如下： 设A，B都是n×n矩阵，采用行列划分的方法将A，B分块，，。如下形式。 由上式，C的值转化为P2个低级矩阵的乘积，每个乘积是独立的，可以并行计算。简单起见，不妨设n可被P整除，即A，B可均匀地分为P块，上述矩阵乘积可以用下面的并行算法[7]。 数据存储。将Ai，Bi分别存入处理机i（i=1，2，…，p）的矩阵Ai，Bi中，其中Ai为n/p×n矩阵，Bi 为n×n/p矩阵，并令k=1； 信息轮换传送。处理机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； 数据的并行计算。每台处理机并行计算Ai×Bi，并根据Ai，Bi中元素在A，B中的位置，将结果存入其工作矩阵Ci中相应单元，Ci是一个n/p×n矩阵； 信息接收。每台处理机接收上一台处理机送来的信息，并存入其Bi中，覆盖Bi中原来的信息。即：若i-11，则j=p；否则j=i-1 ，处理机i接收处理机j传送来的信息； 如果np，则令n=n+1，再goto(2)，并行计算Ai×Bi，如果n=p，则各处理机并行计算Ai×Bi，运行结束。 第k次并行 计算结果 处理器i 1 2 ．．． P K=1 A1B1 A2B2 ．．． APBP K=2 A1BP A2B1 ．．． APBP-1 ．．． ．．． ．．． ．．． ．．． K=p A1B2 A2B3 ．．． APB1 矩阵相乘并行计算过程 算法有P个进程，每个进程计算C矩阵的n/p行。计算一行所需的时间为O(n2)，所以每个进程的计算复杂度为O(n2*(n/p))=O(n3/p)；又由于各进程刚好同步一次，所以同步的开销