并行计算简介

忘是亡心i 2023-06-20 11:59 37阅读 0赞

1 什么是并行计算？

串行计算： 传统的软件通常被设计成为串行计算模式，具有如下特点：

*   *  一个问题被分解成为一系列离散的指令；
     *  这些指令被顺次执行；
     *  所有指令均在一个处理器上被执行；

在任何时刻，最多只有一个指令能够被执行。  
![这里写图片描述][aHR0cHM6Ly9jb21wdXRpbmcubGxubC5nb3YvdHV0b3JpYWxzL3BhcmFsbGVsX2NvbXAvaW1hZ2VzL3NlcmlhbFByb2JsZW0uZ2lm]

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

*   *  一个问题被分解成为一系列可以并发执行的离散部分；
     *  每个部分可以进一步被分解成为一系列离散指令；
     *  来自每个部分的指令可以在不同的处理器上被同时执行；

需要一个总体的控制/协作机制来负责对不同部分的执行情况进行调度。  
![这里写图片描述][aHR0cHM6Ly9jb21wdXRpbmcubGxubC5nb3YvdHV0b3JpYWxzL3BhcmFsbGVsX2NvbXAvaW1hZ2VzL3BhcmFsbGVsUHJvYmxlbS5naWY]

这里的 **计算问题** 需要具有如下特点：

*  能够被分解成为并发执行离散片段；
 *  不同的离散片段能够被在任意时刻执行；
 *  采用多个计算资源的花费时间要小于采用单个计算资源所花费的时间。

这里的 **计算资源** 通常包括：

*  具有多处理器/多核(multiple processors/cores)的计算机；
 *  任意数量的被连接在一起的计算机。

并行计算机：  
通常来讲，从 **硬件** 的角度来讲，当前所有的单机都可以被认为是并行的：

*  多功能单元（L1缓存，L2缓存，分支，预取，解码，浮点数，图形处理器，整数等）
 *  多执行单元/内核
 *  多硬件线程  
      
    IBM BG/Q Compute Chip with 18 cores (PU) and 16 L2 Cache units (L2)

通过 **网络** 连接起来的多个单机也可以形成更大的并行计算机集群:  
![这里写图片描述][aHR0cHM6Ly9jb21wdXRpbmcubGxubC5nb3YvdHV0b3JpYWxzL3BhcmFsbGVsX2NvbXAvaW1hZ2VzL25vZGVzTmV0d29yay5naWY]

例如，下面的图解就显示了一个典型的LLNL并行计算机集群：

*   *   *  每个计算结点就是一个多处理器的并行计算机；
         *  多个计算结点用无限宽带网络连接起来；

某些特殊的结点（通常也是多处理器单机）被用来执行特定的任务。

###  ###

### 2 概念和术语 ###

2.1 冯诺依曼体系结构

以匈牙利数学家约翰·冯诺依曼命名的这一计算机体系结构，出现在他1945年发表的一篇论文中。这也通常被称为“存储程序计算机”——程序指令和数据都被保存在存储器中，这与早期通过“硬接线”编程的计算机不同。从此以后，所有的计算机走遵从这一基本架构：  
![这里写图片描述][aHR0cHM6Ly9jb21wdXRpbmcubGxubC5nb3YvdHV0b3JpYWxzL3BhcmFsbGVsX2NvbXAvaW1hZ2VzL3Zvbk5ldW1hbm4xLmdpZg]![这里写图片描述][format_png]  
\- 四个组成部分：1）内存；2）控制器；3）处理器；4）输入输出。  
\- 读写操作：支持随机存储的内存用来同时保存程序指令和数据：1）程序指令用来指导计算机操作；2）数据是程序用来操作的对象。  
\- 控制器：从内存中读取指令或者数据，对这些指令进行解码并且顺序执行这些指令。  
\- 处理器：提供基本的算术和逻辑操作。  
\- 输入输出设备：是人机交互的接口。

那么冯诺依曼体系结构和并行计算有什么关系呢？答案是：并行计算机仍然遵从这一基本架构，只是处理单元多于一个而已，其它的基本架构完全保持不变。

2.2 弗林的经典分类

有不同的方法对并行计算机进行分类（具体例子可参见[并行计算分类][Link 1]）。

一种被广泛采用的分类被称为弗林经典分类，诞生于1966年。弗林分类法从指令流和数据流两个维度区分多处理器计算机体系结构。每个维度有且仅有两个状态：单个或者多个。

下面个矩阵定义了弗林分类的四个可能状态：  
![这里写图片描述][aHR0cHM6Ly9jb21wdXRpbmcubGxubC5nb3YvdHV0b3JpYWxzL3BhcmFsbGVsX2NvbXAvaW1hZ2VzL2ZseW5uc1RheG9ub215LmdpZg]

单指令单数据(SISD)： SISD是标准意义上的串行机，具有如下特点：1）单指令：在每一个时钟周期内，CPU只能执行一个指令流；2）单数据：在每一个时钟周期内，输入设备只能输入一个数据流；3）执行结果是确定的。这是最古老的一种计算机类型。  
![这里写图片描述][aHR0cHM6Ly9jb21wdXRpbmcubGxubC5nb3YvdHV0b3JpYWxzL3BhcmFsbGVsX2NvbXAvaW1hZ2VzL3Npc2QyLmdpZg]

单指令多数据(SIMD)： SIMD属于一种类型的并行计算机，具有如下特点：1）单指令：所有处理单元在任何一个时钟周期内都执行同一条指令；2）多数据：每个处理单元可以处理不同的数据元素；3）非常适合于处理高度有序的任务，例如图形/图像处理；4）同步（锁步）及确定性执行；5）两个主要类型：处理器阵列和矢量管道。  
![这里写图片描述][aHR0cHM6Ly9jb21wdXRpbmcubGxubC5nb3YvdHV0b3JpYWxzL3BhcmFsbGVsX2NvbXAvaW1hZ2VzL3NpbWQzLmdpZg]

![这里写图片描述][aHR0cHM6Ly9jb21wdXRpbmcubGxubC5nb3YvdHV0b3JpYWxzL3BhcmFsbGVsX2NvbXAvaW1hZ2VzL3NpbWQuZ2lm]

![这里写图片描述][aHR0cHM6Ly9jb21wdXRpbmcubGxubC5nb3YvdHV0b3JpYWxzL3BhcmFsbGVsX2NvbXAvaW1hZ2VzL3NpbWQyLmdpZg]

\*\*多指令单数据(MISD)：\*\*MISD属于一种类型的并行计算机，具有如下特点：1）多指令：不同的处理单元可以独立地执行不同的指令流；2）单数据：不同的处理单元接收的是同一单数据流。这种架构理论上是有的，但是工业实践中这种机型非常少。

多指令多数据(MIMD)： MIMD属于最常见的一种类型的并行计算机，具有如下特点：1）多指令：不同的处理器可以在同一时刻处理不同的指令流；2）多数据：不同的处理器可以在同一时刻处理不同的数据；3）执行可以是同步的，也可以是异步的，可以是确定性的，也可以是不确定性的。这是目前主流的计算机架构类型，目前的超级计算机、并行计算机集群系统，网格，多处理器计算机，多核计算机等都属于这种类型。值得注意的是，许多MIMD类型的架构中实际也可能包括SIMD的子架构。  
![这里写图片描述][aHR0cHM6Ly9jb21wdXRpbmcubGxubC5nb3YvdHV0b3JpYWxzL3BhcmFsbGVsX2NvbXAvaW1hZ2VzL21pbWQyLmdpZg]

### 3 并行计算机的内存架构 ###

3.1 共享内存

一般特征： 共享内存的并行计算机虽然也分很多种，但是通常而言，它们都可以让所有处理器以全局寻址的方式访问所有的内存空间。多个处理器可以独立地操作，但是它们共享同一片内存。一个处理器对内存地址的改变对其它处理器来说是可见的。根据内存访问时间，可以将已有的共享内存机器分为统一内存存取和非统一内存存取两种类型。

统一内存存取(Uniform Memory Access)： 目前更多地被称为*对称多处理器机器(Symmetric Multiprocessor (SMP))*，每个处理器都是相同的，并且其对内存的存取和存取之间都是无差别的。有时候也会被称为CC-UMA (Cache coherent - UMA)。缓存想干意味着如果一个处理器更新共享内存中的位置，则所有其它处理器都会了解该更新。缓存一致性是在硬件级别上实现的。

![这里写图片描述][aHR0cHM6Ly9jb21wdXRpbmcubGxubC5nb3YvdHV0b3JpYWxzL3BhcmFsbGVsX2NvbXAvaW1hZ2VzL3NoYXJlZF9tZW0uZ2lm]

非统一内存存取(Non-Uniform Memory Access)： 通常由两个或者多个物理上相连的SMP。一个SMP可以存取其它SMP上的内存。不是所有处理器对所有内存都具有相同的存取或者存取时间。通过连接而进行内存存取速度会更慢一些。如果缓存相缓存想干的特性在这里仍然被保持，那么也可以被称为CC-NUMA。

![这里写图片描述][aHR0cHM6Ly9jb21wdXRpbmcubGxubC5nb3YvdHV0b3JpYWxzL3BhcmFsbGVsX2NvbXAvaW1hZ2VzL251bWEuZ2lm]

优点：全局地址空间提供了一种用户友好的编程方式，并且由于内存与CPU的阶级程度，使得任务之间的数据共享既快速又统一。

缺点：最大的缺点是内存和CPU之间缺少较好的可扩展性。增加更多的CPU意味着更加共享内存和缓存想干系统上的存取流量，从而几何级别地增加缓存/内存管理的工作量。同时也增加了程序员的责任，因为他需要确保全局内存“正确”的访问以及同步。

3.2 分布式内存

一般概念： 分布式内存架构也可以分为很多种，但是它们仍然有一些共同特征。分布式内存结构需要通讯网络，将不同的内存连接起来。一般而言，处理器会有它们所对应的内存。一个处理器所对应的内存地址不会映射到其它处理器上，所以在这种分布式内存架构中，不存在各个处理器所共享的全局内存地址。  
![这里写图片描述][aHR0cHM6Ly9jb21wdXRpbmcubGxubC5nb3YvdHV0b3JpYWxzL3BhcmFsbGVsX2NvbXAvaW1hZ2VzL2Rpc3RyaWJ1dGVkX21lbS5naWY]

由于每个处理器具有它所对应的局部内存，所以它们可以独立进行操作。一个本地内存上所发生的变化并不会被其它处理器所知晓。因此，缓存想干的概念在分布式内存架构中并不存在。

如果一个处理器需要对其它处理器上的数据进行存取，那么往往程序员需要明确地定义数据通讯的时间和方式，任务之间的同步因此就成为程序员的职责。尽管分布式内存架构中用于数据传输的网络结构可以像以太网一样简单，但在实践中它们的变化往往也很大。

优点： 1）内存可以随着处理器的数量而扩展，增加处理器的数量的同时，内存的大小也在成比例地增加；2）每个处理器可以快速地访问自己的内存而不会受到干扰，并且没有维护全局告诉缓存一致性所带来的开销；3）成本效益：可以使用现有的处理器和网络。

缺点： 1）程序员需要负责处理器之间数据通讯相关的许多细节；2）将基于全局内存的现有数据结构映射到该分布式内存组织可能会存在困难；3）非均匀的内存访问时间——驻留在远程结点上的数据比本地结点上的数据需要长的多的访问时间。

### 4 并行计算模型 ###

......

### 5 并行程序设计 ###

......

参阅：[https://blog.csdn.net/magicbean2/article/details/75174859][https_blog.csdn.net_magicbean2_article_details_75174859]

[aHR0cHM6Ly9jb21wdXRpbmcubGxubC5nb3YvdHV0b3JpYWxzL3BhcmFsbGVsX2NvbXAvaW1hZ2VzL3NlcmlhbFByb2JsZW0uZ2lm]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9jb21wdXRpbmcubGxubC5nb3YvdHV0b3JpYWxzL3BhcmFsbGVsX2NvbXAvaW1hZ2VzL3NlcmlhbFByb2JsZW0uZ2lm
[aHR0cHM6Ly9jb21wdXRpbmcubGxubC5nb3YvdHV0b3JpYWxzL3BhcmFsbGVsX2NvbXAvaW1hZ2VzL3BhcmFsbGVsUHJvYmxlbS5naWY]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9jb21wdXRpbmcubGxubC5nb3YvdHV0b3JpYWxzL3BhcmFsbGVsX2NvbXAvaW1hZ2VzL3BhcmFsbGVsUHJvYmxlbS5naWY
[aHR0cHM6Ly9jb21wdXRpbmcubGxubC5nb3YvdHV0b3JpYWxzL3BhcmFsbGVsX2NvbXAvaW1hZ2VzL25vZGVzTmV0d29yay5naWY]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9jb21wdXRpbmcubGxubC5nb3YvdHV0b3JpYWxzL3BhcmFsbGVsX2NvbXAvaW1hZ2VzL25vZGVzTmV0d29yay5naWY
[aHR0cHM6Ly9jb21wdXRpbmcubGxubC5nb3YvdHV0b3JpYWxzL3BhcmFsbGVsX2NvbXAvaW1hZ2VzL3Zvbk5ldW1hbm4xLmdpZg]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9jb21wdXRpbmcubGxubC5nb3YvdHV0b3JpYWxzL3BhcmFsbGVsX2NvbXAvaW1hZ2VzL3Zvbk5ldW1hbm4xLmdpZg
[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9jb21wdXRpbmcubGxubC5nb3YvdHV0b3JpYWxzL3BhcmFsbGVsX2NvbXAvaW1hZ2VzL3Zvbk5ldW1hbm4yLmpwZw?x-oss-process=image/format,png
[Link 1]: https://computing.llnl.gov/tutorials/parallel_comp/parallelClassifications.pdf
[aHR0cHM6Ly9jb21wdXRpbmcubGxubC5nb3YvdHV0b3JpYWxzL3BhcmFsbGVsX2NvbXAvaW1hZ2VzL2ZseW5uc1RheG9ub215LmdpZg]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9jb21wdXRpbmcubGxubC5nb3YvdHV0b3JpYWxzL3BhcmFsbGVsX2NvbXAvaW1hZ2VzL2ZseW5uc1RheG9ub215LmdpZg
[aHR0cHM6Ly9jb21wdXRpbmcubGxubC5nb3YvdHV0b3JpYWxzL3BhcmFsbGVsX2NvbXAvaW1hZ2VzL3Npc2QyLmdpZg]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9jb21wdXRpbmcubGxubC5nb3YvdHV0b3JpYWxzL3BhcmFsbGVsX2NvbXAvaW1hZ2VzL3Npc2QyLmdpZg
[aHR0cHM6Ly9jb21wdXRpbmcubGxubC5nb3YvdHV0b3JpYWxzL3BhcmFsbGVsX2NvbXAvaW1hZ2VzL3NpbWQzLmdpZg]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9jb21wdXRpbmcubGxubC5nb3YvdHV0b3JpYWxzL3BhcmFsbGVsX2NvbXAvaW1hZ2VzL3NpbWQzLmdpZg
[aHR0cHM6Ly9jb21wdXRpbmcubGxubC5nb3YvdHV0b3JpYWxzL3BhcmFsbGVsX2NvbXAvaW1hZ2VzL3NpbWQuZ2lm]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9jb21wdXRpbmcubGxubC5nb3YvdHV0b3JpYWxzL3BhcmFsbGVsX2NvbXAvaW1hZ2VzL3NpbWQuZ2lm
[aHR0cHM6Ly9jb21wdXRpbmcubGxubC5nb3YvdHV0b3JpYWxzL3BhcmFsbGVsX2NvbXAvaW1hZ2VzL3NpbWQyLmdpZg]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9jb21wdXRpbmcubGxubC5nb3YvdHV0b3JpYWxzL3BhcmFsbGVsX2NvbXAvaW1hZ2VzL3NpbWQyLmdpZg
[aHR0cHM6Ly9jb21wdXRpbmcubGxubC5nb3YvdHV0b3JpYWxzL3BhcmFsbGVsX2NvbXAvaW1hZ2VzL21pbWQyLmdpZg]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9jb21wdXRpbmcubGxubC5nb3YvdHV0b3JpYWxzL3BhcmFsbGVsX2NvbXAvaW1hZ2VzL21pbWQyLmdpZg
[aHR0cHM6Ly9jb21wdXRpbmcubGxubC5nb3YvdHV0b3JpYWxzL3BhcmFsbGVsX2NvbXAvaW1hZ2VzL3NoYXJlZF9tZW0uZ2lm]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9jb21wdXRpbmcubGxubC5nb3YvdHV0b3JpYWxzL3BhcmFsbGVsX2NvbXAvaW1hZ2VzL3NoYXJlZF9tZW0uZ2lm
[aHR0cHM6Ly9jb21wdXRpbmcubGxubC5nb3YvdHV0b3JpYWxzL3BhcmFsbGVsX2NvbXAvaW1hZ2VzL251bWEuZ2lm]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9jb21wdXRpbmcubGxubC5nb3YvdHV0b3JpYWxzL3BhcmFsbGVsX2NvbXAvaW1hZ2VzL251bWEuZ2lm
[aHR0cHM6Ly9jb21wdXRpbmcubGxubC5nb3YvdHV0b3JpYWxzL3BhcmFsbGVsX2NvbXAvaW1hZ2VzL2Rpc3RyaWJ1dGVkX21lbS5naWY]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9jb21wdXRpbmcubGxubC5nb3YvdHV0b3JpYWxzL3BhcmFsbGVsX2NvbXAvaW1hZ2VzL2Rpc3RyaWJ1dGVkX21lbS5naWY
[https_blog.csdn.net_magicbean2_article_details_75174859]: https://blog.csdn.net/magicbean2/article/details/75174859