一、前言
并行处理是早就存在的问题。十九世纪研究机械式计算机时遇过，电子计算机出现不久，五十年代初期就采用了由位处理来进行字处理这样形式的并行处理。不过，现在谈到并行处理，通常是指使用若干个运算器同时进行好几个运算，或者使用若干个处理器执行好几个任务这样比较高层次的并行处理。这些从广义并行处理的观点来看，都是一样的东西。为了实现处理高速化，研究并采用了对应于各个时代元件技术及高速化要求的各种并行处理技术。在科学技术计算中对高速化的要求是无止境的，希望出现高性能计算机开拓新的应用领域的种种要求，越来越多。高速化的手段有元件高速化和并行处理两种，当超出元件的能力时，只能寄希望于并行处理。特别是随着VLSI（超大规模集成电路）的发展，将许多一样的电路放在一起很容易，所以现在能够开始谈论实现106数量级的并行性的问题。
此外，以第五代计算机为代表，处理模式本身变革的动向，也不断地给并行处理以新的推动。知识信息处理对计算机结构的要求之一，当然就是高速性，进一步发展下去，就是希望使并行处理作为基本的形态，而串行处理只作为特殊的形态。就是说，并行程序设计的目的之一，就是尽可能地去除现在语言中所见到的“不必要串行性”，从结构上来支持这一目的的计算机，就称为并行处理机。
迄今为止，并行处理往往是不成功的，可以说积累了许多失败的经验。但是，在这个基础上正对并行处理寄以厚望，研究正日益活跃。现在的研究和以前有所不同。首先以超大规模集成电路为代表的元件技术、安装技术有明显发展，便研究的环境有所变化。其次，建立了分析应用问题的动作的算法，制成了适合这种算法的专用机，使定向应用研究得到落实。这样，数据驱动、减法、主体等新的计算模式也走向成熟。
二、并行处理的历史
下面对1980年以前并行处理的发展过程作一概述。
1. 多处理器方式
多处理器方式系共用主存的系统，60年代初UNIVACLARC机就采用这种方式。它主要用以提高计算机系统的吞吐量和可靠性，现在通用大型计算机几乎都采用这种方式。处理器的个数通常4个、至多16个左右，在高速机中，维持高速绫冲存储器无矛盾性的电路常成为瓶颈。
2. SIMD（单指令多数据）型机
这是一种使用多个运算器及处理器对不同数据进行同样运算的计算机。将空间细分成许多小格，使用其邻近的数据进行运算，对偏微分方程求解就是其典型例子。20年代Richardson提出用许多人进行手工的气象计算，60年代的SOLOMON计算机的设计，以及它的改良型ILLIAC Ⅳ等计算机，都是沿着这一方向发展卞来的。它的特点是进行大规模处理时易于控制。适于使用这种方式算类型，有扩散方程式、热方程式、图像处理、空气动力学等，在这些方面它发挥了巨大的威力，但是也有许多不适合使用它的计算。如最近具有16000个处理要素的MPP达到实用，比起用这种方式Cray-1的巨型计算机，图像处理时的分辨能力为其三倍。
3. MIMD（多指令多数据）型机
这种系统由进行各自不同处理的多个处理器组成，是多处理器方式中的一种。它不是用多个处理器并行进行木同的作业以提高吞吐量，而是将一个作业进行分割，分给多个处理器进行处理以达到高速处理的目的。因此，采用了各种各样的处理器间通信机构、共用存储器以及进行明示的数据存取机构，处理器的数量一般也很多，最近出现了多达1000个的规模。70年代中期的C.mmp和Cm*，以及许多由为数众多的微处理器结合在一起的所谓多微处理器便相当于MD型机。由于它比SIMD型机更适于作柔性处理，故适用范围宽，但如用它作SIMD处理时效率反而降低。这种计算机结构上的特点是基元处理器的结合是个拓扑学问题，可以是只有相邻基元才可连接，也可以任意基元都可以连接。适于使用MIMD机的问题，有粒子的蒙特卡罗仿真。
4. 联想处理器
它的存储元件分别具有逻辑功能，属于所谓Logic-in-Memory（内含逻辑的存储器）系统。从60年代初便作为分散逻辑存储（DLM）及联想存储处理器而得到研究。在STARAN. OMEN、PEPE机上得到实用。其特点为可进行位处理和存储内容探索。最近由于VLSI技术的发展，非常大容量的联想存储器又引人注意，需要再次研究驱动它的结构。
5. 流水线方式
它将某一处理分成许多小的处理阶段，分别由安排在流水线上相应的硬件完成。每一小处理阶段完成后，该硬件空闲便可开始受理新的处理。只要连续地输入指令，用完成一小阶段处理的时间就可完成一个处理。这时等效的处理时间为各小阶段处理时间之和。这种方法称为流水线方式，是非常好用的高速化方法，60年代初IBM在STRETCH的提前控制方式中就用了它，通过IBM 360/91运算回路内部的流水线化而广为普及。70年代初在ASC、CDC STAR-100等机上确立了它的地位，以后Cray-1巨型机取得成功，说明高逨计算机也适于使用高级的流水式方式。现在通用大型机全都采用由几段以至十几段组成的流水线方式，像Cray-2及SX—2这样巨型机，流水线中每段所花的时间只有几纳秒。
6. 数据流机
通常的计算机是依次执行明确给予的指令（称为控制驱动），而数据流机则根据来到的操作数从可能执行的指令中选择执行之（称为数据驱动）。因为它对运算尽可能并行地执行，所以是并行处理的基本模式，具有对问题内在的并行性尽可能提取出来的能力。数据流的想法源于70年代初的并行程序研究，经由单一代入的提议，1974年J. Dennis将其总结成数据流计划。以后，MIT、曼彻斯特大学、UC欧文、图卢兹大学、德州仪器公司等都进行的数据流机的研制和语言研究。在日本，武藏野通研、东大、阪大、电总研、冲电气、IC OT、群马大学等也进行了研究。目前，日本正逐渐成为对数据流机研究最积极的国家。
三、并行处理技术
1. 并行处理的各个层次
并行处理要求在某种应用于计算机上运行时，根据最初目的经过某些阶段的变换操作最终使各个电子元件都起作用。图1表示从这种变换操作的角度看到的各个处理层次。图中的右侧表示同各处理层次相互间变换有关的技术。在原有应用中内在的并行性，在经受图示的那些变形过程中将一点一点地失掉。因此，需要考虑所有这些技术，以便尽可能地提高综合性能。必须看到，只提高某一部分的效率，未必能提高整体的性能。
图中的处理源（primitive）相当于计算机的机器语言，根据所使用的计算模式而定，是一种将处理进行的方法等用逻辑表示的层次。下面的执行形式则根据计算机的物理构造将处理源分配给各个处理装置，这种执行同硬件的特性有关。因此，根据处理源来定下面的动作，便是计算机系统结构的事，而决定执行形式的动作则是处理器结构的事。
2. 并行处理问题和算法
通常，需要庞大计算的科学技术计算，如原子能、核聚变、气象、卫星图像、飞机设计、分子科学、CAD、声音处理、信号处理等，其本身往往就具有很大的并行性，可以进行程序的分析。从计算的分类看，有连续系、离散系、粒子系等，但经常由于只着眼串行处理来开发程序，所以可贵的并行性往往被扼杀。因此希望开发一开始就想到并行处理的算法，这就是并行程序设计并行性变化的构造。此外，对算法优劣的评价，要受运行它的计算机的结构、处理分配方式等强烈的影响，所以在实际评价时，必须考虑这些因素。
在知识信息处理中，同样也内在有很大的并行性。这说明如果改变计算的模式，它将对算法的描述方法及其并行性起巨大影响，所以希望利用知识信息处理的框架，以便今后进一步开发应用程序并进行分析。这一领域的处理往往基本是发现性的探索，这时为了对付简单的逐一探索而引起的计算量爆炸性增大，需要采用某种算法。实际上，优良算法的效果很大，比起略微增加处理器的数目更为有效。
3. 并行程序设计语言及并行性的抽出
并行程序设计语言的作用，在于具体地、形式地表现算法，并进而在计算机上运行时给以建议。前一作用，普通程序设计语言本来就有，但从并行处理的观点看，还起有给程序以明示的并行性的作用。当然也希望能像以前的巨型计算机那样，进行自动向量化的编译，尽管程序并未明示但可自动地取出其并行性，不过仅有这一点还不够，为了取出更多的并行性，需要程序的相互配合。在计算机上运行时的建议，有给出程序内出现的动态型存储容量及串流型缓冲区容量的估计值，在各部分产生冲突时给出优先顺序，以及在众多处理器上执行时给出各作业分配方法的建议等，这些对高效率的运行在目前都是不可少的。一般说来，并不要求在程序上强制给出这些指示，程序只要表示出算法就可以了。但是，现在并行执行的方法论尚未成熟，因此在某种程度上要有这些要求。即使今后，恐怕也是某个层次上的程序所应有的功能。
目前，并行程序设计语言有PL/I及Ada，这些系在任务层次上给予并行处理描述。至于在语句的层次上，除了以前为ILLIACIV使用而开发的语言外，最近又有基于CSP而开发出来的Occam语言。对FORTRAN所具有的记述并行处理的能力也进行了研究。还进行了阵列运算系及模块构造化等研究，这些都是为了使并行性的分析及目标码的生成变得容易。
此外，还可以根据语言及计算模式来组成计算机系统以进行并行处理。函数型语言、逻辑型语言、产生式系统、语义网络、面向目标的语言等，所有这一切都和并行处理有密切关系。
关于并行性的检出，在以前自动向量化的编译程序中，只在DO循环的最内侧进行，现在也进行了在DO循环之间求并行性，以及在子程序之间取出并行任务这样并行性的研究o还对通过图形变换减少其冗长的依赖关系以改变循环构造、提高循环伺的并行性进行了研究。
作为并行处理的支持软件，开发了以巨型机作为对象的程序生成、调试、执行各阶段的支持软件。对程序生成来说，有能够指示程序的分割和数据配置方法的软件。对调试来说，有通过对数据参照/定义关系及子程序从属关系等进行分析以进行并行性认识和动态数据流分析的工具。对支持执行来说，除认识并行性的编译程序外，还有执行时数据库管理、任务间分配/同步以及数据传递控制用的各种软件。
4. 计算模式
从70年代中期便开始根据计算模式及程序设计语言的研究，来探讨支持它们的结构。现在暂不讨论并行计算模式的一般问题，只对比较具体的问题加以介绍。首先，集并行处理的理论模式研究之大成的是数据流模式，由于它容易最大限度地抽出程序所含的并行性，所以广被研究。特别是从不规则形式程序中抽出好用的并行性，当流水线方式和阵列式计算机难以奏效时，具有其他方式难以做到的特性。最近，不单在多抽出并行性，而且还在根据需要控制这些并行性以有效利用计算机资源方面下功夫。
数据流机用的语言基本上是函数型的，所以关于函数型计算模式的研究也很多。以更换字节内容作为中心来进行处理的减法机，有Berkling机、Mago机、ALICE机等，从并行性的角度看，它们都是性能良好的模式。
在计算模式中设定谓词逻辑的研究，作为第五代计算机研究项目而著称。所用的语言除Prolog外，还有一些其他方案，最近出现了以并行处理为主的新语言Guarded Horn Clauses。对这些语言的处理源进行了研讨，并对PM、PIE、PARK. KPR等并行度相当高的并行推理机开展了研究。这种模式适于把知识作为库的处理形态，正尝试使其往知识获得、学习、自动设计程序等功能接近。
在专家系统的构造中经常使用产生式系统，进行了从结构方面对其进行支持的研究，以OPS6作为对象的有DADO、PSM等，它们使用多个处理器对字节内容进行并行探索以达到更高的速度。
还进行了对作为知识表示方法之一的语义网络直接用硬件支持的研究。如Connection Machine，探讨了使用104 ~ 106个处理器的方案。
还有在支持更高效率生成软件的并行性变化中面向目标的计算。它的基本概念就是使称为actor的主体同信息相互交叉进行处理。它作为并行处理模式有很好的相容性。对面向并行目标的语言和面向这种语言的计算结构进行了研究。此外，在其他语言中也有面向目标的考虑，还进行了将目标这一自然单位作为模块程序设计中的模块及作为并行任务的单位的研究。在程序中不是强行用非自然形式的并行处理，而是用目标这样自然单位进行并行处理，当然是非常自然的方法，希望能进行进一步的研究。
如上所述，以计算模式作为中心的并行处理研究有很多。但是，即使计算模式确定了，如何把它放在计算机上执行的源操作选择（处理粒度：granularity）也还有自由度，这正是计算机结构研究的内容。改变计算模式将对算法起巨大影响，因而也使并行性有巨大变化。关于这种基根（radical）的研究，目前还刚开始，今后会有巨大的发展。将并行处理放在传统的冯 · 诺伊曼框框内封闭地进行一般不太费事，但很可能扼杀了并行处理的好处。
5. 执行分配和控制
尽管逻辑上取得许多并行性，但只有把它放在物理的并行机上执行才能最终取得并行的好处，因此执行分配的效率是个问题。就是说，需要决定各并行活度（activity）怎样分配于各处理器中、数据放在哪里，才能有最高效率。这种决定同各活度的处理时间、所需的数据、计算机内通信的开销等有关，而且希望活度处理的结果可以尽可能多地产生新的活度。在使用的处理器个数受到限制时，为了最有效地利用它们，从处理一开始就要尽可能快地使所有处理器都进入工作状态，要在活度分配上狠下功夫，使饱和时刻各处理器都不空闲。
通常，活度的分配方法有三种。一是由程序指定，二是由编译程序分配，三是根据各个时刻各处理器工作状况动态地分配。动态方法乍看很实在，但由于它所用到的负载监控和判断过程需要开销，因此多数还是使用较容易的静态分配方法。此外，即使各活度的处理时间和所需的资源已知，要决定整个执行时间最小的分配方案也要非常多的计算时间，因此必须采用一些有创见的方法。而且作为前提条件的各种信息往往也不知道。因此在实际上，以处理开始时对活度进行静态分配，然后根据大致的工作状况予以简单修正较为现实。这方面目前需要进行许多具体的研究。
要尽可能采用使任务同步的执行控制以减少开销，要在共用存储器的存取方面下点功夫，还要进行用硬件支持同步通信等的研究。
6. 联网和共用存储器
在把许多处理器连接成大规模系统时，联网对其性能有重大影响。作为网络，希望其传递延迟尽可能小，而且传递的吞吐量要大，但网络规模过大经济上不合理，因此考虑通信局部性的网络拓扑方法更为适用。除此之外，网络设计上的重要内容还有换接控制速度、故障时取代路径的功能、网内不要发生死锁等。
最近，还研究了在网内包含相当高级功能的问题。例如，在PIE机上有各处理器负载状况的反馈功能以及自动选择适当处理器的功能，更有甚者，在Ceder项目中还有整理向同一地址进行存取的功能。
当存在许多处理器时，如果它们共有资源，由于集中向共有资源进行存取，使它容易成为整体性能的瓶颈。这是设计高并行系统时的常识。但是，共用存储器作为处理器间通信功能是非常好的，所以又希望采用它。解决这一矛盾的方法有：将共有存储器分成许多组以减少其竞争以及使用多读单写存储器。后一方法利用了对共用存储器的读出要求比写入要求多许多倍的特性，所以备有好几套具有同一拷贝内容的存储器以避免读出时的竞争。日本神户大学的PARK和庆义塾大学的(SM)2机便使用这一方法。
7. 调试及故障排除
即使用并行程序设计语言写成了程序，如何进行调试还是个难题。计算的流程是多个的流程，而且相互关系是非确定的。仍按以前的步骤调试显然是困难的，希望有更彻底的解决方法。例如，在数据流方式中可利用作为函数的框架，在面向目标的系统中可利用信息的问答。
当系统中元素数目增加时，需要在组成系统时考虑各元素的故障。必须使故障元素的确定、隔离及系统内再组成等比较容易。为了使高并行计算机得以实用，要采用计算机容错技术。
四、最新研究动向
1. 大规模阵列式计算机系统
为了并行处理研究和科学技术计算，现在由几十个乃至几千个处理器组成的系统很多。筑波大学的PAX，Calitech的Cosmic Cube、Mosaic，ITT的CAP等均是，作为商用的有Sequent公司的Balance等。由于32位微处理器的出现，构成一级或系统都很容易，其结合的形式有阵列的、超立体的和总线的。
2. 巨型（超级）计算机
Cray-1之类的商用巨型计算机，以流水线运算器为中心而组成，每一步只花5纳秒，正逐渐接近硅器件的极限。因此，除了改用GaAs等更高速的元件外，还要作其他努力，如设置多条流水线、采用阵列式处理器等并行结构。根据多年来对大规模科学技术计算的分析结果，其用途可分成好几类，并明确了适合这些用途的各种并行结构。即可分为流水线方式、SIMD方式、MIMD方式等，根据不同问题而选用它们，甚至有柔性的结构可以动态地再组成以进行SIMD/MIMD的选择。为了进一步高速化，不仅限于在最内层DO循环的向量化，还致力于利用外层循环间的并行性和过程间的并行性。不仅日本有关于巨型计算机的计划，美国也有Cedar计划。在Cedar中将巨大的并行处理的单位称为宏数据流。现在关于这类巨母机的计划，全世界多达几十个。除了上面举出的外，还有洛仑兹利巴莫阿研究所的S-1、IBM的RP3、ITT的CAP、CDC的Cyberplus等多种。
3. 面向VLSI的结构
今后的计算机几乎都要用VLSI，其中有些是强烈面向VLSI的系统。采用VLSI可以得到的好处有容易获得同样的构造、可使软件硬件化、元素间通信代价小等，因此要致力于以存储器构造为中心的设计和高度的并行处理。
典型的例子就是Systric阵列。目前还不能达到实用规模，但正慢慢地走向实用化。卡内基梅隆大学计算机视觉所用的Systric阵列计算机Warp就是一例。正尝试用整个芯片来安装Systric阵列。
厚木通研的AAP-1是256×256的阵列处理器，利用它的规则构造可以通过VLSI化而做得很小。
此外，还进行了三维VLSI的研究，估计在90年代就能掌握10-20层的技术。目前在发热及制造技术方面还存在有问题。通过掌握更多的元件集成可达到小型化，而且由于三维化使用垂直接线故连线延迟缩短，可以达到高速化。
4. 数据流机
从数据流概念明确以来，在这十年左右制造了许多试验机。曼彻斯特大学的计算机、图卢兹大学的LAU、TI的DDMI、东京大学的TOPSTAR、武藏野通研的DFM、冲电气的DDDP、MIT的MEF、电总研的EM-3和SIGMA-1、ICOT的PIM-D等都是。对其结果进行了评价，通常对具有并行性的问题，都取得非常优秀的并行效益。需要的门数比一般的计算机多，而且需要的存储容量也大。对向量运算这样定形的处理以流水线方式的计算机为好，对具有非定形并行性的问题以数据流机更有效。
6. 知识处理机
自从提出第五代计算机计划以来，日本进行了许多以谓词逻辑作为对象的并行推理机的研究。有ICOT的PIM-P2、PIM-R，东大的PIE，京大的PR，神户大的K-Prolog，电总研的Dialog，BIT的OR Parallel Token Machine，Bull的Multi SCHUSS，ECRC的并行符号机等。最初多以Pure Prolog为对象，现在有取用串流并行和AND并行的动向，今后恐怕将以GHC的支持作为话题。要对它们进行评价，需要积累适当的作为评价标准的程序。
关于函数型机，有1986年2月开始工作的伦敦帝国学院的ALICE、正在制造中的Mago机，还有MIT在制造中的Multilisp机。
对产生式系统的支持，有哥仑比亚大学的DADO和卡内基梅隆大学的PSM。这两种正好成明显的对照，DADO面向个数多而低速的处理器，而PSM则面向个数少而高速的处理器系统。此外，施朗贝尔丘公司的FAIM-1也是以支持人工智能处理为目的，在面向目标的框架中放进一些语言样式。
用结构直接支持语义网络的有Thinking Machine公司的Connection Machine、卡内基梅隆大学的Bolzmann Machine、电总研的IX号机等，这些都是采用超过104个处理器的大规模系统。如果从另一角度看，这些都是内含逻辑的存储器，在掌握了大规模元件技术的今天应考虑一下接近联想存储器的组成。
6. 专用计算机系统
最近的一个动向就是开发了许多专用机。对各个专门领域的应用问题进行分析，制造适合这些用途的计算机，在元件价格便宜的今天，是种切实可行的方法。如在图像处理、图形处理、信号处理、CAD、数据库等领域，便制造了许多专用机。在巨型计算机的大型项目中，研讨了卫星图像处理、三维图像处理等专用机。至于Goodyear Aerospace的MPP则是图像专理专用机，IBM的YSE和NEC的HAL则是回路/逻辑仿真专用机，Britton-Lee的IDM、ICOT的Delta、东大的GRACE则是数据库处理专用机。
上述这些问题只有通过硬件化才能取得巨大效益，例如富士通的分光相关系统FX，采用以FFT（傅立叶快速变换）为主的处理，可达到每秒1200亿次操作。这样的速度，一般的巨型机也难以做到，所以需要制造专用机。
五、结束语
并行处理达到今天的水平，得力于对计算机处理能力不断提高的要求和元件技术的发展。现在不断地积累了一些研究成果，概括起来有两点经验。
第一点目的要明确，要针对用途进行分析、确定处理方案以制造专用系统，并配置使它便于使用的支持软件。其次，对开发通用并行处理机来说，尽管现在有了必要的手段但要全面开花仍是困难的，必须看到计算模式和语言的并行性变换都非常重要。要使并行活度分配等控制方法同结构紧密联系起来。
总之，要想用仿真方法来弄清并行处理的所有状况是困难的，所以试制是非常重要的。
以前的计算机系统通过通道、SVP、CCP等将功能不断地分散，这些也算是广义的并行处理，但是对真正并行处理这样密并行来说只是一种粗并行。商用的并行机正陆续推出，今后才是并行处理真正的发展时期。并行处理不是一种特殊系统，甚至可以说串行处理倒是并行处理的一种特殊执行形式。现在并行处理正从专用系统中慢慢地往其他方面推广，可以期待它的今后发展。
（《情报处理》（日）1987，No1，p. 3 ~ 9）