【信息技术篇】并行计算及其发展

1.计算科学与并行计算的提出
    随着计算机和计算方法的飞速发展，几乎所有的学科都走向定量化和精确化，从而产生了一系列诸如计算物理、计算化学、计算生物学、计算地质学、计算气象学和计算材料科学等的计算科学，在世界上逐渐形成了一门计算性的学科分支，即计算科学与工程，简称为CSE(Computational Science & Engineering)。当今，计算科学已经和传统的两种科学即理论科学和实验科学，并列成为第三门科学，它们彼此相辅相成地推动科学发展与社会进步。在很多情况下，或者是理论模型复杂甚至理论尚未建立，或者实验费用昂贵甚至实验无法进行，此时计算就成为求解问题的唯一或主要手段。计算极大地增强了人们从事科学研究的能力，大大地加速了把科技转化为生产力的过程，深刻地改变着人类认识世界和改造世界的方法和途径。计算科学的理论和方法，作为新的研究手段和新的设计与制造技术的理论基础，正推动着当代科学与技术向纵深发展。
    计算科学所涉及的计算方法，即我们平常所说的算法，是求解问题的方法和步骤，而并行算法则是指用多台计算机联合求解问题的方法和步骤。现在，并行算法之所以受到极大的重视，是为了提高计算速度（单机受物理速度限制无法满足）、提高计算精度（加密、计算网格等）以及满足实时计算需要（数值天气预报等）。而并行计算，简单地说，就是在并行计算机上所作的计算，它和常说的高性能计算，超级计算是同义词，因为在任何高性能计算和超级计算总离不开使用并行技术。

 

2.并行计算概述
    所谓并行计算，是指同时使用多种计算资源解决计算问题的过程。为执行并行计算，计算资源应包括一台配有多处理机（并行处理）的计算机、一个与网络相连的计算机专有编号，或者两者结合使用。并行计算的主要目的是快速解决大型且复杂的计算问题。此外还包括：利用非本地资源，节约成本 ― 使用多个“廉价”计算资源取代大型计算机，同时克服单个计算机上存在的存储器限制。
    传统地，串行计算是指在单个计算机（具有单个中央处理单元）上执行软件写操作。CPU 逐个使用一系列指令解决问题，但其中只有一种指令可提供随时并及时的使用。并行计算是在串行计算的基础上演变而来，它努力仿真自然世界中的事务状态：一个序列中众多同时发生的、复杂且相关的事件。
    为利用并行计算，通常计算问题表现为以下特征：
（1）将工作分离成离散部分，有助于同时解决；
（2）随时并及时地执行多个程序指令；
（3）多计算资源下解决问题的耗时要少于单个计算资源下的耗时。
    并行计算是相对于串行计算来说的，所谓并行计算分为时间上的并行和空间上的并行。时间上的并行就是指流水线技术，而空间上的并行则是指用多个处理器并发的执行计算。
    并行计算科学中主要研究的是空间上的并行问题。空间上的并行导致了两类并行机的产生，按照Flynn的说法分为：单指令流多数据流（SIMD）和多指令流多数据流（MIMD）。我们常用的串行机也叫做单指令流单数据流（SISD）。 MIMD类的机器又可分为以下常见的五类： 并行向量处理机(PVP) 、对称多处理机(SMP) 、大规模并行处理机(MPP) 、工作站机群(COW) 、分布式共享存储处理机(DSM)。
 
3.并行处理计算机系统
    并行处理计算机的结构特点主要表现在两个方面：①在单处理机内广泛采用各种并行措施；②由单处理机发展成各种不同耦合度的多处理机系统。并行处理的主要目的是提高系统的处理能力。有些类型的并行处理计算机系统（如多处理机系统）还可以提高系统的可靠性。由于器件的发展，并行处理计算机系统具有较好的性能价格比，而且还有进一步提高的趋势。

结构原理  并行处理计算机的结构主要有流水线方式 、多功能部件方式 、阵列方式、多处理机方式和数据流方式。
流水线处理机  将指令的执行过程分解为若干段，每段进行一部分处理。一条指令顺序流过所有段即执行完毕获得结果。当本条指令在本段已被处理完毕而进入下段时，下条指令即可流入本段。因此，在整个流水线上可以同时处理若干条指令。若各段的执行时间均为一个时钟节拍，则在正常情况下每拍可以输出一个结果，即完成一条指令。这就可加快处理机的速度。程序中相邻指令的相关性会影响流水线处理机效率的发挥。例如，条件转移指令在上条指令执行完以前，有时不能确定后继指令；又如本条指令需要用上条指令的结果作为操作数等，都将中断流水线而使效率下降。
多功能部件处理机  一台处理机具有多个功能部件。各功能部件可以并行地处理数据，因而处理机可以使用不同的功能部件并行执行几条指令，以提高处理速度。如有的计算机具有浮点加、定点加、浮点乘、浮点除、逻辑操作、移位等多个对不同数据进行处理的功能部件。一些流水线向量机也含有多个功能部件。程序在执行中因对各部件的需求不平衡，各功能部件不可能全部处于忙碌状态。指令间的相关性也影响机器的效率，如本条指令所需的功能部件尚在执行其他指令；又如本条指令所需操作数恰为尚未执行完毕的指令的结果等。
阵列处理机  一台处理机由多个相同的处理部件和一个统一的控制器组成。这个控制器解释指令并传送操作命令至全部处理部件。各处理部件按照控制器的命令同时进行完全相同的操作。阵列处理机又可分为浮点阵列处理机和位片式阵列处理机两类。
多处理机系统  多处理机系统能提高系统的性能和可靠性。它是多指令流多数据流处理机。根据系统中各处理机的耦合程度，多处理机系统可分为两类。①非直接耦合的多处理机系统：系统中各处理机均有主存储器。各处理机由各自的操作系统进行管理，它们通过共享的输入输出系统进行通信。②直接耦合的多处理机系统：系统中各处理机共享主存储器，并受统一的操作系统管理。多处理机系统一般指直接耦合这一类。
数据流处理机  数据流处理机是受到人们重视的高度并行的处理机。它虽保留了存储程序的做法，但在主要原理上已与诺依曼计算机结构不同。它不按程序计数器指出的指令顺序执行程序，只要所需操作数全部具备，指令即可被执行，亦即程序的执行不是由控制流驱动，而是由数据流驱动。数据流处理机是以语言为基础的处理机。它使用数据流程序图作为用户语言与计算机结构之间的接口。数据流程序图用能动框表示。每个能动框有多个域，分别存放操作码、操作数和目标地址。数据流程序以能动框集合的方式保存在能动存储器中。当某条指令可以执行时，相应的能动框地址便被送入指令排队器。读取部件则按地址从存储器中取出该能动框，形成操作包，送至操作部件进行处理，产生结果包。修改部件根据结果包的目标地址将结果数据送至规定的能动框作为操作数，并将具备操作数的指令的地址送至指令排队器。指令排队器中的指令均具备执行条件，因而只需增加部件数量或增强部件流水程度，就可以高速并行执行。此外，还可将多个指令处理单元连接成数据流多处理机系统，进一步提高处理能力。

 

4.并行算法设计概述
    算法是解题方法的精确描述，是一组有穷的规则，它们规定了解决某一特定类型问题的一系列运算。
    并行算法是一些可同时执行的诸进程的集合，这些进程互相作用和协调动作从而达到给定问题的求解。并行算法可从不同的角度分类成数值计算的和非数值计算的并行算法；同步的、异步的和分布式的并行算法；共享存储的分布存储的并行算法；确定的和随机的并行算法等等。
数值计算 是指基于代数关系运算的一类诸如矩阵运算、多项式求值、求解线性方程组等数字计算问题。求解数值计算问题的算法称为数值算法。
非数值计算 是指基于比较关系运算的一类诸如排序，选择、搜索、匹配等符号处理问题。求解非数值计算问题的算法称为非数值算法。
同步算法 是指算法的诸进程的执行必须互等待的一类并行算法。
异步算法 是指算法的诸进程的执行不必相互等待的一类并行算法。
分布算法 是指由通信链路连接的多个场点或节点，协同完成问题求解的一类并行算法。按照上述定义，在局网环境下进行的计算称为分布计算。在Internet流行的今天，可把工作站机群COW环境下进行的计算称为网络计算。推而广之，有人把基于Internet的计算则称为元计算。
确定算法 是指算法的每一步都能明确地指明下一步应该如何行进的一种算法。
随机算法 是指算法的每一步，随机地从指定范围内选取若干参数，由其来确定算法的下一步走向的一种算法。
    并行算法的基本设计技术主要有以下几种：
划分设计技术 用划分法求解问题可分为两步：（1）将给定的问题劈成p个独立的几乎等尺寸的子问题；（2）用p台处理器并行求解诸子问题。划分时关键在于如何将问题进行分组，使得子问题较容易并行求解，或者子问题的解较容易被组合成原问题的解。
分治设计技术 分治策略是一种问题的求解技术，其思想是将一个大而复杂的问题分解成若干特性相同的子问题分而治之。若所得的子问题规模仍嫌过大，可反复使用分治策略，直至很容易求解诸子问题为止。使用分治法时，子问题的类型通常和原问题的类型相同，因此分治法很自然地导致递归过程。一般而言，并行分治法分为三步：（1）将输入划分成若干个规模近于相等的子问题；（2）同时递归地求解各个子问题；（3）归并各子问题的解成为原问题的解。用分治法和划分法求解问题的共同点在于两者均试图将原问题的分解成为可并行求解的子问题，但分治法的侧重点在于子问题的归并上；而划分法的注意力则集中在原问题的划分上。
平衡树设计技术 该方法是将输入元素作为叶节点构筑一棵平衡二叉树，然后自叶向根往返遍历。此法成功的部分原因是在树中能快速地存取所需要的信息。平衡二叉树的方法可推广到内节点的数目不只两个的任意平衡树。这种方法对数据的播送、压缩、抽取和前级计算等甚为有效。
倍增设计技术 又叫指针跳越技术，特别适合处理以链表或有向有根树之类表示的数据结构，在图论和链表算法中有着广泛的应用。每当递归调用时，所要处理的数据之间的距离将逐步加倍，经过k步后就可完成距离为2^k的所有数据的计算。
流水线设计技术 是一项重要的并行技术。它在VLSI并行计算中表现得尤为突出。其基本思想是将一个计算任务t分成一系列子任务t1,t2,…tm,使得一旦t1完成，后继的子任务就可以立即开始，并以同样的速率进行计算。

 

5.并行计算的应用前景举例
一、分布式计算
    所谓分布式计算是一门计算机科学，它研究如何把一个需要非常巨大的计算能力才能解决的问题分成许多小的部分，然后把这些部分分配给许多计算机进行处理，最后把这些计算结果综合起来得到最终的结果。最近的分布式计算项目已经被用于使用世界各地成千上万位志愿者的计算机的闲置计算能力，通过因特网，您可以分析来自外太空的电讯号，寻找隐蔽的黑洞，并探索可能存在的外星智慧生命；您可以寻找超过1000万位数字的梅森质数；您也可以寻找并发现对抗艾滋病病毒的更为有效的药物。这些项目都很庞大，需要惊人的计算量，仅仅由单个的电脑或是个人在一个能让人接受的时间内计算完成是决不可能的。
    分布式计算是利用互联网上的计算机的中央处理器的闲置处理能力来解决大型计算问题的一种计算科学。下面，我们看看它是怎么工作的：
    首先, 要发现一个需要非常巨大的计算能力才能解决的问题。这类问题一般是跨学科的、极富挑战性的、人类急待解决的科研课题。其中较为著名的是:
1. 解决较为复杂的数学问题，例如：GIMPS（寻找最大的梅森素数）。
2. 研究寻找最为安全的密码系统，例如：RC-72（密码破解）。
3. 生物病理研究，例如：Folding@home（研究蛋白质折叠，误解，聚合及由此引起的相关疾病）。
4. 各种各样疾病的药物研究，例如：United Devices（寻找对抗癌症的有效的药物）。
5. 信号处理，例如：SETI@Home（在家寻找地外文明）。

    从这些实际的例子可以看出，这些项目都很庞大，需要惊人的计算量，仅仅由单个的电脑或是个人在一个能让人接受的时间内计算完成是决不可能的。在以前，这些问题都应该由超级计算机来解决。但是, 超级计算机的造价和维护非常的昂贵，这不是一个普通的科研组织所能承受的。随着科学的发展，一种廉价的、高效的、维护方便的计算方法应运而生——分布式计算！
    随着计算机的普及，个人电脑开始进入千家万户。与之伴随产生的是电脑的利用问题。越来越多的电脑处于闲置状态，即使在开机状态下中央处理器的潜力也远远不能被完全利用。我们可以想象，一台家用的计算机将大多数的时间花费在“等待”上面。即便是使用者实际使用他们的计算机时,处理器依然是寂静的消费，依然是不计其数的等待（等待输入，但实际上并没有做什么）。互联网的出现, 使得连接调用所有这些拥有限制计算资源的计算机系统成为了现实。
    当然，这看起来也似乎很原始、很困难，但是随着参与者和参与计算的计算机的数量的不断增加, 计算计划变得非常迅速，而且被实践证明是的确可行的。目前一些较大的分布式计算项目的处理能力已经可以达到甚而超过目前世界上速度最快的巨型计算机。
    分布式计算是近年提出的一种新的计算方式。所谓分布式计算就是在两个或多个软件互相共享信息，这些软件既可以在同一台计算机上运行，也可以在通过网络连接起来的多台计算机上运行。分布式计算比起其它算法具有以下几个优点：
1、稀有资源可以共享，
2、通过分布式计算可以在多台计算机上平衡计算负载，
3、可以把程序放在最适合运行它的计算机上，
其中，共享稀有资源和平衡负载是计算机分布式计算的核心思想之一。
实际上，网格计算就是分布式计算的一种。如果我们说某项工作是分布式的，那么，参与这项工作的一定不只是一台计算机，而是一个计算机网络，显然这种“蚂蚁搬山”的方式将具有很强的数据处理能力。网格计算的实质就是组合与共享资源并确保系统安全。
二、基于GPU的计算
    GPU英文全称Graphic Processing Unit，中文翻译为“图形处理器”。GPU是相对于CPU的一个概念，由于在现代的计算机中（特别是家用系统，游戏的发烧友）图形的处理变得越来越重要，需要一个专门的图形的核心处理器。

    GPU所有计算均使用浮点算法，而且目前还没有位或整数运算指令。此外，由于GPU专为图像处理设计，因此存储系统实际上是一个二维的分段存储空间，包括一个区段号（从中读取图像）和二维地址（图像中的X、Y坐标）。此外，没有任何间接写指令。输出写地址由光栅处理器确定，而且不能由程序改变。这对于自然分布在存储器之中的算法而言是极大的挑战。最后一点，不同碎片的处理过程间不允许通信。实际上，碎片处理器是一个SIMD数据并行执行单元，在所有碎片中独立执行代码。
    简单说GPU就是能够从硬件上支持T&L（Transform and Lighting，多边形转换与光源处理）的显示芯片，因为T&L是3D渲染中的一个重要部分，其作用是计算多边形的3D位置和处理动态光线效果，也可以称为“几何处理”。一个好的T&L单元，可以提供细致的3D物体和高级的光线特效；只大多数PC中，T&L的大部分运算是交由CPU处理的(这就也就是所谓的软件T&L)，由于CPU的任务繁多，除了T&L之外，还要做内存管理、输入响应等非3D图形处理工作，因此在实际运算的时候性能会大打折扣，常常出现显卡等待CPU数据的情况，其运算速度远跟不上今天复杂三维游戏的要求。即使CPU的工作频率超过1GHz或更高，对它的帮助也不大，由于这是PC本身设计造成的问题，与CPU的速度无太大关系。
    GPU擅长执行矢量和矩阵运算，其三维变换计算都是矩阵运算。而且其片元处理中涉及大量的数学运算。GPU天生具有并行性，往往是对屏幕上所有点进行相同的运算。这也是采用GPU作图形处理比CPU效率高得多的一个主要原因。
三、多核时代
    多内核是指在一枚处理器中集成两个或多个完整的计算引擎(内核)。多核技术的开发源于工程师们认识到，仅仅提高单核芯片的速度会产生过多热量且无法带来相应的性能改善，先前的处理器产品就是如此。他们认识到，在先前产品中以那种速率，处理器产生的热量很快会超过太阳表面。即便是没有热量问题，其性价比也令人难以接受，速度稍快的处理器价格要高很多。英特尔工程师们开发了多核芯片，使之满足“横向扩展”（而非“纵向扩充”）方法，从而提高性能。该架构实现了“分治法”战略。

    通过划分任务，线程应用能够充分利用多个执行内核，并可在特定的时间内执行更多任务。多核处理器是单枚芯片（也称为“硅核”），能够直接插入单一的处理器插槽中，但操作系统会利用所有相关的资源，将它的每个执行内核作为分立的逻辑处理器。通过在两个执行内核之间划分任务，多核处理器可在特定的时钟周期内执行更多任务。
    多核架构能够使目前的软件更出色地运行，并创建一个促进未来的软件编写更趋完善的架构。尽管认真的软件厂商还在探索全新的软件并发处理模式，但是，随着向多核处理器的移植，现有软件无需被修改就可支持多核平台。
    操作系统专为充分利用多个处理器而设计，且无需修改就可运行。为了充分利用多核技术，应用开发人员需要在程序设计中融入更多思路，但设计流程与目前对称多处理 (SMP) 系统的设计流程相同，并且现有的单线程应用也将继续运行。
    现在，得益于线程技术的应用在多核处理器上运行时将显示出卓越的性能可扩充性。此类软件包括多媒体应用（内容创建、编辑，以及本地和数据流回放）、工程和其他技术计算应用以及诸如应用服务器和数据库等中间层与后层服务器应用。
    多核技术能够使服务器并行处理任务，而在以前，这可能需要使用多个处理器，多核系统更易于扩充，并且能够在更纤巧的外形中融入更强大的处理性能，这种外形所用的功耗更低、计算功耗产生的热量更少。
    现在面临的多核带给软件业的挑战：（1）对于传统软件而言，传统的软件开发多为串行程序开发，随着 CPU 频率的提升自然能得到性能提升，而多核CPU现行的频率并不高，在多核 CPU 上，单独一个核心的性能并不会比高频 CPU高。软件如何充分利用多核 CPU 的资源成为需要解决问题。（2）现行的程序设计语言，包括它们的 Library多为串行设计，如C++及它的 STL，Boost；Java Class Library，.NET Framework。
四、量子计算
    量子计算的概念最早由IBM的科学家R. Landauer及C. Bennett于70年代提出。他们主要探讨的是计算过程中诸如自由能、信息与可逆性之间的关系。80年代初期，阿岗国家实验室的P. Benioff首先提出二能阶的量子系统可以用来仿真数字计算；稍后费因曼也对这个问题产生兴趣而着手研究，并在1981年于麻省理工学院举行的First Conference on Physics of Computation中给了一场演讲，勾勒出以量子现象实现计算的愿景。1985年，牛津大学的D. Deutsch提出量子图林机的概念，量子计算才开始具备了数学的基本型式。然而上述的量子计算研究多半局限于探讨计算的物理本质，还停留在相当抽象的层次，尚未进一步跨入发展算法的阶段。

    1994年，贝尔实验室的应用数学家P. Shor指出，相对于传统电子计算器，利用量子计算可以在更短的时间内将一个很大的整数分解成质因子的乘积。这个结论开启量子计算的一个新阶段：有别于传统计算法则的量子算法(quantum algorithm)确实有其实用性，绝非科学家口袋中的戏法。自此之后，新的量子算法陆续的被提出来，而物理学家接下来所面临的重要的课题之一，就是如何去建造一部真正的量子计算器，来执行这些量子算法。许多量子系统都曾被点名做为量子计算器的基础架构，例如光子的偏振、空腔量子电动力学、离子阱以及核磁共振等等。以目前的技术来看，这其中以离子阱与核磁共振最具可行性。事实上，核磁共振已经在这场竞赛中先驰得点：以I. Chuang为首的IBM研究团队在2002年的春天，成功地在一个人工合成的分子中(内含7个量子位)利用NMR完成N =15的因子分解。

 

 

【参考文献】
[1]陈国良：《并行计算---结构.算法.编程》，高等教育出版社，1999年10月

                                                                                   （本文作于：2008年5月）1.计算科学与并行计算的提出

    随着计算机和计算方法的飞速发展，几乎所有的学科都走向定量化和精确化，从而产生了一系列诸如计算物理、计算化学、计算生物学、计算地质学、计算气象学和计算材料科学等的计算科学，在世界上逐渐形成了一门计算性的学科分支，即计算科学与工程，简称为CSE(Computational Science & Engineering)。当今，计算科学已经和传统的两种科学即理论科学和实验科学，并列成为第三门科学，它们彼此相辅相成地推动科学发展与社会进步。在很多情况下，或者是理论模型复杂甚至理论尚未建立，或者实验费用昂贵甚至实验无法进行，此时计算就成为求解问题的唯一或主要手段。计算极大地增强了人们从事科学研究的能力，大大地加速了把科技转化为生产力的过程，深刻地改变着人类认识世界和改造世界的方法和途径。计算科学的理论和方法，作为新的研究手段和新的设计与制造技术的理论基础，正推动着当代科学与技术向纵深发展。
    计算科学所涉及的计算方法，即我们平常所说的算法，是求解问题的方法和步骤，而并行算法则是指用多台计算机联合求解问题的方法和步骤。现在，并行算法之所以受到极大的重视，是为了提高计算速度（单机受物理速度限制无法满足）、提高计算精度（加密、计算网格等）以及满足实时计算需要（数值天气预报等）。而并行计算，简单地说，就是在并行计算机上所作的计算，它和常说的高性能计算，超级计算是同义词，因为在任何高性能计算和超级计算总离不开使用并行技术。

 

2.并行计算概述
    所谓并行计算，是指同时使用多种计算资源解决计算问题的过程。为执行并行计算，计算资源应包括一台配有多处理机（并行处理）的计算机、一个与网络相连的计算机专有编号，或者两者结合使用。并行计算的主要目的是快速解决大型且复杂的计算问题。此外还包括：利用非本地资源，节约成本 ― 使用多个“廉价”计算资源取代大型计算机，同时克服单个计算机上存在的存储器限制。
    传统地，串行计算是指在单个计算机（具有单个中央处理单元）上执行软件写操作。CPU 逐个使用一系列指令解决问题，但其中只有一种指令可提供随时并及时的使用。并行计算是在串行计算的基础上演变而来，它努力仿真自然世界中的事务状态：一个序列中众多同时发生的、复杂且相关的事件。
    为利用并行计算，通常计算问题表现为以下特征：
（1）将工作分离成离散部分，有助于同时解决；
（2）随时并及时地执行多个程序指令；
（3）多计算资源下解决问题的耗时要少于单个计算资源下的耗时。
    并行计算是相对于串行计算来说的，所谓并行计算分为时间上的并行和空间上的并行。时间上的并行就是指流水线技术，而空间上的并行则是指用多个处理器并发的执行计算。
    并行计算科学中主要研究的是空间上的并行问题。空间上的并行导致了两类并行机的产生，按照Flynn的说法分为：单指令流多数据流（SIMD）和多指令流多数据流（MIMD）。我们常用的串行机也叫做单指令流单数据流（SISD）。 MIMD类的机器又可分为以下常见的五类： 并行向量处理机(PVP) 、对称多处理机(SMP) 、大规模并行处理机(MPP) 、工作站机群(COW) 、分布式共享存储处理机(DSM)。
 
3.并行处理计算机系统
    并行处理计算机的结构特点主要表现在两个方面：①在单处理机内广泛采用各种并行措施；②由单处理机发展成各种不同耦合度的多处理机系统。并行处理的主要目的是提高系统的处理能力。有些类型的并行处理计算机系统（如多处理机系统）还可以提高系统的可靠性。由于器件的发展，并行处理计算机系统具有较好的性能价格比，而且还有进一步提高的趋势。

结构原理  并行处理计算机的结构主要有流水线方式 、多功能部件方式 、阵列方式、多处理机方式和数据流方式。
流水线处理机  将指令的执行过程分解为若干段，每段进行一部分处理。一条指令顺序流过所有段即执行完毕获得结果。当本条指令在本段已被处理完毕而进入下段时，下条指令即可流入本段。因此，在整个流水线上可以同时处理若干条指令。若各段的执行时间均为一个时钟节拍，则在正常情况下每拍可以输出一个结果，即完成一条指令。这就可加快处理机的速度。程序中相邻指令的相关性会影响流水线处理机效率的发挥。例如，条件转移指令在上条指令执行完以前，有时不能确定后继指令；又如本条指令需要用上条指令的结果作为操作数等，都将中断流水线而使效率下降。
多功能部件处理机  一台处理机具有多个功能部件。各功能部件可以并行地处理数据，因而处理机可以使用不同的功能部件并行执行几条指令，以提高处理速度。如有的计算机具有浮点加、定点加、浮点乘、浮点除、逻辑操作、移位等多个对不同数据进行处理的功能部件。一些流水线向量机也含有多个功能部件。程序在执行中因对各部件的需求不平衡，各功能部件不可能全部处于忙碌状态。指令间的相关性也影响机器的效率，如本条指令所需的功能部件尚在执行其他指令；又如本条指令所需操作数恰为尚未执行完毕的指令的结果等。
阵列处理机  一台处理机由多个相同的处理部件和一个统一的控制器组成。这个控制器解释指令并传送操作命令至全部处理部件。各处理部件按照控制器的命令同时进行完全相同的操作。阵列处理机又可分为浮点阵列处理机和位片式阵列处理机两类。
多处理机系统  多处理机系统能提高系统的性能和可靠性。它是多指令流多数据流处理机。根据系统中各处理机的耦合程度，多处理机系统可分为两类。①非直接耦合的多处理机系统：系统中各处理机均有主存储器。各处理机由各自的操作系统进行管理，它们通过共享的输入输出系统进行通信。②直接耦合的多处理机系统：系统中各处理机共享主存储器，并受统一的操作系统管理。多处理机系统一般指直接耦合这一类。
数据流处理机  数据流处理机是受到人们重视的高度并行的处理机。它虽保留了存储程序的做法，但在主要原理上已与诺依曼计算机结构不同。它不按程序计数器指出的指令顺序执行程序，只要所需操作数全部具备，指令即可被执行，亦即程序的执行不是由控制流驱动，而是由数据流驱动。数据流处理机是以语言为基础的处理机。它使用数据流程序图作为用户语言与计算机结构之间的接口。数据流程序图用能动框表示。每个能动框有多个域，分别存放操作码、操作数和目标地址。数据流程序以能动框集合的方式保存在能动存储器中。当某条指令可以执行时，相应的能动框地址便被送入指令排队器。读取部件则按地址从存储器中取出该能动框，形成操作包，送至操作部件进行处理，产生结果包。修改部件根据结果包的目标地址将结果数据送至规定的能动框作为操作数，并将具备操作数的指令的地址送至指令排队器。指令排队器中的指令均具备执行条件，因而只需增加部件数量或增强部件流水程度，就可以高速并行执行。此外，还可将多个指令处理单元连接成数据流多处理机系统，进一步提高处理能力。

 

4.并行算法设计概述
    算法是解题方法的精确描述，是一组有穷的规则，它们规定了解决某一特定类型问题的一系列运算。
    并行算法是一些可同时执行的诸进程的集合，这些进程互相作用和协调动作从而达到给定问题的求解。并行算法可从不同的角度分类成数值计算的和非数值计算的并行算法；同步的、异步的和分布式的并行算法；共享存储的分布存储的并行算法；确定的和随机的并行算法等等。
数值计算 是指基于代数关系运算的一类诸如矩阵运算、多项式求值、求解线性方程组等数字计算问题。求解数值计算问题的算法称为数值算法。
非数值计算 是指基于比较关系运算的一类诸如排序，选择、搜索、匹配等符号处理问题。求解非数值计算问题的算法称为非数值算法。
同步算法 是指算法的诸进程的执行必须互等待的一类并行算法。
异步算法 是指算法的诸进程的执行不必相互等待的一类并行算法。
分布算法 是指由通信链路连接的多个场点或节点，协同完成问题求解的一类并行算法。按照上述定义，在局网环境下进行的计算称为分布计算。在Internet流行的今天，可把工作站机群COW环境下进行的计算称为网络计算。推而广之，有人把基于Internet的计算则称为元计算。
确定算法 是指算法的每一步都能明确地指明下一步应该如何行进的一种算法。
随机算法 是指算法的每一步，随机地从指定范围内选取若干参数，由其来确定算法的下一步走向的一种算法。
    并行算法的基本设计技术主要有以下几种：
划分设计技术 用划分法求解问题可分为两步：（1）将给定的问题劈成p个独立的几乎等尺寸的子问题；（2）用p台处理器并行求解诸子问题。划分时关键在于如何将问题进行分组，使得子问题较容易并行求解，或者子问题的解较容易被组合成原问题的解。
分治设计技术 分治策略是一种问题的求解技术，其思想是将一个大而复杂的问题分解成若干特性相同的子问题分而治之。若所得的子问题规模仍嫌过大，可反复使用分治策略，直至很容易求解诸子问题为止。使用分治法时，子问题的类型通常和原问题的类型相同，因此分治法很自然地导致递归过程。一般而言，并行分治法分为三步：（1）将输入划分成若干个规模近于相等的子问题；（2）同时递归地求解各个子问题；（3）归并各子问题的解成为原问题的解。用分治法和划分法求解问题的共同点在于两者均试图将原问题的分解成为可并行求解的子问题，但分治法的侧重点在于子问题的归并上；而划分法的注意力则集中在原问题的划分上。
平衡树设计技术 该方法是将输入元素作为叶节点构筑一棵平衡二叉树，然后自叶向根往返遍历。此法成功的部分原因是在树中能快速地存取所需要的信息。平衡二叉树的方法可推广到内节点的数目不只两个的任意平衡树。这种方法对数据的播送、压缩、抽取和前级计算等甚为有效。
倍增设计技术 又叫指针跳越技术，特别适合处理以链表或有向有根树之类表示的数据结构，在图论和链表算法中有着广泛的应用。每当递归调用时，所要处理的数据之间的距离将逐步加倍，经过k步后就可完成距离为2^k的所有数据的计算。
流水线设计技术 是一项重要的并行技术。它在VLSI并行计算中表现得尤为突出。其基本思想是将一个计算任务t分成一系列子任务t1,t2,…tm,使得一旦t1完成，后继的子任务就可以立即开始，并以同样的速率进行计算。

 

5.并行计算的应用前景举例
一、分布式计算
    所谓分布式计算是一门计算机科学，它研究如何把一个需要非常巨大的计算能力才能解决的问题分成许多小的部分，然后把这些部分分配给许多计算机进行处理，最后把这些计算结果综合起来得到最终的结果。最近的分布式计算项目已经被用于使用世界各地成千上万位志愿者的计算机的闲置计算能力，通过因特网，您可以分析来自外太空的电讯号，寻找隐蔽的黑洞，并探索可能存在的外星智慧生命；您可以寻找超过1000万位数字的梅森质数；您也可以寻找并发现对抗艾滋病病毒的更为有效的药物。这些项目都很庞大，需要惊人的计算量，仅仅由单个的电脑或是个人在一个能让人接受的时间内计算完成是决不可能的。
    分布式计算是利用互联网上的计算机的中央处理器的闲置处理能力来解决大型计算问题的一种计算科学。下面，我们看看它是怎么工作的：
    首先, 要发现一个需要非常巨大的计算能力才能解决的问题。这类问题一般是跨学科的、极富挑战性的、人类急待解决的科研课题。其中较为著名的是:
1. 解决较为复杂的数学问题，例如：GIMPS（寻找最大的梅森素数）。
2. 研究寻找最为安全的密码系统，例如：RC-72（密码破解）。
3. 生物病理研究，例如：Folding@home（研究蛋白质折叠，误解，聚合及由此引起的相关疾病）。
4. 各种各样疾病的药物研究，例如：United Devices（寻找对抗癌症的有效的药物）。
5. 信号处理，例如：SETI@Home（在家寻找地外文明）。

    从这些实际的例子可以看出，这些项目都很庞大，需要惊人的计算量，仅仅由单个的电脑或是个人在一个能让人接受的时间内计算完成是决不可能的。在以前，这些问题都应该由超级计算机来解决。但是, 超级计算机的造价和维护非常的昂贵，这不是一个普通的科研组织所能承受的。随着科学的发展，一种廉价的、高效的、维护方便的计算方法应运而生——分布式计算！
    随着计算机的普及，个人电脑开始进入千家万户。与之伴随产生的是电脑的利用问题。越来越多的电脑处于闲置状态，即使在开机状态下中央处理器的潜力也远远不能被完全利用。我们可以想象，一台家用的计算机将大多数的时间花费在“等待”上面。即便是使用者实际使用他们的计算机时,处理器依然是寂静的消费，依然是不计其数的等待（等待输入，但实际上并没有做什么）。互联网的出现, 使得连接调用所有这些拥有限制计算资源的计算机系统成为了现实。
    当然，这看起来也似乎很原始、很困难，但是随着参与者和参与计算的计算机的数量的不断增加, 计算计划变得非常迅速，而且被实践证明是的确可行的。目前一些较大的分布式计算项目的处理能力已经可以达到甚而超过目前世界上速度最快的巨型计算机。
    分布式计算是近年提出的一种新的计算方式。所谓分布式计算就是在两个或多个软件互相共享信息，这些软件既可以在同一台计算机上运行，也可以在通过网络连接起来的多台计算机上运行。分布式计算比起其它算法具有以下几个优点：
1、稀有资源可以共享，
2、通过分布式计算可以在多台计算机上平衡计算负载，
3、可以把程序放在最适合运行它的计算机上，
其中，共享稀有资源和平衡负载是计算机分布式计算的核心思想之一。
实际上，网格计算就是分布式计算的一种。如果我们说某项工作是分布式的，那么，参与这项工作的一定不只是一台计算机，而是一个计算机网络，显然这种“蚂蚁搬山”的方式将具有很强的数据处理能力。网格计算的实质就是组合与共享资源并确保系统安全。
二、基于GPU的计算
    GPU英文全称Graphic Processing Unit，中文翻译为“图形处理器”。GPU是相对于CPU的一个概念，由于在现代的计算机中（特别是家用系统，游戏的发烧友）图形的处理变得越来越重要，需要一个专门的图形的核心处理器。

    GPU所有计算均使用浮点算法，而且目前还没有位或整数运算指令。此外，由于GPU专为图像处理设计，因此存储系统实际上是一个二维的分段存储空间，包括一个区段号（从中读取图像）和二维地址（图像中的X、Y坐标）。此外，没有任何间接写指令。输出写地址由光栅处理器确定，而且不能由程序改变。这对于自然分布在存储器之中的算法而言是极大的挑战。最后一点，不同碎片的处理过程间不允许通信。实际上，碎片处理器是一个SIMD数据并行执行单元，在所有碎片中独立执行代码。
    简单说GPU就是能够从硬件上支持T&L（Transform and Lighting，多边形转换与光源处理）的显示芯片，因为T&L是3D渲染中的一个重要部分，其作用是计算多边形的3D位置和处理动态光线效果，也可以称为“几何处理”。一个好的T&L单元，可以提供细致的3D物体和高级的光线特效；只大多数PC中，T&L的大部分运算是交由CPU处理的(这就也就是所谓的软件T&L)，由于CPU的任务繁多，除了T&L之外，还要做内存管理、输入响应等非3D图形处理工作，因此在实际运算的时候性能会大打折扣，常常出现显卡等待CPU数据的情况，其运算速度远跟不上今天复杂三维游戏的要求。即使CPU的工作频率超过1GHz或更高，对它的帮助也不大，由于这是PC本身设计造成的问题，与CPU的速度无太大关系。
    GPU擅长执行矢量和矩阵运算，其三维变换计算都是矩阵运算。而且其片元处理中涉及大量的数学运算。GPU天生具有并行性，往往是对屏幕上所有点进行相同的运算。这也是采用GPU作图形处理比CPU效率高得多的一个主要原因。
三、多核时代
    多内核是指在一枚处理器中集成两个或多个完整的计算引擎(内核)。多核技术的开发源于工程师们认识到，仅仅提高单核芯片的速度会产生过多热量且无法带来相应的性能改善，先前的处理器产品就是如此。他们认识到，在先前产品中以那种速率，处理器产生的热量很快会超过太阳表面。即便是没有热量问题，其性价比也令人难以接受，速度稍快的处理器价格要高很多。英特尔工程师们开发了多核芯片，使之满足“横向扩展”（而非“纵向扩充”）方法，从而提高性能。该架构实现了“分治法”战略。

    通过划分任务，线程应用能够充分利用多个执行内核，并可在特定的时间内执行更多任务。多核处理器是单枚芯片（也称为“硅核”），能够直接插入单一的处理器插槽中，但操作系统会利用所有相关的资源，将它的每个执行内核作为分立的逻辑处理器。通过在两个执行内核之间划分任务，多核处理器可在特定的时钟周期内执行更多任务。
    多核架构能够使目前的软件更出色地运行，并创建一个促进未来的软件编写更趋完善的架构。尽管认真的软件厂商还在探索全新的软件并发处理模式，但是，随着向多核处理器的移植，现有软件无需被修改就可支持多核平台。
    操作系统专为充分利用多个处理器而设计，且无需修改就可运行。为了充分利用多核技术，应用开发人员需要在程序设计中融入更多思路，但设计流程与目前对称多处理 (SMP) 系统的设计流程相同，并且现有的单线程应用也将继续运行。
    现在，得益于线程技术的应用在多核处理器上运行时将显示出卓越的性能可扩充性。此类软件包括多媒体应用（内容创建、编辑，以及本地和数据流回放）、工程和其他技术计算应用以及诸如应用服务器和数据库等中间层与后层服务器应用。
    多核技术能够使服务器并行处理任务，而在以前，这可能需要使用多个处理器，多核系统更易于扩充，并且能够在更纤巧的外形中融入更强大的处理性能，这种外形所用的功耗更低、计算功耗产生的热量更少。
    现在面临的多核带给软件业的挑战：（1）对于传统软件而言，传统的软件开发多为串行程序开发，随着 CPU 频率的提升自然能得到性能提升，而多核CPU现行的频率并不高，在多核 CPU 上，单独一个核心的性能并不会比高频 CPU高。软件如何充分利用多核 CPU 的资源成为需要解决问题。（2）现行的程序设计语言，包括它们的 Library多为串行设计，如C++及它的 STL，Boost；Java Class Library，.NET Framework。
四、量子计算
    量子计算的概念最早由IBM的科学家R. Landauer及C. Bennett于70年代提出。他们主要探讨的是计算过程中诸如自由能、信息与可逆性之间的关系。80年代初期，阿岗国家实验室的P. Benioff首先提出二能阶的量子系统可以用来仿真数字计算；稍后费因曼也对这个问题产生兴趣而着手研究，并在1981年于麻省理工学院举行的First Conference on Physics of Computation中给了一场演讲，勾勒出以量子现象实现计算的愿景。1985年，牛津大学的D. Deutsch提出量子图林机的概念，量子计算才开始具备了数学的基本型式。然而上述的量子计算研究多半局限于探讨计算的物理本质，还停留在相当抽象的层次，尚未进一步跨入发展算法的阶段。

    1994年，贝尔实验室的应用数学家P. Shor指出，相对于传统电子计算器，利用量子计算可以在更短的时间内将一个很大的整数分解成质因子的乘积。这个结论开启量子计算的一个新阶段：有别于传统计算法则的量子算法(quantum algorithm)确实有其实用性，绝非科学家口袋中的戏法。自此之后，新的量子算法陆续的被提出来，而物理学家接下来所面临的重要的课题之一，就是如何去建造一部真正的量子计算器，来执行这些量子算法。许多量子系统都曾被点名做为量子计算器的基础架构，例如光子的偏振、空腔量子电动力学、离子阱以及核磁共振等等。以目前的技术来看，这其中以离子阱与核磁共振最具可行性。事实上，核磁共振已经在这场竞赛中先驰得点：以I. Chuang为首的IBM研究团队在2002年的春天，成功地在一个人工合成的分子中(内含7个量子位)利用NMR完成N =15的因子分解。

 

 

【参考文献】
[1]陈国良：《并行计算---结构.算法.编程》，高等教育出版社，1999年10月

                                                                                   （本文作于：2008年5月）