并行算法研究现状及其相关问题综述     
并行程序的编程模型、运行环境、调试环境等都要比串行程序复杂得多。提供良好的高性能计算开发环境，一直是学术界和工业界所追求的目标。这里的开发环境既包括并行计算机体系结构，计算机网络拓扑结构等硬件环境；也包括并行程序的开发模式，网络通信协议和通信方式等软件环境。并行算法研究要以硬件，即并行计算机为依托，并行计算机性能的发挥要依靠优秀并行算法的设计的实现。
所以本文，并行算法研究现状及其相关问题的综述，将对与并行紧密相关的并行计算机体系结构，并行程序开发环境，通信技术三个问题依次进行讨论。闪闪红星歌曲
一、 并行计算机体系结构
“ 并行计算机是由一组处理单元组成的；这组处理单元通过相互之间的通 信与协作，以更快的速度共同完成一项大规模的计算任务。”这就是并行计算机 的经典定义。这个定义并没有包含更多的细节，但是从中我们也不难看出并行计算机的两个最主要的组成部分：计算节点和节点间的通信与协作机制。
徐小凤每一步
给你 陈奕迅并行计算机体系结构的发展变化非常快，而这种变化主要体现在计算节点 性能的提高以及节点间通信技术的改进两方面。长期以来，超大规模集成电路技 术一直在按照摩尔定律高速发展，芯片的元件密度以及时钟频率在不断提高，从 而大大提高了作为并行计算机基本处理单元的微处理器的性能。而在通信技术 方面， 传统的交叉开关的切换速度不断提高，而新的高速网络技术也不断应用 到并行计算机中，从而大大提高了节点间通信的速率。
（一）体系结构的分类
    1972年，Micheal Flynn根据指令和数据流的概念对计算机的体系结构进行了分类，这就是所谓的Flynn分类法。
Flynn将计算机划分为四种基本类型，即SISD、MIMD、SIMD、MISD。
        传统的顺序执行的计算机在同一时刻只能执行一条指令（即只有一个控制 流）、处理一个数据（即只有一个数据流），因此被称为单指令流单数据流计算 机（Single Instruction Single Data即SISD计算机）。而对于大多数并行计算机而言，多个处理单元都是根据不同的控制流程执行不同的操作，处理不同的 数据，因此，它们被称作是多指令流多数据流计算机，即MIMD（Multiple Instruction Multiple Data）计算机。
        曾经在很长一段时间内成为超级并行计算机主流的向量计算机除了标量处 理单元之外，最重要的是具有能进行向量计算的硬件单元。在执行向量操作时， 一条指令可以同时对多个数据（组成一个向量）进行运算，这就是单指令流多数 据流（Single Instruction Multiple Data，SIMD）的概念。因此，我们将向量 计算机称SIMD计算机。
        第四种类型即所谓的多指令流单数据流（Multiple Instruction Single Data）计算机。在这种计算机中，各个处理单元组成一个线性阵列，分别执行不 同的指令流，而同一个数据流则顺次通过这个阵列中的各个处理单元。这种系统 结构只适用于某些特定的算法。
        相对而言，SIMD和MISD模型更适合于专用计算。 在并行计算机中，MIMD模型最为通用，SIMD次之，而MISD最少用。
(二)体系结构的发展过程
        并行计算机40年的发展过程中出现过许多著名的机器。
        60年代初期，由于晶体管以及磁芯存储器的出现，处理单元变得越来越小， 存储器也更加小巧和廉价。这些技术发展的结果导致了并行计算机的出现，并迎 来了它的第一个
他大舅黄金时代。
这一时期的并行计算机多是规模不大的共享存储多处理器系统，不过，当时 它们可是被当作大型主机（Mainframe）来看待的。Burroughs B5000, D825以及IBM System 360是这一时期的典型代表。其中，IBM System 360在过渡到370系列时引入了多处理机的概念，而CDC 6600则在中央处理器与多个I/O处理器 之间采用了异步共享存储器的机制。与这些机器有所不同的是，RW400则是最早 采用消息传递机制的大型主机。
到了60年代末期，同一个处理器开始设置多个功能相同的功能单元，流水 线技术也出现了。与单纯提高时钟频率相比，这些并行特性在处理器内部的应用 大大提高了并行计算机系统的性能。
伊利诺依大学和Burroughs公司此时开始了一项庞大的工程，即Illiac IV 计划。他们认为，当时已有的技术已经走到尽头了，因此决定另辟蹊径。根据这 一规划，Illiac IV 应该是一台64个CPU的SIMD主机系统，它涉及到从最底层 的硬件技术、体系结构、I/O设备、操作系统、程序设计语言直至应用程序在内 的众多研究课题。不过，当一台规模大大缩小了的16 CPU系统终于在1975年露 出了它的庐山真面目的时候，整个计算机界已经发生了巨大
的变化。
首先是存储系统概念的彻底革新。虚拟存储和缓存这两个概念现在已经应 用在了几乎所有的计算机系统里，但在70年代初期，它们却带来一场真正的革 命。 IBM 360/85系统与360/91是属于同一系列的两个机型，360/91的主频高于360/85，所选用的内存速度也较快，并且采用了动态调度的指令流水线；但是，360/85的整体性能却高于360/91，唯一的原因就是前者采用了缓存技术，而后者则没有。
其次是半导体存储器开始代替磁芯存储器。最初，半导体存储器只是在某些 机器中被用作缓存，而CDC 7600则率先全面采用这种体积更小、速度更快、可以直接寻址的半导体存储器，磁芯存储器从此退出了历史舞台。与此同时，集成 电路也出现了，并迅速应用到了计算机中。元器件技术的这两大革命性突破，使 得Illiac IV的设计者们在底层硬件以及并行体系结构方面提出的种种改进都 大为逊。
Illiac IV原本是想解决数值计算中向量运算密集的问题的，不过，这个任 务却是由这一时期诞生的最早的向量流水线计算机CDC STAR 100完成的。而到 了1976年CRAY 1问世以后，一个长达15年的新时代开始了，向量计算机从此牢牢地控制着整个高性能计算机市场。
CRAY 1对所使用的逻辑电路进行了精心 的设计，采用了我们如今称为RISC的精简指令集，还引入了向量寄存器，以完成向量运算。这一系列全新技术手段的使用，使CRAY 1的主频达到了令时人不可思议的80 MHz。
微处理器的出现则使并行计算机的体系结构迈出了另一大步。最早的微处 理器性能并不是很理想，但是随着机器的字长从4位、8位、16位一直增加到32位，其性能也随之显著提高。正是因为看到了微处理器的这种潜力，卡内基梅隆大学开始在当时流行的DEC PDP 11小型计算机的基础上进行共享存储多处 理器系统的研究。C.mmp就是这一研究项目的具体成果。它是一台由16个PDP 11/40处理机通过交叉开关与16个共享存储器模块相连接而成的。
从80年代开始，微处理器技术一直在高速前进。稍后又出现了非常适合于SMP方式的总线协议，而伯克利加州大学则对总线协议进行了扩展，提出了Cache 一致性问题的处理方案。从此，C.mmp开创出的共享存储多处理器之路越走越 宽；到了10年之后的今天，这种体系结构已经基本上统治了服务器和桌面工作 站市场。 歌唱祖国大合唱
同一时期，基于消息传递机制的并行计算机也开始不断涌现。80年代中期， 加州理工成功
地将64个i8086/i087处理器通过超立方体互连结构连结起来。此 后，便先后出现了Intel iPSC系列、INMOS Transputer系列，Intel Paragon以及IBM SP的前身Vulcan等基于消息传递机制的并行计算机。
向量计算机渐渐衰落下去。数据并行方式的计算机在相对沉寂了一段时间 之后，到了80年代中期又开始逐渐复兴。这一时期数据并行方式的计算机主要 有Goodyear MPP，Thinking Machines的CM 1、CM 2以及MasPar等。在互连机 制方面，这一代机器不仅仅限制在相邻的节点之间，而是可以根据需要在任意节 点之间进行通信。CM 2则更是具备了大量的浮点单位并行（Bit parallel）运算单元。
80年代末到90年代初，共享存储器方式的大规模并行计算机又获得了新的 发展。IBM公司在RP 3计划中希望能将大量早期RISC微处理器通过蝶形互连网 络连结起来。而BBN公司则先后推出了两个型号的这类机器，即采用Motorola 68000芯片的BBN Butterfly以及采用88100芯片的TC2000。通过这些尝试，人 们开始考虑如何才能在实现共享存储器缓存一致的同时，使系统具有一定的可 扩展性（Scalability）。90年代初期，斯坦福大学提出了DASH计划，它通过维护一个保存有每一缓存块位置信息的目录结构来实现分布式共享存
储器的缓存一致性。后来，IEEE在此基础上提出了缓存一致性协议的标准。MIT的Alewife 计划则试图简化为保持缓存一致性而带来的硬件开销。
90年代以来，主要的几种体系结构开始走向融合，这种趋势有其内在的必 然性。为了获得更好的性能，在Alewife以及FLASH等共享存储类型的项目中也 引入了消息传递机制；而属于数据并行类型的CM 5除大量采用商品化的微处理 器以外，也允许用户层的程序传递一些简单的消息；CRAY T3D是一台NUMA结构 的共享存储型并行计算机，但是它也提供了全局同步机制、消息队列机制，并采 取了一些减少消息传递延迟的技术；Meiko CS 2采用的是消息传递机制，但是， 一个节点上用户程序虚地址空间内的数据却可以直接复制到另一个节点上另一 个程序的虚地址空间里去，实际上这正是共享地址空间机制的特点。
乌溜溜的黑眼珠和你的笑脸不过IBM近年来大获成功的SP 1、 SP 2系列机系统走的则是另外一条路 线。在这些系统中，各个节点采用的都是标准的商品化Unix工作站（RS 6000）， 它们之间通过高速网络连接起来。各节点内存系统之间没有多少联系，网络连接 的可靠性也不高，面向的是通用的应用领域。因此，从总体上说，SP 1、SP 2基本上属于消息传递型系统。
目前的并行计算机系统主要有四类:第一类是多向量处理系统, 如Cray YMP 90、NEC SX 3
和Fujitsu VP 2000 等；第二类是基于共享存储的多处理机（SMP） 系统,如SGI Power Challenge、曙光1号等；第三类是基于分布存储的大模并行处理(MPP)系统,如Intel Paragon、IBM SP2、曙光1000等；第四类是基于RISC 工作站或高档微机通过高速互连网络连接而构成的机计算机系统，如清华同 方探索集计算机等。
展望
实现上述第一和第三类系统由于受研制费用高、售价高等因素的影响,其市 场受到一定的限制。第二类系统由于共享结构的限制,系统的规模不可能很大。 由于机系统计算机具有投资风险小、可扩展性好、可继承现有软硬件资源和开 发周期短、可编程性好等特点，目前已成为并行处理的热点和主流。据专家预测：“未来的高性能计算机和超级服务器都将基于机系统结构”。