并行处理技术

1、并行处理技术摘要：并行处理计算机是计算机设计的未来。当代面临着的重大科学技术问题要依赖于计算技术协助解决，一方面要作 大型计算以得到更精确的解，另一方面要作计算机模拟，以便进一步了解所探讨 问题的结构与运动规律。这两个方面都离不开并行处理技术。虽然许多人都认识 到并行处理技术的重要性，但并行处理技术的发展道路并不平坦。从70年代到 90年代中期，中间几起几落，究其原因，就是并行计算技术仍然遇到若干困难， 使其无法推广应用。这其中既有软件方面的（并行程序设计）问题，也有硬件方 面（并行处理机）的原因。本文主要从并行程序设计和并行处理机两方面对并行 处理技术进行了简要的介绍。关键词：并行处理技术、

2、并行处理机、并行程序引言人类对计算能力的需求是永无止境的，而在各种类型的计算系统中，超级计 算机的性能最高。90年代以来，超级计算机在工业、商业和设计等民用领域的 重要性越来越明显了。因此，超级计算机的发展，不仅会深刻地改变产品和材料 的设计方法，改变研究和实验的方式，而且将逐步影响人们的生活方式。超级计 算机已经成为体现一个国家经济和国防力量的重要标志。20多年来，超级计算机的工作频率只提高了将近10倍，而峰值速度却提高了 1 万倍。这说明，主要的性能改善来自结构的进步，尤其是来自各种形式的并行处 理技术。但是，超级计算机的用户们关心的并不是系统在理论上的最高速度，而 是实际解题所需要的时间

3、和程序设计及移植的工作量。并行处理是提高计算机系统性能的重要途径。目前几乎所有的高性能计算机 系统，都或多或少地采用了并行处理技术。本文将就并行处理技术做简要的介绍。何为并行并行性主要是指同时性或并发性，并行处理是指对一种相对于串行处理的处 理方式，它着重开发计算过程中存在的并发事件。并行性通常划分为作业级、任务级、例行程序或子程序级、循环和迭代级以 及语句和指令级。作业级的层次高，并行处理粒度粗。粗粒度开并行性开发主要 采用MIMD方式，而细粒度并行性开发则主要采用SIMD方式。开发计算机并行性的方法主要有：资源重复、时间重叠和资源共享三种方法。并行程序设计在并行处理技术中，并行程序是最为核

4、心的领域之一。没有好的并行程序的 支持，并行处理机就不可能很好的工作，所谓超级计算也就更加无从谈起了。并行程序设计方法不同于顺序程序设计方法，主要在于对问题采取何种看 法：顺序程序设计方法把事物的变化发展看成是单线程的，任何两种事物之间必 然存在因果关系，从而把一系列统一事物看成是不可分割的整体。后来的结构程 序设计特别是对象式程序设计把一个复杂的事物分解成多个简单的事物，或者把 一个系统看成是由多个相互联系的实体构成的。应该说，这里在对事物的认识上 取得了突破性的进展，但也是从事物的静态结构上来看的，并未从行为上来分解。 从行为上来看，它们仍然被认为或者是一致的，或者是先后相继的，相互之间不

5、 存在有并发干扰现象，更不存在可同时发生的相互作用的行为。并行程序设计方法的一个最基本的观点，就是把一个事物的行为看成是多个 事物互相作用的结果。这是一个观念上的根本转变，根据这个观点，并行程序设 计方法的核心内容就是并行划分与算法映射。其理论基础是并行计算模型。并行 计算模型决定了并行语义，并行语义决定了可并行执行的准则，从而决定了并行 划分的原则。要研究并行程序设计，首先就要讨论并行算法的结构，这涉及到对并行算法 的理解、并行程序设计方法、并行算法与并行系统结构匹配等问题。所谓并行算法结构，就是构成并行算法的基本组成部分与属性及其互相之间 的关系。一般来讲，一个并行算法结构由以下几部分组成

6、：（1）划分模式，即并行划分类型与并行模块;（2）合作模式，即合作方式与计算图；（3）映射（分配）格局；通信模式；运行模式。一个并行算法的结构既是该算法的骨架，也是该算法的精髓，这些方面确定 了，这个算法也就基本上确定了。理解或者说一个算法，都可以从这几个方面来 考虑。算法结构应当与机器结构相匹配，这是提高应用程序实际执行性能的一条重 要途径。因此，从算法结构应与机器系统结构相匹配的观点出发，对算法结构作 一个分类，具有重要的实际意义。根据算法结构的组成部分，我们按以下优先级 进行分类：运行模式一通信模式一并行划分类型与合作模式。分类情况如下：同步操作公共变量型消息传递型向量型水平数据划分+分

7、工式水线型垂直划分+接力式脉动型水平垂直划分+接力式异步操作公共变量型消息传递型数据流型垂直水平划分+合力式对话型垂直水平划分+对话式过程型(归约型，对象型)垂直水平划分+请求式会议型垂直水平划分+会议式SPMD型水平划分+分工式MPMD型混合划分+合力式以上这些算法结构类型，大多数都有一种特定的系统与之对应。算法结构的 分类，对于设计一个满足与系统结构相匹配的算法也是很有意义的。并行处理机好的并行程序也要在好的并行处理机上运行，才能发挥出最大的能量。并行 机按系统结构划分可分为以下五类：向量流水巨型机、SIMD阵列机、共享主存 多处理机、分布存储多计算机和联网计算机。本章将着重介绍SIMD阵

8、列机何多处理机的相关知识。（一）SIMD并行计算机（阵列处理机）阵列机也称并行处理机。它将大量重复设置的处理单元按一定方式互连成阵 列，在单一控制部件CU（Contrul Unit）控制下对各自所分配的不同数据并行执 行同一指令规定的操作，是操作并行的SIMD计算机。它采用资源重复的措施开 发并行性。是以SIMD（单指令流多数据流）方式工作的。1、阵列机的基本结构阵列机通常由一个控制器CU、N个处理器单元PE（Processing Element）、M 个存储模块以及一个互连网络部件（IN）组成。根据其中存储器模块的分布方式， 阵列机可分为两种基本结构：分布式存储器的阵列机和共享存储器的阵列机

9、。 阵列机的主要特点：它采用资源重复的方法引入空间因素，这与利用时间重叠的流水线处理机是 不一样的。它是利用并行性中的同时性而不是并发性，所有的处理单元必须同时 进行相同操作（资源重复同时性）（我们想象一下亚运会的开幕式大型团体操表 演，每个人就是一个PE，他们听从一个总指挥的指令，同时进行自己的操作， 很快地就能“计算”出一个结果（队形）来。它是以某类算法为背景的专用计算机，基本上是专用于向量处理的计算机 （某类算法专用机）。阵列机的研究必须与并行算法研究密切结合，以使它的求解算法适应性更强 一些，应用面更广一些（并行算法合研究）。陈列机实质上是由专门对付数据组运算的处理单元阵列组成的处理机

10、（M个 PE）、专门从事处理单元阵列的控制及标量处理机（控制器CU）和专门从事系统输 入输出操作及操作系统管理的处理机三部分构成的一个异构型多处理机系统（三 个部分成异构）。3、阵列机的并行算法阵列机的算法是与结构紧密联系在一起的，阵列机上常用的算法有矩阵计 算、图形处理等，我们对教材中举的两种算法要领会，特别是累加和递归操作， 不难理解。它就是使各个处理器同时进行加的操作，但并不是全部处理器都参加 运算，在处理时，根据累加计算的需要，由控制器CU借助屏蔽的方式将一部分 PE设置成不活动的状态。这种累加操作的速度提高倍数是N/log2N倍。（二）多处理机多处理机具有两台以上的处理机，在操作系统

11、控制下通过共享的主存或输入 输出子系统或高速通讯网络进行通讯。多处理机属MIMD系统。多处理机与SIMD相比有较大不同，表现在：结构灵活性：MIMD机结构上具有更大灵活性和更强的通用性；程序并行性：前者是作业级并行，后者则是操作级并行；并行任务派生：前者需要由专用语句显式指明是否派生并行任务，而后者 则不需要专门指令；进程同步：MIMD机中各进程的同步需要采取特殊措施来保证，而SIMD机 则由于受同一控制器控制，自然是同步的；资源分配和调度：MIMD机任务调度要采用软件手段，而SIMD机中，只需 用屏蔽来控制实际参加并行操作的处理单元数目。；多处理机在系统结构上分为两类：紧耦合和松耦合系统。紧

12、耦合是通过共享 主存实现处理机间的互相通信，处理机间的相互联系比较紧密。按所用处理机类 型是否相同及对称，又可分为同构或异构及对称或非对称的形式。常见组合是同 构对称式和异构非对称式多机系统。松耦合是通过消息传递方式来实现处理机间 的相互通信，而每个处理机是由一个独立性较强的计算机模块组成。为了解决多系统中的cache 一致性问题，可采用的方法有（1）件方法（2）采用总线监听机制（3）目录表法多处理机系统中，机间互连主要采用以下几种方式。（1）总线方式（2）纵横交叉开关互连方式（3）多端口存储器互连方式（4）多级网络互连方式（5）虫孔互连和寻径技术多处理机中并行性的开发第一步是要对程序中存在的

13、并行性进行分析，主要 分析其中的数据相关、数据反相关及数据输入相关，其次是用伯恩斯坦准则来分 析哪些部分是可以并行执行的。并行的程序设计语言常用FORK-JOIN原语及块结构语言Cobegin-Coend语言 来表示程序中可并行执行部分及相互之间的同步关系。多处理机操作系统除了完成通常单机操作系统的资源分配和管理、存储管理 和保护、死锁防止、异常里程终止或例外处理等功能外，还必须具有以下特点和 功能：（1）支持多个任务的并行执行（2）支持处理机同步和通信管理（3）提供系统结构重构运动系统降级使用（4）自动支持硬件并行性和程序并行性的开发多处理机操作系统主要分成三类结构：主从结构、独立监控结构和浮动监控 结构。其中主从结构适用于系统负载固定以及主机功能较强、从机功能较弱的非 对称多处理机系统；独立监控结构适用于松耦合多处理机系统；第三种结构则适 用于对称紧耦全多处理机系统。衡量多处理机