并行计算

Disambig gray.svg此条目的主题是parallel computing。关于concurrent computing，请见“并发计算”。

并行计算（英语：parallel computing）一般是指许多指令得以同时进行的计算模式。在同时进行的前提下，可以将计算的过程分解成小部分，之后以并发方式来加以解决[1]。

电脑软件可以被分成数个运算步骤来执行。为了解决某个特定问题，软件采用某个算法，以一连串指令执行来完成。传统上，这些指令都被送至单一的中央处理器，以循序方式执行完成。在这种处理方式下，单一时间中，只有单一指令被执行（processor level: 比较微处理器，CISC, 和RISC，即流水线Pipeline的概念，以及后来在Pipeline基础上以提高指令处理效率为目的的硬件及软件发展，比如branch-prediction, 比如forwarding，比如在每个运算单元前的指令堆栈，汇编程序员对programm code的顺序改写）。并行运算采用了多个运算单元，同时执行，以解决问题。

基本体系结构

相对于串行计算，并行计算可以划分成时间并行和空间并行。时间并行即指令流水化，空间并行使用多个处理器执行并发计算，当前研究的主要是空间的并行问题。以程序和算法设计人员的角度看，并行计算又可分为数据并行和任务并行。数据并行把大的任务化解成若干个相同的子任务，处理起来比任务并行简单。

空间上的并行导致两类并行机的产生，按照麦克·弗莱因（Michael Flynn）的说法分为单指令流多数据流（SIMD）和多指令流多数据流（MIMD），而常用的串行机也称为单指令流单数据流（SISD）。MIMD类的机器又可分为常见的五类：并行向量处理机（PVP）、对称多处理机（SMP）、大规模并行处理机（MPP）、工作站机群（COW）、分布式共享存储处理机（DSM）。

访存模型

并行计算机有以下五种访存模型：均匀访存模型（UMA）、非均匀访存模型（NUMA）、全高速缓存访存模型（COMA）、一致性高速缓存非均匀存储访问模型（CC-NUMA）和非远程存储访问模型（NORMA）。

并行计算模型

不像串行计算机那样，主流使用冯·诺伊曼的计算模型，并行计算机没有一个统一的计算模型。不过，人们已经提出了几种有价值的参考模型：PRAM模型，BSP模型，LogP模型，C^3模型等。

并行计算机网络

并行计算机是靠网络将各个处理机或处理器连接起来的，一般来说有以下几种方式

  1. 静态连接：一维线性连接，网孔连接，超立方体连接，树连接，立方环连接，洗牌交换连接，蝶形连接，金字塔连接等。
  2. 动态连接：总线连接（Bus），交叉开关（CS），多级互联网络（MIN）。

网络的基本术语：

  1. 节点度
  2. 网络直径
  3. 对剖宽度
  4. 嵌入

并行计算机性能度量

  1. 基本指标
    1. 执行时间
    2. 工作负载
    3. 访问性能
  2. 加速比评测
    1. Amdahl定理
    2. Gustafson定理（英语：Gustafson's law）
    3. Sun-Ni定理
  3. 可扩放性标准
    1. 等效率标准
    2. 等速度标准
    3. 平均延迟标准

并行算法

并行算法是一门还没有发展成熟的学科，虽然人们已经总结出了相当多的经验，但是远远不及串行算法那样丰富。并行算法设计中最常用的的方法是PCAM方法，即划分，通信，组合，映射。首先划分，就是将一个问题平均划分成若干份，并让各个处理器去同时执行；通信阶段，就是要分析执行过程中所要交换的数据和任务的协调情况，而组合则是要求将较小的问题组合到一起以提高性能和减少任务开销，映射则是要将任务分配到每一个处理器上。总之，并行算法还需要相当多完善的地方。 并行算法与串行算法最大的不同之处在于，并行算法不仅要考虑问题本身，而且还要考虑所使用的并行模型，网络连接等等。

  • 常见的非数值算法设计方法举例
    • 并行播送与并行求和
    • 并行排序算法；
    • 并行选择算法：所谓选择问题就是在一给定的序列中选择出某组（个）满足给定条件的元素。
    • 关于图论中的一些并行算法：
      • 图论作为一门到近代才发展起来的科学。在图论中有很多关于如何设计算法的问题，比如求最小生成树，单源最短路径等等。事实上，这些算法中有很多是可以并行化的，而且并行化时运用的思想具有很大的启发性，下面是几个常见的并行图论算法。
    • 关于串处理的并行算法：
      • KMP算法的并行化：在英特尔的开发手册《Intel® 64 and IA-32 Architectures Optimization Reference Manual》中，“14.3.3 Substring Searches”章节内提供了KMP算法基于SIMD指令集并行的C语言实现例程，可以作为KMP算法并行化的参考范例。其中涉及到若干SIMD Intrinsics指令，比如：_mm_loadu_si128、_mm_cmpestrs、_mm_cmpestri等，其具体含义及用法可从 Intel Intrinsics Guide（ https://intel-intrinsics.com/ （页面存档备份，存于互联网档案馆） ）在线手册中查询获悉。
  • 常见的数值算法设计方法举例

参考文献

  1. ^ 平行計算基礎理論,系統及應用研究. 国立中正大学信息工程研究所. 1992 [2 June 2013]. 

参见

  • 计算机科学
  • 理论计算机科学
  • 消息传递接口 （Message Passing Interface － MPI）