并行计算的基本问题及现状分析

林彬

[摘 要] 从1946年世界上第一台计算机ENIAC诞生至今的60多年时间里，计算机的体系结构发生了巨大的变化。尤其是过去的20年，是超级计算机，特别是并行机飞速发展，走向成熟的20年。20年中CPU芯片的性能翻了几番，计算机工作者发明了Wormhole（虫蚀寻径）技术，找到了更符合实际的LogP并行计算模型，创造了成百的不同规模、不同拓扑结构的并行平台。特别是，由于多种软硬件技术的进步，是既具有可扩展性，又具有可编程性的，分布式共享存储结构的并行机成为可能。并行计算机已理所当然地成为当今超级计算机的主流。本文主要从为什么要进行并行计算入手，探讨了并行计算的基本涵义、处理模式、发展现状以及发展趋势。

[关键词] 并行计算；现状；发展

doi ： 10 . 3969 / j . issn . 1673 - 0194 . 2014 . 16. 071

[中图分类号] TP368 [文献标识码] A [文章编号] 1673 - 0194（2014）16- 0121- 03

0 引 言

工作中，我们总是希望我们自己工作得更有效率，用更少的时间解决更多的问题。在计算机里，这就是并行计算的基本初衷。全世界第一台计算机ENIAC中就已经出现了并行计算的概念。它有20个累加器，可以并发执行多个加减运算，可谓开并行计算的先河。在随后的20世纪五六十年代，由于晶体管和集成电器的发明，出现了更多更快的计算机。IBM是这一时期的主角，同期计算机编程语言的出现，由软件完成处理并行计算的思想进一步深化。但这一时期的计算还是大型机时代，没有几个平民能用得起这些昂贵的东西。计算机和软件技术还锁在研究院和大学校园里。

20世纪70年代，随着微电子技术的发展，出现了微型处理器（CPU）。接着，1974年，全世界第一台个人电脑——牛郎星顺利出炉。紧随其后，看到市场前景的苹果和IBM推波助澜，计算机开始进入个人时代。个人计算机同时又催生了软件业的高速发展，软件又带动CPU不断升级换代。这为并行计算摆脱高端路线，进入平民化时代打下了基础。

1 并行计算的基本问题

1.1 为什么需要并行计算

在个人计算机诞生后的几十年里，程序员们编写了大量的应用软件，这些软件决大部分了采用串行计算方法。所谓串行，是指软件在PC上执行，在进入CPU前被分解为一个个指令，指令在CPU中一条条顺序执行。任一时间内，CPU只能够运行一条指令。这种方式很符合我们对现实世界的思考习惯。至于软件的运行速度，则依赖硬件的处理能力，尤其CPU的处理速度。这种思维方式到了2005年遇到了挑战。在那一年，受限于制造CPU的半导体材料限制，左右CPU发展的摩尔定律开始失效了。但芯片业很快找到了一个变通的办法：在一块芯片中植入多个处理核心，通过多核的共同运算，提高运行速度。不幸的是，采用串行方法编写的软件面临着一个尷尬的局面：如果仍采用串行编程方式，运行速度将停滞不前。这样，原来需要CPU完成的提速工作，被迫需要软件自已来完成。 在另一个领域：互联网，由于网络数据极速膨胀，数据量已经远远超过一台或者几台大型计算机的处理能力，需要更大数量的计算机协同完成。面对这些问题，主要的解决方案就是：并行计算。

1.2 并行计算的涵义

并行计算目前还是一门发展中的学科。并行计算是相对串行计算而言的，并行计算可以分为时间上的并行计算和空间上的并行计算。

时间上的并行计算就是流水线技术，即采用指令预取技术，将每个指令分成多步，各步间叠加操作，当前指令完成前，后一指令准备就绪，缩小指令执行的时钟周期。典型的以时间换空间。

空间上的并行计算是指由多个处理单元（不仅是CPU）执行的计算，是以空间换时间。空间上的并行计算分为两类：单指令多数据流（SIMD）和多指令多数据流（MIMD）。

SIMD是流水技术的扩展，可以在一个时钟周期处理多个指令，我们目前使用的PC大多属于此列，例如AMD 3DNOW 和Intel MMX。

MIMD大致又分为5类：工作站集群（COW）、对称多处理机（SMP）、大规模并行处理机（MPP）、分布共享存储处理机（DSM）、并行向量机（PVP）。

空间并行计算技术包括数据并行计算和任务并行计算。数据并行计算是指将一个大的数据分解为多个小的数据，分散到多个处理单元执行。任务并行是将大的任务分解为小的任务，分散到多个处理单元执行，任务并行同时还要避免任务重复执行，协调数据的上下文关系，避免冲突发生。任务并行计算与实际应用需求紧密相关。所以，任务并行计算要比数据并行计算复杂得多。并行计算与串行计算的最大不同在于，并行计算不仅要考虑计算本身，还要考虑并行处理模型、网络通信、计算协作诸多问题。

1.3 主要的并行计算体系类型

1.3.1 工作站集群（COW Cluster of Workstation）

工作站集群可以理解为：PC+网络。它可以由少数几台PC扩展到数千个节点的大规模并行系统，既可以是廉价的并行程序调试环境，也可以成为的高性能计算平台。集群由于低成本，动态可扩充的特点，已经成为高性能计算平台的主流。目前Google搜索和云计算业务即采用这一方式。 我国的联想深腾XXXX、曙光XXXX系列均属此类。

1.3.2 多处理系统（SMP Symmetric Multi Processing）

它由多个紧耦合多处理器组成，最大特点就是共享全部资源。

1.3.3 大规模并行处理系统（MPP Massively Parallel Processing）

由许多松耦合处理单元（不是处理器）组成的。这种结构与SMP对立，每个单元自成体系，包括CPU、内存、硬盘、操作系统，最大特点是不共享资源。刀片服务器属于此列。

1.3.4 分布式共享存储多处理（DSM）

它可以视为对SMP的可扩充，将共享数据映射到不同的物理位置。数据的同步由硬件或者软件来完成。是目前高性能计算机的主流发展方向之一。

1.3.5 并行向量机（PVP，Parallel Vector Processor）

PVP使用专用的向量处理器，提供数据共享，通过高速交叉开关实现通信。向量运算是一种较简单的并行计算，适用面很广，机器比较容易实现，使用也方便，因此向量处理机（向量机）在20世纪70年代获得了迅速发展。

1.4 并行计算的处理模式

1.4.1 主从模型（MS，Master-slave）

即有一个主进程，其他是从进程。主进程负责整个系统的控制（包括任务调度、负载平衡），从进程负责对数据的处理和计算任务。Google搜索业务目前就是采用的这种编程模型。

1.4.2 对称处理模型（SPM）

这种架构没有主从概念之分，所有进程的地位都是平等的。在并行执行过程中，我们可以任意选择其中一个进程执行输入输出操作，其他进程扮演同样的角色。

1.4.3 多程序处理模型（MPPM）

在计算机集群中，每台计算机节点执行不同的程序和相同的程序。

1.5 并行计算设计原则

（1）适应性。并行算法是并行计算的基础，是为解决实际问题而出现，必须与实际应用相结合。

（2）可扩展。并行算法是否能够随计算节点增加或减少而同步的线性变化，是评价一个并行算法是否有效的重要标志之一。

（3）粗粒度。通常情况下，粒度越大越好。这是因为在每个处理机中有很多需要计算的工作任务，如此可以充分发挥多处理机的作用。并行加速比对细粒度问题一般情况下是不会很高的，这也是为什么并行计算需要求解大规模问题的原因所在。

（4）减少通信。一个高效的并行算法，通信是至关。提高性能的一个关键是减少数据通信量和通信次数。

（5）优化性能。评价性能的优缺，主要是看单节点计算的处理能力，和并行执行效率。这与实际采用的技术息息相关。

1.6 并行计算设计方法

1.6.1 分片

（1）数据分片。数据分片包括两类：数值分片和哈希分片。数值分片适用于已知数据范围的分解，如果Int、Long类型处理。哈希分片适用于未知数据范围的数据分解，包括字符串，字节数组类型。

数据分片是把相同的操作作用于不同的数据，达到提到快速求解的目的。数据分片模型是一种较高层次的并行计算模型，编程却相对简单。数据分片的并行计算最早应用于并行向量计算机（PVP）。经过长期实践表明，该技术可以高效地求解大部分的科学和工程计算问题。数据并行处理对象是数值，对应非数值类问题，则需要其他并行计算模型来解决。Google的搜索业务是采用数据分片的并行计算模式。

（2）任务分片。任务分片的并行计算主要针对非数值类的并行处理。它通常的消息传递机制（目前主流是PMI）是各并行计算执行单元之间通过传递消息来交换数据，协调步伐，执行控制操作。消息传递一般是针对分布节点内存，也可以适用于共享内存的并行节点。消息传递模型为程序员提供了更加灵活的控制手段和表现形式。消息传递模型很容易实现，控制变化手段灵活多样，但是需要程序员有丰富的并行编程经验。是一种较低层次，编程相对复杂的模型，适用于业务流程的并行化处理。

1.6.2 通信

协调计算过程中的数据共享。通信工作目前主要由TCP/IP协议完成。

1.6.3 组织

组织各任务并发执行，提高性能。在主线程的控制下，子线程在此承担具体的并发操作任务。

1.6.4 映射

分配任务（分布处理、共享处理）。线程和通信共同完成。

1.7 并行计算应注意的事项

（1）任务分解：这是所有并行计算的核心问题，优秀的任务分解需要保证平均和处理负载的平衡，同时，随着处理器能力的动态伸缩动态调节。

（2）通信：并发处理离不开网络通信联系。相较与CPU运算，数据在网络间传递延迟是并发处理的瓶颈之一。光纤网络是目前最好的选择。

（3）并行协调：是并行运算过程中控制流程。

（4）并行冲突：并行冲突来源主要是任务分解和并行协调。

（5）数据归并：这是数据计算完成后，必不可少的一步操作。数据归并需要注意：过滤重复数据，合并相关性数据等。

（6）死锁。死锁是在编程过程中，由于人为的原因造成。死锁表示为：对象间在不放弃自己资源下互相调用。请程序员注意。

2 并行计算的发展现状

2.1 多核为主流的体系结构

多核处理器代表了计算技术的一次创新。由于数字数据和互联网的全球化，商业和消费者开始要求多核处理器带来性能改进，这个重要创新就开始了，因为多核处理器比单核处理器具有性能和效率优势，多核处理器将会成为被广泛采用的计算模型。在驱动PC安全性和虚拟化技术的重大进程过程中，多核处理器扮演着中心作用，这些安全性和虚拟化技术的开发用于为商业计算市场提供更大的安全性、更好的资源利用率、创造更大价值。普通消费者用户也期望得到前所未有的性能，这将极大地扩展其家庭PC和数字媒体计算系统的使用。多核处理器具有不增加功耗而提高性能的好处，实现更大的性能/能耗比。

在一个处理器中放入两个或多个功能强大的计算核产生了一个重大的可能性。由于多核处理器能提供比单核处理器更好的性能和效率，下一代的软件应用程序很有可能是基于多核处理器而开发的。不管这些应用是帮助专业的电影公司以更少的投入和更少的时间完成更真实的电影，还是以更彻底的方法使得PC更自然和直观，多核处理器技术将永远改变计算世界。多核处理器表达了AMD了解顾客需求并且开发最能满足客户要求产品的意愿。

微软多核计算的主管Dan Reed称，整个世界上很缺乏那些并行计算的研究人员，而一个间接的原因就是学院里对于并行计算的关注度不够，而这些学院正是下一代软件开发人员诞生的地方。越来越高的时钟频率导致应用程序的代码运行得越来越快，而对于当前多核处理器来讲这一规则虽然成立，但却有所不同。而这种不同可以做一个形象的比喻，那就是一部跑车和一辆学校的巴士。当跑车能够以很快的速度飞奔时，巴士虽然比较慢，但它可以载着更多的人前行。问题就是，简单地在计算机CPU上增加多个核并不能增加传统应用程序代码的运行速度，这一结果是根据一项来自于Forrester研究公司的报告得出的。换句话说，复杂的工作需要拆分来填充这辆巴士上的空座位。Forrester的报告还谈到：当前四核处理器会激发更多的多处理器设计的思想，2009年x86的服务器使用64个处理器核，并且2012年台式机也已实现了这一梦想。

2.2 以数据为中心的云计算

云计算可以被解释为虚拟主机的租赁服务，也可以被解释为企业软件的SaaS化，又或者是一个“云机箱”之上跑许多个虚拟桌面。但不管怎么说笔者认为云计算要解决3个实质问题：

（1）大规模。这里提到的大规模不仅是超过单台PC服务器的能力，更指的是能够支撑互联网级别的数据和应用，例如个人邮箱、搜索等。

（2）低成本。低成本的一个标志在于用系统软件来解决廉价硬件在复杂条件下不可靠的问题。

（3）服务运营。这里所指的服务运营是能够通过无差别的存储计算能力来提供公共的基础服务。

当各式各样的应用可以共同运行在一个统一平台之上，才能达到真正的大规模，而由此得到的规模效益才能够获得低成本，于是这3个本质的问题是云计算的有机整体。

传统的软件以功能为主体，而云计算则彻底推动了“数据为王”。数据将成为一家企业乃至是一个国家极其重要的战略资源。而数据的搜集、存储、分享、处理和应用是需要大量的计算资源的，从这个意义上说，云计算可以称为“以数据为中心的分布式大规模计算”。而一个企业乃至一个国家瞬间能够调用的计算资源则成为了能否利用和发挥好数据这个战略资源的核心竞争力。提供公共计算服务的云计算平台将大大促进企业之间、社会各行业间的数据收集、分享和实时处理，在这基础之上必将孕育出大量的数据运营的新商业模式，数据也将最终成为一切商业行为的决策基础，从而大大提高社会的整体效率，促进人类从大工业化时代走向信息化时代。

2.3 以普及应用为宗旨的个人高性能计算机

作为三大科学研究手段之一的高性能计算机，其发展的根本动力来自于各类科学技术对计算机性能永无止境的需求和生产的实际需要。

在1996年的“SuperComputing96”大会上，美国政府HPCC计划全国协调委员会主席John Toole在题为“危机、创新与机会：HPCC将向何处去”的报告中指出：“高性能计算与通信对美国的国家安全及保持美国在未来的优势至关重要。美国政府将在高端计算机与通信、大规模网络、高可信系统等5个方面制定10～15年的长期计划，保持长期持续性投资。”

过去的10年是超级计算机、特别是并行机飞速发展、走向成熟的10年。10年中CPU芯片的性能翻了几番，计算机工作者发明了Wormhole（虫蚀寻径）技术，找到了更符合实际的LogP并行计算模型，创造了成百的不同规模、不同拓扑结构的并行平台。特别是，由于多种软硬件技术的进步，使既具有可扩展性、又具有可编程性的、分布式共享存贮结构的并行机成为可能。并行计算机是当今超级计算机的主流。

并行计算机的发展史就是可扩展性与可编程性这一对矛盾相互作用直至统一的历史。可扩展性是并行计算机最大的优势，可简单定义为“在确定的应用背景下，计算机系统的性能要随处理机数的增加而线性增长”（美籍并行处理专家黄铠教授语）。可扩展性包括规模可扩展、时间可扩展和问题可扩展几个方面。规模可扩展的要点是均衡，均衡的目的是防止瓶颈的发生，“三T”表达了当今均衡的指标。时间可扩展也称换代可扩展，主要指体系不受限于芯片、器件、工艺等。问题可扩展指格点增加时，系统能适应问题规模的扩大，而当问题的粒度加大时，效率能相应提高。现有的MPP，如Inetl的Paragon、IBM的SP/2、国内的曙光1000，一般认为是可以扩展的。

可编程性是在并行机发展的过程中，伴随可扩展性而产生的新概念。并行计算机有共享与分布式两种存储结构，所以操作系统进程间的通信（IPC）也有两种不同的机制：共享变量和信息传递。机器结构和操作系统的这些区别又影响到支撑软件和应用软件的编程模式。SMP的程序设计仍以传统的高级语言为基础，系统提供自动并行识别或增加并行语言成分。而MPP必须建立另一种编程环境（如PVM、MPI等），在程序中显式地写出信息的发送和接收。这不仅导致应用软件编写困难，还给广大用户增加了很多负担。为此，创建了一个新的单词Programmability，用以描述并行计算机的这一重要特点。

高性能计算机已走过了整整20年，这是一段可扩展性与可编程性这一对矛盾相互作用直至统一的历史。市场需求是发展的动力，技术进步是发展的条件。有专家估计，从现在起直到21世纪若干年，DSM结构将是超级计算机的主流，将稳固地占领超级计算机的主要市场。

3 并行计算的发展——机群系统

机群系统是利用高速通用网络将一组高性能工作站或高档PC机，按某种结构连接起来，在并行程序设计以及可视化人机交互集成开发环境支持下，统一调度，协调处理，实现高效并行处理的系统。从结构和结点间的通信方式来看，它属于分布存储系统。机群系统中的主机和网络可以是同构的，也可以是异构的。机群系统之所以能够从技术可能发展到实际应用，主要原因是它与传统的并行处理系统相比有以下几个明显的特点：

（1）系统开发周期短。由于机群系统大多采用商用工作站和通用LAN网络，节省了大量的研制时间。

（2）系统价格低。构成机群的工作站或高档PC机是批量生产的，因而售价较低。

（3）用户投资风险小。机群系统不仅是一个并行处理系统，它的每个结点同时也是一台独立的工作站，即使整个系统对某些应用问题并行效率不高，它的结点仍然可以作为单个工作站使用。

（4）系统扩展性好。机群系统大多使用通用网络，系统扩展容易。

（5）节约系统资源。由于机群系统的结构比较灵活，可以将不同体系结构，不同性能的工作站连在一起，这样就可以充分利用现有设备。

（6） 用户编程方便。机群系统中，程序的并行化还是在用户熟悉的编程环境C、C++或Fortran下实现的。

总之，随着网络技术的发展和对机群系统研究的深入，特别是高效通信机制的开发，机群系统的通信性能将会接近专用的互联网络，并行编程环境和工具更加完善，有望在机群系统上解决粒度更细的应用问题，使并行处理系统的应用领域更加广泛。

4 结束语

并行计算目前尚不是一门成熟的技术，有待我们继续努力和完善。受到CPU单核处理能力的限制，必须采用并行计算是提高软件运行速度的主要出路。但是由于并行编码的难度远超过串行处理，这是我们面临的巨大挑战。共同努力！

主要参考文献

[1]中国行业研究网.2014-2018年中国并行计算行业市场全景调研及投资价值预测研究报告[EB/OL].http：//www.chinairn.com/report/20140308/100414413.html.

[2]陈国良，等.并行计算的一体化研究现状及发展趋势[J].科学通报，2009（8）.