《计算机系统结构》大作业介绍并行算法与并行程序设计及它们的不足及发展趋势专业计算机科学与技术（软件工程方向）指导教师蔡启先班级学号姓名日期 2013年6月广西科技大学计算机学院介绍并行算法与并行程序设计及它们的不足及发展趋势摘要：并行算法是并行计算中非常重要的问题。

这篇报告首先简要介绍并行计算，然后主要讨论并行算法研究中的问题和今后的方向，最后阐述并行计算研究中存在的问题以及今后面临的挑战。

并行算法研究应该确立一个“理论－设计－实现－应用”的系统方法，形成一个完善的“架构—算法—编程”方法论，这样才能保证并行算法不断发展并变得更加实用。

再结合例子进而介绍并行算法的基本原理，给并行算法下一个基本的定义，对并行算法进行了相关的介绍；接着根据目前并行算法的应用，提出了在计算机系统结构中以并行算法为基础的一些并行程序设计的应用，比较了目前流行的并行程序设计的方法，并通过比较指出它的不足以及并行程序设计在未来的发展趋势和前景。

关键词：计算机系统结构并行算法并行程序设计引言并行计算机从70年代的开始，到80年代蓬勃发展和百家争鸣，再到90年代体系结构框架趋于统一，近年来其快速发展，并行机技术日趋成熟。

首先是市场的需求，一直是推动并行计算机发展的主要动力，大量实际应用部门，如天气预报、核武器、石油勘探、地震数据处理、飞行器数值模拟以及其他大型事务处理等，都需要每秒执行数十万亿次乃至数百万亿此浮点运算的计算机，基于这些应用问题本身的限制，并行计算是满足它们的唯一可行途径。

使用多计算机进行并行程序设计，它们之间的通信是通过发送消息来完成的，所以消息传递需要并行程序设计。

并行程序设计使用多计算机或多个内部处理器的计算机来求解问题，它比使用单台计算机的计算速度要快得多。

并行程序设计也为求解更大规模的问题提供了机会，前面所述问题需要更多的计算步或更大存储容量需求，并行程序设计以并行算法为核心，能满足这要求，因为多计算机和多处理机系统通常比单计算机有更大的总存储容量。

并行算法是一门还没有发展成熟的学科，虽然人们已经总结出了相当多的经验，但是远远不及串行算法那样丰富。

并行算法设计中最常用的的方法是PCAM方法，即划分，通信，组合，映射。

首先划分，就是将一个问题平均划分成若干份，并让各个处理器去同时执行；通信阶段，就是要分析执行过程中所要交换的数据和任务的协调情况，而组合则是要求将较小的问题组合到一起以提高性能和减少任务开销，映射则是要将任务分配到每一个处理器上。

总之，并行算法还需要相当多完善的地方。

并行算法与串行算法最大的不同之处在于，并行算法不仅要考虑问题本身，而且还要考虑所使用的并行模型，网络连接等等。

并行算法是并行计算中非常重要的问题。

并法研究应该确立一个“理论－设计－实现－应用”的系统方法，形成一个完善的“架构—算法—编程”方法论，这样才能保证并行算法不断发展并变得更加实用。

简单的说，算法就是求解问题的方法和步骤。

并行算法，就是在并行机上用很多个处理器联合求解问题的方法和步骤。

实际上，在自然界中并行是客观存在的普遍现象，关键问题在于能不能很好的利用。

由于人们的思维能力以及思考问题的方法对并行不太习惯，且并行算法理论不成熟，所以总是出现了需求再来研究算法，不具有导向性，同时实现并行算法的并行程序性能较差，往往满足不了人们的需求。

并行算法的研究历史可简单归纳为：上世纪70到80年代，并行算法研究处于高潮；到上世纪90年代跌入低谷；目前，又处于研究的热点阶段。

现在，人们已经可以自己搭建PC cluster，利用学习到的理论知识来解决实际问题，不再是纸上谈兵，这也为我们提供了新的机遇和挑战。

并行计算模型并行算法作为一门学科，首先研究的是并行计算模型。

并行计算模型是算法设计者与体系结构研究者之间的一个桥梁，是并行算法设计和分析的基础。

它屏蔽了并行机之间的差异，从并行机中抽取若干个能反映计算特性的可计算或可测量的参数，并按照模型所定义的计算行为构造成本函数，以此进行算法的复杂度分析。

并行计算模型的第一代是共享存储模型，如SIMD-SM和MIMD-SM的一些计算模型，模型参数主要是UPU的单位计算时间，这样科学家可以忽略一些细节，集中精力设计算法。

第二代是分布存储模型。

在这个阶段，人们逐渐意识到对并行计算机性能带来影响的不仅仅是CPU，还有通信。

因此如何把不同的通信性能抽象成模型参数，是这个阶段的研究重点。

第三代是分布共享存储模型，也是我们目前研究所处的阶段。

随着网络技术的发展，通信延迟固然还有影响，但对并行带来的影响不再像当年那样重要，注重计算系统的多层次存储特性的影响。

设计技术并行算法研究的第二部分是并行算法的设计技术。

虽然并行算法研究还不是太成熟，但并行算法的设计依然是有章可循的，例如划分法、分治法、平衡树法、倍增法/指针跳跃法、流水线法破对称法等都是常用的设计并行算法的方法。

另外人们还可以根据问题的特性来选择适合的设计方法。

并行算法分为多机并行和多线程并行。

多机并行，如MPI技术；多线程并行，如OpenMP技术。

并行计算的特点：a将工作分离成离散部分，有助于同时解决；b随时并及时地执行多个程序指令；c多计算资源下解决问题的耗时要少于单个计算资源下的耗时。

并行计算是相对于串行计算来说的，所谓并行计算分为时间上的并行和空间上的并行。

时间上的并行就是指流水线技术，而空间上的并行则是指用多个处理器并发的执行计算。

并行计算机的分类：Flynn分类法(行为特征)并行程序设计比顺序程序设计要困难得多，一是因为并行程序设计的平台不是唯一的，存在多种不同的并行体系结构，而顺序程序设计只有唯一的冯·诺依曼体系结构；二是因为并行程序有多个进程或线程在同时运行，它们之间往往需要进行通信和同步，这就使并行程序设计变得复杂，特别是在要获得线性加速比时尤为如此；三是因为并行程序设计没有顺序程序设计中如C及Java那样通用和普及的并行程序设计语言，因此只能针对不同的体系结构选择使用不同的并行语言或例程库，例如对于共享地址空间的体系结构就必须选择如OpenMP、Java Threads或POSIX Threads那样的语言，而对于分布地址空间的体系结构就不得不选择如MPI或PVM那样的例程库语言。

目前流行的并行程序设计方法：隐式并行程序设计：常用传统的语言编程成顺序源编码，把“并行”交给编译器实现自动并行程序的自动并行化是一个理想目标，存在难以克服的困难语言容易，编译器难；显式并行程序设计：在用户程序中出现“并行”的调度语句显式的并行程序开发则是解决并行程序开发困难的切实可行的，语言难，编译器容易。

接下来具体介绍一下目前流行的MPI并行程序设计方法：传统的串行计算，分为“指令”和“数据”两个部分，并在程序执行时“独立地申请和占有”内存空间，且所有计算均局限于该内存空间。

并行计算将进程相对独立的分配于不同的节点上，由各自独立的操作系统调度，享有独立的CPU和内存资源(内存可以共享)；通过网络联接的不同计算机的多个进程，进程位于不同的计算机，消息传递是实现进程间通信的唯一方式；消息传递的实现是基于网络socket机制，用户不必关心；进程间可以相互交换信息如数据交换、同步等待，消息是这些交换信息的基本单位。

消息传递操作有发送消息(send)、接受消息(receive)、进程同步(barrier)、规约(reduction)；根据应用程序对消息传递功能的需求，全球工业、应用和研究部门联合推出标准的消息传递界面函数，不考虑其具体实现，以保证并行应用程序的可移植性在当前所有的消息传递软件中，最重要最流行的是MPI，MPI 表示消息传递接1：1(Message Passing Interface)，它能运行在所有的并行平台上，包括SMP和PVP。

二者已经在Windows NT和Windows 9X这样的非Unix平台上实现，程序设计语言支持C，Fortran和Java。

在国产的三大并行机系列神威、银河和曙光上都实现了对MPI和支持。

MPI标准化涉及到大约60个国家的人们，他们主要来自于美国和欧洲的40个组织，这包括并行计算机的多数主要生产商，还有来自大学、政府实验室和工厂的研究者们。

MPI的目的是为编写消息传递程序而开发的广范使用的标准。

象这个接口一样，为消息传递建立一个实际的、可移植的、有效的和灵活的标准。

目标如下：①设计一个应用编程接口(不必为编译器或一个系统实现库)。

②允许有效的通信：避免存储器到存储器的拷贝，而允许计算和通信的重叠，尽可能给通信协同处理器卸载。

③对于接口允许方便的C语言和Fortran 77联接。

④设定一个可靠的通信接口：用户不必处理通信失败。

这些失败由基本的通信子系统处理。

⑤定义一个接口，并非不同于现在的实践，如：PVM．NX，Express，p4等，还提供更大灵活性的扩展。

⑥定义一个接IZl，它能在基本的通信和系统软件无重大改变时，在许多生产商的平台上实现。

接IZl的语义是独立于语言的。

⑦接口应设计成允许线索一安全(thread—safety)。

目前并行程序设计的不足:a并行软件的发展落后于并行硬件；b 和串行系统的应用软件相比，现今的并行系统应用软件甚少且不成熟；b并行软件的缺乏是发展并行计算的主要障碍；d而且这种状态仍在继续。

其原因是:a并行程序设计不但包含了串行程序设计，而且还包含了更多的富有挑战性的问题；b串行程序设计仅有一个普遍被接受的冯*诺依曼模型，而并行计算模型虽有好多，但没有一个被共同认可；c并行程序设计对环境工具的要求远比串行程序设计先进得多；d串行程序设计比较适合于自然习惯，且人们在过去积累了大量的编程知识和宝贵的软件财富。

至今并行算法范例不能被很好地理解和广泛地接受；并行程序设计是建立在不同的计算模型上的，而它们没有能像冯.诺依曼模型那样被普遍接受和认可。

发展趋势及应用前景：一直以来并行计算的应用均展现了其高端性, 多用于大型的科学计算领域. 随着互联网的飞速发展和多核技术的出现, 并行计算开始向低端的个人高性能机领域发展, 即所谓的桌面应用.它使得普通用户也可能要面对并发和并行操作, 这些通常是并行计算专业人员和高端用户才需要面对的问题. 以下就相关的并行计算应用加以简述. 首先, 计算密集型的应用依然是并行计算的主要方面. 并行计算在科研方面的主要应用包括以下几个领域: 计算生物学、计算化学、计算流体动力学、飞行动力学、计算机辅助设计、数据库管理、油藏建模、中长期天气预报、海洋环流和求解N-body问题等以及面向应用的大型科学与工程问题的并行数值计算, 诸如求解大型稀疏方程组、大型非线性方程和有限元分析等. 在交叉学科中出现了一些非传统计算方式, 例如分子计算和量子计算等. 这些计算本身包含着巨大的并行度, 超出了传统的计算模式, 但目前都还处于研究探索阶段. 相信在可预期的未来, 高性能计算依然是处理大规模科学计算的重要工具：1) 随着并行计算的最新发展, 新型的以数据密集为特征的并行应用也日益成为主流。