一、并行计算基础

1.1 概念

并行计算是相对于串行计算来说的。它是一种一次可执行多个指令的算法，目的是提高计算速度，
及通过扩大问题求解规模，解决大型而复杂的计算问题。

简单来讲，并行计算就是同时使用多个计算资源来解决一个计算问题。

 1.2 并行计算条件

 

1.3 并行计算层次

 二、并行计算机体系结构

弗林经典分类法（ 1966 年）： 从 指令流 和 数据流 两个维度区分多处理器计算机体系结构。

SISD是标准意义上的串行机，具有如下特点：

1 ）单指令：在每一个时钟周期内， CPU 只能执行一个指令流；

2 ）单数据：在每一个时钟周期内输入设备只能输入一个数据流；

3 ）执行结果是确定的。这是最古老的一种计算机类型。

SIMD属于一种类型的并行计算机，具有如下特点：

1 ）单指令：所有处理单元在任何一个时钟周期内都执行同一条指令；

2 ）多数据：每个处理单元可以处理不同的数据元素；

3 ）非常适合于处理高度有序的任务例如图形 图像处理；

4 ）同步（锁步）及确定性执行 。

MISD属于一种类型的并行计算机，具有如下特点：

1 ）多指令：不同的处理单元可以独立地执行不同的指令流；

2 ）单数据：不同的处理单元接收的是同一单数据流。这种架构理论上是有的，但是工业实践中这种机型非常少。

MIMD属于最常见的一种类型的并行计算机，具有如下特点：

1 ）多指令：不同的处理器可以在同一时刻处理不同的指令流；

2 ）多数据：不同的处理器可以在同一时刻处理不同的数据；

3 ）执行可以是同步的也可以是异步的，可以是确定性的，也可以是不确定性的。 这是目前主流的计算机架构类型 ，目前的超级计算机、并行计算机集群系统网格，多处理器计算机，多核计算机等都属于这种类型。 

用于科学计算的主流高性能并行计算机系统结构通常可以分成以下5 类：

并行向量处理机（PVP）
对称式共享存储器多处理机（SMP）
分布式共享存储器多处理机（DSM）
大规模并行处理机（MPP）
集群计算机（Cluster ）

 五种结构特性一览表

属性	PVP	SMP	MPP	DSM	Cluster
结构类型	MIMD	MIMD	MIMD	MIMD	MIMD
处理器类型	专用定制	商用	商用	商用	商用
互联网络	定制交叉开关	总线、交叉开关	定制网络	定制网络	商用网络
通讯机制	共享变量	共享变量	消息传递	共享变量	消息传递
地址空间	单地址空间	单地址空间	多地址空间	单地址空间	多地址空间
系统存储器	集中共享	集中共享	分布非共享	分布共享	分布非共享
访存模型	UMA	UMA	NORMA	NUMA	NORMA

SMP、 MPP 、 DSM 和 cluster 并行结构渐趋一致。
大量的节点通过高速网络互连起来
节点遵循Shell 结构：用专门定制的 Shell 电路将商用微处理器和节点的其它部分（包括板级 Cache 、 局存、 NIC 和 DISK 连接起来。优点是CPU 升级只需要更换 Shell 。

 2.1 并行计算访存模型UMA

UMA（Uniform Memory Access）模型是均匀存储访问模型的简称。其特点是：

物理存储器被所有处理器均匀共享；

所有处理器访问任何存储字取相同的时间；

每台处理器可带私有高速缓存；

外围设备也可以一定形式共享。 

 

2.2并行计算访存模型NUMA 

 

NUMA(Nonuniform Memory Access)模型是非均匀存储访问模型的简称。特点是：

被共享的存储器在物理上是分布在所有的处理器中的，其所有本地存储器的集合就组成了全局地址空间；

处理器访问存储器的时间是不一样的；访问本地存储器LM或群内共享存储器CSM较快，而访问外地的存储器或全局共享存储器GSM较慢(此即非均匀存储访问名称的由来)；

每台处理器照例可带私有高速缓存，外设也可以某种形式共享。

 

2.3 并行计算访存模型COMA

COMA(Cache-Only Memory Access)模型是全高速缓存存储访问的简称。其特点是：

各处理器节点中没有存储层次结构，全部高速缓存组成了全局地址空间；

利用分布的高速缓存目录D进行远程高速缓存的访问;

COMA中的高速缓存容量一般都大于2级高速缓存容量；

使用COMA时，数据开始时可任意分配，因为在运行时它最终会被迁移到要用到它们的地方。

 

2.4 并行计算访存模型CC-NUMA

CC-NUMA（Coherent-Cache Nonuniform Memory Access）模型是高速缓存一致性非均匀存储访问模型的简称。其特点是：

大多数使用基于目录的高速缓存一致性协议；

保留SMP结构易于编程的优点，也改善常规SMP的可扩放性；

CC-NUMA实际上是一个分布共享存储的DSM多处理机系统；

它最显著的优点是程序员无需明确地在节点上分配数据，系统的硬件和软件开始时自动在各节点分配数据，在运行期间，高速缓存一致性硬件会自动地将数据迁移至要用到它的地方。

 

  2.5 并行计算访存模型NORMA

NORMA（No-Remote Memory Access）模型是非远程存储访问模型的简称。NORMA的特点是：

所有存储器都是私有的；

绝大数NUMA都不支持远程存储器的访问

在DSM中，NORMA就消失了。

 

2.6 构筑并行机系统的不同存储结构

 

三、并行程序设计基础 

3.1 并行程序设计模型

隐式并行（Implicit Parallel）
编写串行程序，通过编译器和运行支持系统将串行程序自动并行化
特点：语义简单，可移植性好，易于调试和验证
缺点：细粒度并行，效率很低

数据并行（Data Parallel）
SIMD（单指令流多数据流），同一操作同时作用到一组数据上
特点：单一地址空间，编程简单，松散同步，隐式交互，隐式数据分配
缺点：并行粒度局限于数据级并行，粒度小
典型代表：Fortran 90 HPF

共享变量（Shared Variable）
特点：松散同步，多线程（SPMD MPMD）
单一地址空间，显式同步，隐式通信，隐式数据分布
典型代表：OpenMP Pthreads

消息传递（Message Passing）
特点：异步并行，多线程，多地址空间，
显式同步，显式通信，显式数据映射和负载分配
典型代表：MPI PVM

3.2 并行程序设计原则

• 与体系结构相结合
• 具有可扩展性
• 粗粒度
• 减少通信
• 优化性能

粒度是指各个线程可以独立并行执行的任务的大小，是一个相对的概念，与并行度和并行机相关。一般可理解为：

细粒度：基于向量和循环系级并行
中粒度：较大的循环级并行
大粒度：任务级并行（如：区域分解）