高性能计算（2）——万丈高楼平地起

存储方式

从物理划分上 共享内存和分布式内存是两种基本的并行计算机存储方式 除此之外 分布式共享内存也是一种越来越重要的并行计算机存储方式

指令和数据

• [小粒度]根据一个并行计算机能够同时执行的指令与处理数据的多少 可以把并行计算机分为 SIMD Single-Instruction Multiple-Data 单指令多数据并行计算机和MIMD Multiple-Instruction Multiple-Data 多指令多数据并行计算机
• [大粒度]按同时执行的程序和数据的不同 又提出了SPMD Single-Program Multuple-Data 单程序多数据并行计算机和MPMD Multiple-ProgramMultiple-Data 多程序多数据并行计算机

根据指令的同时执行和数据的同时执行，计算机系统可以分成以下四类：

• 单处理器，单数据 (SISD)
• 单处理器，多数据 (SIMD)
• 多处理器，单数据 (MISD)
• 多处理器，多数据 (MIMD)

SISD

单处理器单数据就是“单CPU的机器”，它在单一的数据流上执行指令。在SISD中，指令被顺序地执行。

对于每一个“CPU时钟”，CPU按照下面的顺序执行：

• Fetch: CPU 从一片内存区域中（寄存器）获得数据和指令
• Decode: CPU对指令进行解码
• Execute: 该执行在数据上执行，将结果保存在另一个寄存器中
  

这种架构（冯·诺依曼体系）的主要元素有以下：

• 中心内存单元：存储指令和数据
• CPU：用于从内存单元获得指令/数据，对指令解码并顺序执行它们
• I/O系统：程序的输入和输出流

传统的单处理器计算机都是经典的SISD系统。下图表述了CPU在Fetch、Decode、Execute的步骤中分别用到了哪些单元：

MISD

这种模型中，有n个处理器，每一个都有自己的控制单元，共享同一个内存单元。在每一个CPU时钟中，从内存获得的数据会被所有的处理器同时处理，每一个处理器按照自己的控制单元发送的指令处理。在这种情况下，并行实际上是指令层面的并行，多个指令在相同的数据上操作。能够合理利用这种架构的问题模型比较特殊，例如数据加密等。因此，MISD在现实中并没有很多用武之地，更多的是作为一个抽象模型的存在。

SIMD

SIMD计算机包括多个独立的处理器，每一个都有自己的局部内存，可以用来存储数据。所有的处理器都在单一指令流下工作；具体说，就是有n个数据流，每个处理器处理一个。所有的处理器同时处理每一步，在不同的数据上执行相同的指令。

很多问题都可以用SIMD计算机的架构来解决。这种架构另一个有趣的特性是，这种架构的算法非常好设计，分析和实现。限制是，只有可以被分解成很多个小问题（小问题之间要独立，可以不分先后顺序被相同的指令执行）的问题才可以用这种架构解决。很多超级计算机就是使用这架构设计出来的。例如Connection Machine（1985年的 Thinking Machine)和MPP（NASA-1983）.我们在第六章 GPU Python编程中会接触到高级的现代图形处理器（GPU），这种处理器就是内置了很多个SIMD处理单元，使这种架构在今天应用非常广泛。

MIMD

在费林分类中，这种计算机是最广泛使用、也是最强大的一个种类。这种架构有n个处理器，n个指令流，n个数据流。每一个处理器都有自己的控制单元和局部内存，让MIMD架构比SIMD架构的计算能力更强。每一个处理器都在独立的控制单元分配的指令流下工作；因此，处理器可以在不同的数据上运行不同的程序，这样可以解决完全不同的子问题甚至是单一的大问题。在MIMD中，架构是通过线程或进程层面的并行来实现的，这也意味着处理器一般是异步工作的。这种类型的计算机通常用来解决那些没有统一结构、无法用SIMD来解决的问题。如今，很多计算机都应用了这中间架构，例如超级计算机，计算机网络等。然而，有一个问题不得不考虑：异步的算法非常难设计、分析和实现。

并发和并行

并行类型

几种并行区分

程序、线程、进程和超线程

• 程序程序是一组指令的有序集合。它本身没有任何运行的含义，只是存在于计算机系统的硬盘等存储空间中一个静态的实体文件。比如Linux系统下的binary excutable，windows系统下的exe
• 进程进程是处于动态条件下由操作系统维护的系统资源管理实体。进程具有自己的生命周期， 反映了一个程序在一定的数据集上运行的全部动态过程。需要加载到内存中，点开一个exe就是开启了一个进程
• 线程。线程则是进程的一个实体，是比进程更小的能独立运行的基本单位，是被系统调度和分配的基本单元。线程自身基本上不拥有系统资源，只拥有一点在运行中必不可少的资源 （如程序计数器、一组寄存器和调用堆栈）， 但它与同属一个进程的其他线程共享所属进程所拥有的全部资源，同一个进程的多个线程可以并发执行，从而提高了系统资源的利用率
• 超线程超线程技术就是利用特殊的硬件指令，把两个逻辑内核模拟成两个物理芯片，让单颗CPU都能进行线程级并行计算，进而兼容多线程操作系统和软件。一般一个CPU对应一个线程，通过超线程可以达到比如8核16线程

老生常谈，线程和进程的区别和联系：

1. 一个程序的执行至少有一个进程，一个进程至少包含一个线程（主线程）。
2. 线程的划分尺度小于进程，所以多线程程序并发性更高。
3. 进程是系统进行资源分配和调度的一个独立单位，线程是CPU调度和分派的基本单位。同一进程内允许多个线程共享其资源。
4. 进程拥有独立的内存单元，即进程之间相互独立；同一进程内多个线程共享内存。因此，线程间能通过读写操作对它们都可见的内存进行通信，而进程间的相互通信则需要借助于消息的传递。
5. 每个线程都有一个程序运行的入口，顺序执行序列和程序运行的出口，但线程不能单独执行，必须依存于进程中，由进程控制多个线程的执行
6. 进程比线程拥有更多的相应状态，所以创建或销毁进程的开销要比创建或销毁线程的开销大得多。因此，进程存在的时间长，而线程则随着计算的进行不断地动态地派生和缩并。
7. 一个线程可以创建和撤销另一个线程。而且同一进程中的多个线程共享所属进程所拥有的全部资源；同时进程之间也可以并行执行，从而更好地改善了系统资源的利用率。

线程绑定

计算机系统是由一个或多个物理处理器和内存组成，运行的程序会将内存分为两个部分，一部分是共享变量使用的存储区域， 另一部分供各线程的私有变量使用的存储区域。线程绑定是将线程绑定在固定的处理器上， 从而在线程与处理器之间建立一对一的映射关系。如果不进行线程绑定，线程可能在不同的时间片运行在不同的处理器上。我们知道，每个处理器是有自己的多级缓存的，如果线程切来切去，那么cache命中率肯定不高，程序性能也会受到影响。通过线程绑定，程序能够获得更高的cache利用率从而提高程序性能。c++中如何进行线程绑定可以参考https://www.cnblogs.com/wenqiang/p/6049978.html

并行算法评价

理论上来说，n个相同的cpu理论上能提供n倍的计算能力。

但是在实际过程中，并行开销会导致总的执行时间无法线性地减少。这些开销分别为：

1. 线程的建立和销毁、 线程和线程之间的通信、 线程间的同步等因素造成的开销。
2. 存在不能并行化的计算代码，造成计算由单个线程完成， 而其他线程则处于闲置状态。
3. 为争夺共享资源而引起的竞争造成的开销。
4. 由于各cpu工作负载分配的不均衡和内存带宽等因素的限制，一个或多个线程由于缺少工作或因为等待特定事件的发生无法继续执行而处于空闲状态。

并行加速比（加速比）

加速比的定义是顺序程序执行时间除以计算同一结果的并行程序的执行时间

$$R_s = \frac{t_s}{t_p}$$

式中， $t_s$为一颗CPU程序完成该任务所需串行执行时间； $t_p$为n颗CPU并行执行完成该任务所需时间。由于串行执行时间 $t_s$为n颗CPU并行执行完成该 和并行执行时间 $t_p$有多种定义方式。 这样就产生了五种不同的加速比的定义，即相对加速比、实际加速比、绝对加速比、渐近实际加速比和渐近相对加速比。

并行效率（效率）

在实际应用中，影响并行加速比的因素主要是串行计算、并行计算和并行开销三方面。一般情况下， 并行加速比小于CPU的数量。但是，有时会出现一种奇怪的现象，即并行程序能以串行程序快n倍的速度运行，称为超线性加速比。产生超线性加速的原因在于CPU访问的数据都驻留在各自的高速缓存Cache中， 而高速缓存的容量比内存要小， 但读写速度却远高于内存。
衡量并行算法的另一个主要标准是并行效率，它表示的是多颗CPU在进行并行计算时单颗CPU的平均加速比。

$$R_p = \frac{R_s}{n}$$

理想并行效率为1表明全部CPU都在满负荷工作。通常情况下，并行效率会小于1， 且随CPU数量的增加而减小。

伸缩性

伸缩性用于度量并行机器高效运行的能力，代表跟处理器数量成比例的计算能力 (执行速度)。如果问题的规模和处理器的数量同时增加，性能不会下降。

阿姆德尔定律 (Ahmdal’s law)

阿姆德尔定律广泛使用于处理器设计和并行算法设计。它指出程序能达到的最大加速比被程序的串行部分限制。$S=1/(1-p) $中 $1-p$ 指程序的串行部分。它的意思是，例如一个程序90%的代码都是并行的，但仍存在10%的串行代码，那么系统中即使由无限个处理器能达到的最大加速比仍为9。

古斯塔夫森定律 (Gustafson’s law)

古斯塔夫森定律在考虑下面的情况之后得出的：

• 当问题的规模增大时，程序的串行部分保持不变。
• 当增加处理器的数量时，每个处理器执行的任务仍然相同。

古斯塔夫森定律指出了加速比 $S(P)=P-\alpha (P-1)$， $P$ 为处理器的数量， $S$ 为加速比， $\alpha$ 是并行处理器中的非并行的部分。作为对比，阿姆德尔定律将单个处理器的执行时间作为定量跟并行执行时间相比。因此阿姆德尔定律是基于固定的问题规模提出的，它假设程序的整体工作量不会随着机器规模 (也就是处理器数量) 而改变。古斯塔夫森定律补充了阿姆德尔定律没有考虑解决问题所需的资源总量的不足。古斯塔夫森定律解决了这个问题， 它表明设定并行解决方案所允许耗费的时间的最佳方式是考虑所有的计算资源和基于这类信息。