并行计算综述姓名：尹航学号：S131020012 专业：计算机科学与技术摘要：本文对并行计算的基本概念和基本理论进行了分析和研究。

主要内容有：并行计算提出的背景，目前国内外的研究现状，并行计算概念和并行计算机类型，并行计算的性能评价，并行计算模型，并行编程环境与并行编程语言。

关键词：并行计算；性能评价；并行计算模型；并行编程1. 前言网络并行计算是近几年国际上并行计算新出现的一个重要研究方向，也是热门课题。

网络并行计算就是利用互联网上的计算机资源实现其它问题的计算，这种并行计算环境的显著优点是投资少、见效快、灵活性强等。

由于科学计算的要求，越来越多的用户希望能具有并行计算的环境，但除了少数计算机大户（石油、天气预报等）外，很多用户由于工业资金的不足而不能使用并行计算机。

一旦实现并行计算，就可以通过网络实现超级计算。

这样，就不必要购买昂贵的并行计算机。

目前，国内一般的应用单位都具有局域网或广域网的结点，基本上具备网络计算的硬件环境。

其次，网络并行计算的系统软件PVM是当前国际上公认的一种消息传递标准软件系统。

有了该软件系统，可以在不具备并行机的情况下进行并行计算。

该软件是美国国家基金资助的开放软件，没有版权问题。

可以从国际互联网上获得其源代码及其相应的辅助工具程序。

这无疑给人们对计算大问题带来了良好的机遇。

这种计算环境特别适合我国国情。

近几年国内一些高校和科研院所投入了一些力量来进行并行计算软件的应用理论和方法的研究，并取得了可喜的成绩。

到目前为止，网络并行计算已经在勘探地球物理、机械制造、计算数学、石油资源、数字模拟等许多应用领域开展研究。

这将在计算机的应用的各应用领域科学开创一个崭新的环境。

2. 并行计算简介[1]2.1并行计算与科学计算并行计算（Parallel Computing），简单地讲，就是在并行计算机上所作的计算，它和常说的高性能计算（High Performance Computing）、超级计算（Super Computing）是同义词，因为任何高性能计算和超级计算都离不开并行技术。

2.1.1科学与工程计算的需求在应用需求方面，人类对计算机性能的需求总是永无止境的，在诸如预测模型的构造和模拟、工程设计和自动化、能源勘探、医学、军事以及基础理论研究等领域中都对计算提出了极高的具有挑战性的要求。

例如，在作数值气象预报时，要提高全球气象预报的准确性，据估计在经度、纬度和大气层方向上至少要取200*100*20＝40万各网格点。

并行计算机产生和发展的目的就是为了满足日益增长的大规模科学和工程计算、事务处理和商业计算的需求。

问题求解最大规模是并行计算机的最重要的指标之一，也是一个国家高新技术发展的重要标志。

一般地，问题规模分解为输入输出规模、计算规模、内存需求、通信（同步）规模，分别表示问题求解所需的I/O量、计算量、内存大小和通信量（包括通信次数和通信数据量）。

根据在求解中所消耗资源的程度，问题由相应分为CPU密集型应用、Memory密集型应用、Disk密集型应用和网络密集型应用。

针对不同类型的问题，性能瓶颈也往往不同，并行算法就是有针对性地消除相应的瓶颈，从而达到缩短计算时间的目的。

对并行计算的需求是广泛的，但归纳起来主要有三种类型的应用需求：计算密集（Compute-Intensive）型应用，如大型科学工程计算与数值模拟；数据密集(Data-Intensive)型应用,如数值图书馆、数据仓库、数据开采和计算可视化等；网络密集（Network-Intensive）型应用，如协同工作、遥控和远程医疗诊断等。

2.2目前国内外的研究现状随着科学技术的进步和并行计算机的计算速度和容量的迅速增长，以前无法实现的大型计算问题得到了很快的解决。

许多科技工作者在解释自己研究的科技领域中出现的物理现象时提出了一些现代复杂数学和计算技术问题，而这些理论和方法都要解决大问题的计算，最后归结到求解大型方程组等。

不少应用软件，在求解方程组方面耗费的实际时间占80％以上，因而研究高效并行算法及其计算环境在国内外引起了许多科学家的注意。

预测模型的构造和模拟、工程设计和自动化、能源勘探、医学、军事、机械制造、计算数学、石油资源数学模拟问题，常常涉及到现代的复杂数学问题和计算方法，又具有很强的实用性。

这些领域的许多现象的描述都是各种数学物理方程，从数学物理方程的求解方法导出大型稀疏线性方程组。

近几年又有将分形、神经网络及遗传算法应用于这些领域的计算。

由此，许多数学家、科学家在这些领域上提出了许多高效的计算方法。

这些计算方法都有一个共同的特点，那就是计算空间大。

目前将这些高效的计算方法真正应用于解决实际问题而且行之有效的则并不多见。

究其原因，主要是这类问题要求解大型线性方程组，许多用户又不具备并行计算机。

一些优秀的算法在应用领域中借助于串行计算机计算，其优越性不能充分体现出来，直接影响了这些领域的科技应用的发展。

网络并行计算时利用网络上的计算机资源实现大问题的并行计算，这使得许多优秀的算法得以体现和广泛的应用，使得这些领域中应用高效数值计算成为可能。

随着商品化微处理器、网络设备的发展，以及MPI/PVM等并行编程标准的发布，出现了机群架构的并行计算机。

IBM SP2系列机群系统就是其中的典型代表。

在这些系统中，各个结点都采用标准的商品化计算机，它们之间通过高速网络连接。

近几年来机群计算成为国内外研究的热门课题。

国际上，机群系统并行环境在进一步完善中，不少国外大学推出了自己的机群系统，商业机群也逐渐成熟起来。

在国内，中科院、国家高性能计算中心和一些大学投入了相当的力量对其应用理论和方法进行研究，如国家智能计算机研究开发中心的有关机群的在研项目，有机群系统I/O负载的收集与分析、面向机群和网格的分布式构建平台研究和机群服务器功能软件等。

机群并行系统具有构造成本低、编程方便、投资风险小、性能/价格比高、系统结构灵活、可扩展性好、能充分利用分散的计算资源等特点和优势，研究机群并行计算在科学和工程领域中的应用具有十分重要的意义。

3.并行计算概述从事网络并行计算，首先要对并行计算概念和并行计算机类型有一个初步的了解。

3.1.并行算法概述[2]3.1.1并行算法的定义和分类算法是解决问题的精确描述，是一组有穷的规则。

它规定了某一特定类型问题的一系列运算。

并行计算是可同时求解的诸进程的集合，这些进程相互作用和协调动作，并最终获得问题的求解，并行算法就是对并行计算过程的精确描述，是给定并行模型的一种具体的解决方法和步骤。

并行算法可以从不同的角度分类为：·数值计算并行算法和非数值计算并行算法；·同步并行算法、异步并行算法、纯并行算法；·粗粒度并行算法、中粒度并行算法和细粒度并行算法；根据运算的基本对象不同，并行计算分为数值并行算法和非数值数值并行算法是针对基于代数关系运算的计算问题如矩阵运算、多项式线性代数方程组求解等的并行算法；非数值并行算法是针对基于比较关算如排序、选择、查找、匹配等符号处理等的并行算法。

当然，这两种是绝对分开的，比如在数值计算的过程中会用到查找、匹配等非数值算分，而在非数值计算中也会用到数值计算的方法。

划分为何种算法取决的计算量和宏观的计算方法。

根据进程之间的依赖关系，并行算法分为同步并行算法（步调一并行算法（步调、进展互不相同）和纯并行算法（各部分之间没有关同步并行算法，任务的各个部分是同步向前推进的，有一个全局的时钟定是物理的）来控制各个部分的步伐；对于异步并行算法，各个部分的互不相同的，它们根据计算过程的不同阶段决定等待、继续或终止；纯法是理想的情况，各个部分之间可以尽可能快地向前推进，不需要任何等待，但是这样的问题一般很少见。

根据并行计算任务的大小，并行算法可以分为粗粒度并行算法（一个任务包含较长的程序段和较大的计算量）和细粒度并行算法（一个并行含较短的程序段和较小的计算量）以及介于二者之间的中粒度并行算法而言，并行的粒度越小，越有可能开发更多的并行性，提高并行度，这方面；不利方面是并行的粒度越小，通信次数和通信量就会相对增多，加了额外的开销。

因此，合适的并行粒度需要根据计算量、通信量、通信速度等因素进行综合平衡，这样才能取得高效率。

3.1.2并行算法的设计方法利用并行处理机系统求解一个给定的问题，需要根据体统类型和特相应的并行算法。

通常有三种途径：·检查和开发现有串行算法中固有的并行性直接将其并行化；·从问题本身的特征出发，设计一个新的并行算法；·修改已有的并行算法使其可求解另一类相似的问题。

对一类具有内在顺序性的串行算法难于并行化；修改已有的并行算法依赖于特定的一类问题；设计全新的并行算法，尽管技术上尚不成熟，但还是有章可循的。

目前普遍使用的并行算法的设计技术有流水线技术、分治策略、平衡树方法、倍增技术以及加速级联策略等。

3.1.3并行算法的复杂性对算法进行分析时，常要使用上界（Upper Bound）、下界（Lower Bound）和紧致界（Tightly Bound）等概念，分别定义如下：·上界：令f(n)和g(n)是定义在自然数集合N上的两个函数，如果存在正整数c和n0，使得对于所有的n>=n0，均有f(n)<=g(n)，则称g(n)是f(n)的一个上界，记做f(n)=O(g(n))。

·下界：令f(n)和g(n)是定义在自然数集合N上的两个函数，如果存在正整数c和n0，使得对于所有的n>=n0，均有f(n)>=g(n)，则称g(n)是f(n)的一个下界，记做f(n)=O(g(n))。

·紧致界：令f(n)和g(n)是定义在自然数集合N上的两个函数，如果存在正整数c1，c2和n0，使得对于所有的n>=n0，均有c1*g(n)<=f(n)<= c2 *g(n)，则称g(n)是f(n)的一个紧致界，记做f(n)=Θ(g(n))。

在算法分析时，如果对算法的所有输入分析其平均性态时的复杂度，则称之为期望复杂度（Expected Complexity），在某些输入时，可以使得算法的时间、空间复杂度最坏，此时的时间复杂度称为最坏情况下的复杂度（Worst-Case Complexity）。

3.1.4并行算法性能评价并行算法的性能主要通过下列三个因素评价：·计算时间（时间复杂度）·所需的处理器个数（处理器复杂度）·所需的机器模型主要性能指标有加速比（Speedup）和效率(Efficiency)。

加速比和效率考虑一个已知的串行算法，其时间复杂度为T s，我们有一个针对相同问题的并行算法，其时间复杂度为T p，处理器复杂度为P，定义加速比=Ts Tp效率＝Ts Tp∗P加速比最大不超过处理器的个数，我们总是试图开发加速比几乎等于处理器数目的并行算法。