并行计算

并行计算（Parallel Computing），或称平行计算，是相对于传统的串行计算（Sequential Computing）而言的一种计算方法。它是一种算法范式，允许一次性执行多个指令或任务，其核心目标在于提高计算速度，并通过扩大问题求解的规模，来解决大型且复杂的计算问题。所谓的并行计算，可以被划分为时间上的并行和空间上的并行两大类。时间上的并行主要是指“流水线技术”（Pipelining），而空间上的并行则是指使用多个处理器并发地执行计算任务。

并行计算（Parallel Computing）是指在同一时间内使用多种计算资源来协同解决一个计算问题的过程，是提高计算机系统计算速度和处理能力的一种有效手段。其基本思想是：利用多个处理器来共同求解同一个问题，即将一个庞大且复杂的待解问题分解成若干个（可同时处理的）部分，每一部分都由一个独立的处理机（或处理器核心）来进行并行计算。一个并行计算系统既可以是一台专门设计的、包含大量处理器的超级计算机（Supercomputer），也可以是由若干台独立计算机通过网络互连而构成的集群（Cluster）。系统通过并行计算集群完成指定数据的处理，最后将处理的结果汇总并返回给用户。

时间上的并行，主要是指流水线技术。以工厂生产食品为例，一个完整的流程分为：1. 清洗；2. 消毒；3. 切割；4. 包装。如果不采用流水线技术，一个食品必须完成上述所有四个步骤后，下一个食品才能开始进入流程处理，这种方式耗时且效率低下。但如果采用流水线技术，工厂可以在同一时间点上，同时处理四个处于不同工序的食品（例如，食品A在包装，食品B在切割，食品C在消毒，食品D在清洗）。这就是并行算法中的时间并行，它通过在同一时间启动两个或两个以上的操作，实现工序的重叠，从而大大提高计算性能。

空间上的并行，是指多个处理机并发地执行计算任务。具体而言，就是通过网络将两个或两个以上的处理机连接起来，使它们能够同时计算同一个任务的不同部分，或者是协同解决单个处理机无法独立完成的大型问题。例如，小李准备在植树节种三棵树，如果仅他1个人，可能需要6个小时才能完成全部任务。但在植树节当天，他邀请了好友小红和小王共同参与，三个人在同一时刻开始各自挖坑植树。2个小时后，每个人都完成了一棵树的种植任务，总任务得以完成。这就是并行算法中的空间并行，它将一个大任务分割成多个相同的子任务，交由不同的处理单元执行，以此来显著加快问题的解决速度。

为了能够有效地利用并行计算，一个计算问题通常需要表现出以下几个典型特征：
（1）能够将总工作负载分离成若干个离散的部分，以便于这些部分能够被同时求解；
（2）系统能够在任意时刻，及时地执行多个程序指令；
（3）使用多计算资源解决该问题的总耗时，要显著少于使用单个计算资源下的耗时。

并行计算科学中主要研究的是空间上的并行问题。从程序和算法设计人员的角度来看，空间并行又可细分为数据并行（Data Parallelism）和任务并行（Task Parallelism）。一般而言，数据并行的处理相对容易，因为它主要是将一个大任务分解成多个数据不同、但处理逻辑相同的子任务；而任务并行则涉及处理逻辑也不同的子任务。

空间上的并行催生了不同类型的并行计算机。按照Michael J. Flynn（弗林）的分类法，主要分为：单指令流多数据流（SIMD）和多指令流多数据流（MIMD）。我们日常所用的传统串行计算机则被称为单指令流单数据流（SISD）。

在MIMD（多指令流多数据流）类型的机器中，又可细分为以下几种常见的体系结构：
1. 并行向量处理机（PVP）
2. 对称多处理机（SMP）
3. 大规模并行处理机（MPP）
4. 工作站机群（COW）
5. 分布式共享存储处理机（DSM）

并行计算机根据其处理器访问内存的方式不同，有以下五种主流的访存模型：
1. 均匀访存模型（UMA, Uniform Memory Access）
2. 非均匀访存模型（NUMA, Non-Uniform Memory Access）
3. 全高速缓存访存模型（COMA, Cache-Only Memory Access）
4. 一致性高速缓存非均匀存储访问模型（CC-NUMA, Cache-Coherent NUMA）
5. 非远程存储访问模型（NORMA, No-Remote Memory Access）

并行计算机领域不像串行计算机那样，全世界基本都在使用冯·诺伊曼（von Neumann）的计算模型。由于并行体系结构的多样性，目前尚未有一个完全统一的计算模型。尽管如此，学术界和工业界已经提出了几种具有重要价值的参考模型，例如：PRAM（Parallel Random Access Machine）模型、BSP（Bulk Synchronous Parallel）模型、LogP模型以及C^3模型等。

并行计算机是依靠网络将各个处理机（或处理器）连接起来协同工作的。根据网络连接方式的不同，大致可分为以下几类：

静态连接是指处理单元之间具有固定的点到点链接，在程序执行期间，这种连接拓扑保持不变。典型的静态网络拓扑结构包括：一维线性阵列（1D Linear Array）、二维网孔（2D Mesh）、树形连接（Tree）、超立方网络（Hypercube）、立方环（Cube-Connected Ring）、洗牌交换网（Shuffle-Exchange）以及蝶形网络（Butterfly）等。

动态连接是指网络由交换开关（Switching Elements）构成，系统可根据应用程序的通信需求或算法特性，动态地改变处理器之间的连接组态。典型的动态网络包括：总线（Bus）网络、交叉开关（Crossbar）网络和多级互连网络（MINs）等。

在描述并行计算机网络拓扑时，常用到以下几个基本术语：

节点度（Node Degree）: 指射入或射出一个节点的边的总数。在单向网络中，通常指入射边和出射边之和。
网络直径（Network Diameter）: 指网络中任意两个节点之间最短路径的最大值，即所有“最长最短路”的长度。
对剖宽度（Bisection Width）: 指将网络对等（或近似对等）地分割为两半时，所必须移去的（即跨越两个子网的）最少边数。
对剖带宽（Bisection Bandwidth）: 指每秒钟内，在最小的对剖平面上（即上述最少边数所构成的切面上）能够通过所有连线的最大信息位数（或字节数）。

评估一个并行计算系统或算法的性能，涉及多个维度的指标。

· 执行时间： 完成计算任务所消耗的总时间。
· 工作负载： 需要处理的计算任务的总量。
· 存储性能： 系统在数据存储和访问方面的能力，包括容量和速度。

加速比（Speedup）是衡量并行计算相对于串行计算性能提升的核心指标。用于评测加速比的经典理论包括：
· AMDahl（阿姆达尔）定理： 描述了在固定问题规模下，系统加速比受限于程序中必须串行执行部分（Sequential Partion）的比例。
· Gustafson（古斯塔夫森）定理： 描述了在固定时间内，可扩展的问题规模（Scaled Problem Size）随处理器数量的增长关系。
· Sun-Ni（孙-倪）定理： 也称存储限制模型，探讨了在存储容量限制下的加速比问题。

可扩放性（Scalability）用于衡量当处理器数量增加时，并行系统保持其性能（如效率）的能力。主要标准包括：
· 等效率标准（Isoefficiency）： 衡量为保持并行效率不变，问题规模需要如何随处理器数量增长。
· 等速度标准（Isospeed）： 衡量为保持每个处理器上的计算速度不变，问题规模需要如何增长。
· 平均延迟标准（Average Latency）： 关注在扩展过程中，通信延迟的平均变化情况。

云计算（Cloud Computing）是在并行计算、分布式计算、网格计算等技术发展到一定阶段后才产生的概念，它继承了并行计算的许多核心思想，两者在很多方面有着共性。因此，学习并行计算对于深入理解云计算具有极大的帮助，并行计算是学习云计算的必修基础课程之一。但是，并行计算不等于云计算，云计算也不等同于并行计算，两者存在明显区别：

（1）云计算萌芽于并行计算
云计算的萌芽可以追溯到计算机的并行化。并行计算机的出现，源于人们不满足于CPU摩尔定律带来的单核性能增长速度，希望通过将多个计算机（或处理器）并联起来的方式，获得更强大的计算速度。这是一种朴素且有效的实现高速计算的方法，并在后续发展中被证明是相当成功的。

（2）并行计算、网格计算多用于特定科学领域和专业用户
传统的并行计算和后来的网格计算（Grid Computing），其提出主要是为了满足科学（如物理、化学、气象）和工程技术（如CAE仿真）领域的专业计算需求，其应用领域也基本局限于此。传统并行计算机的使用是一项高度专业的工作，需要使用者具备较高的专业素质，且多数操作依赖于命令行界面，这对于许多专业人士而言尚有门槛，更不用说普通的业余级用户。

（3）并行计算追求极致的高性能
在并行计算（特别是高性能计算HPC）的时代，人们极力追求的是计算速度的极限，通常采用昂贵的、定制化的服务器和高速互连网络。各国不惜巨额投入，在计算速度（如TOP500排名）上展开竞争。因此，并行计算时代的高性能机群在某种意义上是一种“快速消费品”。由于技术迭代极快，一台大型机群如果在3年左右不能得到充分利用，其性能就可能远远落后于新系统，导致巨额投资难以收回。

（4）云计算对单节点的计算能力要求相对较低
与并行计算追求“顶配”不同，云计算时代并不刻意追求使用昂贵的、定制化的服务器，也不必过分关注TOP500的排名。云计算中心的基础架构（IaaS）天然支持资源的动态伸缩，其计算力和存储力可根据业务需求逐步增加。云计算倾向于使用大量“商品化”的廉价硬件（Commodity Hardware）来构建集群，因此，高性能计算在云计算时代，更像是一种可按需购买、弹性扩展的“耐用消费品”，而非一次性投入的“快速消费品”。