华为云社区《高性能计算（2）——万丈高楼平地起计算

摘要：在实际应用中，影响并行加速的因素主要是串行计算、并行计算和并行开销。

本文分享自华为云社区“高性能计算（2）-来自万楼平地”），作者：我是个大西瓜。

存储方式

在物理划分方面，共享内存和分布式内存是两种基本的并行计算机存储方式。此外，分布式共享内存也是一种日益重要的并行计算机存储方式。

指令和数据

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

SISD

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

对于每个“CPU时钟”，CPU按以下顺序执行：

这个架构（冯诺依曼系统）的主要元素如下：

传统的单处理器计算机是经典的 SISD 系统。下图显示了在 Fetch、Decode 和 Execute 步骤中 CPU 使用了哪些单元：

误读

在这个模型中，有 n 个处理器，每个处理器都有自己的控制单元，共享同一个内存单元。在每个 CPU 时钟内，从内存中获取的数据会被所有的处理器同时处理，每个处理器都会根据自己的控制单元发出的指令进行处理。在这种情况下，并行性实际上是指令级并行性，其中多条指令对同一数据进行操作。可以合理利用这种架构的问题模型是特殊的，例如数据加密。因此，MISD在现实中并没有太多用处，更多是作为一种抽象模型存在。

SIMD

SIMD 计算机由多个独立的处理器组成，每个处理器都有自己的本地内存，可用于存储数据。所有处理器都在单一指令流下运行；具体来说，有n个数据流，每个处理器一个。所有处理器同时处理每个步骤，对不同的数据执行相同的指令。

SIMD 计算机的体系结构可以解决许多问题。该架构的另一个有趣特性是该架构的算法设计、分析和实现都非常好。限制是只有可以分解成许多小问题的问题（小问题必须是独立的，并且可以由相同的指令以不特定的顺序执行）才能用这种架构来解决。许多超级计算机都是使用这种架构设计的。例如 Connection Machine（Thinking Machine，1985 年）和 MPP（NASA-1983）。在第 6 章 GPU Python 编程中，我们将接触到先进的现代图形处理单元（GPU），这些单元内置了许多需要 SIMD 处理单元，使得这种架构在今天得到了非常广泛的应用。

MIMD

这种类型的计算机是费林分类中使用最广泛、功能最强大的一类。该架构具有 n 个处理器、n 个指令流和 n 个数据流。每个处理器都有自己的控制单元和本地存储器，这使得 MIMD 架构比 SIMD 架构的计算能力更强。每个处理器在独立控制单元分配的指令流下运行；因此，处理器可以在不同的数据上运行不同的程序，从而可以解决完全不同的子问题甚至是单个大问题。在 MIMD 中，架构是通过线程或进程级别的并行实现的，这也意味着处理器通常异步工作。这类计算机常用于解决结构不统一、不能用 SIMD 解决的问题。今天，许多计算机都使用这种中间架构，例如超级计算机、计算机网络等。但是，需要考虑一个问题：异步算法很难设计、分析和实现。

并发和并行

平行型

几个平行的区别

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

线程和进程的区别和联系：

一个程序的执行至少有一个进程，一个进程至少包含一个线程（主线程）。线程的划分规模小于进程的划分规模，因此多线程程序具有更高的并发性。进程是系统中独立的资源分配和调度单位，线程是CPU调度和分配的基本单位。允许同一进程内的多个线程共享它们的资源。进程有独立的内存单元，即进程之间是相互独立的；同一进程内的多个线程共享内存。因此，线程可以通过读写操作与它们可见的内存进行通信，而进程之间的通信需要依靠消息传递。每个线程都有一个程序操作的入口、一个顺序执行序列和一个程序操作的出口，但线程不能独立执行，必须依赖于进程。该进程控制多个线程的执行。进程比线程有更多的对应状态。所以创建或销毁一个进程比创建或销毁一个线程要昂贵得多。结果，进程存在很长时间，而线程随着计算的进行继续动态分叉和收缩。一个线程可以创建和撤销另一个线程。而且，同一进程中的多个线程共享该进程拥有的所有资源；同时，这些进程也可以并行执行，从而更好地提高系统资源的利用率。线程绑定

计算机系统由一个或多个物理处理器和内存组成。运行的程序会将内存分成两部分，一部分是共享变量使用的存储区，另一部分是各个线程区的私有变量使用的存储区。线程绑定就是将线程绑定到固定的处理器上，从而在线程和处理器之间建立一一对应的映射关系。如果没有线程绑定，线程可能会在不同的时间片上运行在不同的处理器上。我们知道每个处理器都有自己的多级缓存。如果切换线程，缓存命中率肯定不高，程序性能也会受到影响。通过线程绑定，程序可以获得更高的缓存利用率，提高程序性能。 c++中如何进行线程绑定可以参考

并行算法评估

理论上，n个相同的CPU理论上可以提供n倍的计算能力。

但实际上，并行开销会导致总执行时间不会线性减少。这些费用是：

线程的建立和销毁、线程间的通信、线程间的同步所带来的开销。存在无法并行化的计算代码，导致计算由单个线程完成，而其他线程处于空闲状态。由于争用共享资源而产生的开销。由于各个 CPU 的工作负载分布不均衡以及内存带宽等因素的限制，一个或多个线程由于工作不足或等待特定事件发生而无法继续执行而处于空闲状态。并行加速（speedup）

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

​公式中，t_sts​是CPU程序完成任务所需的串行执行时间； t_ptp​是 n 个 CPU 并行执行任务所需的时间。由于串行执行时间 t_sts​是由 n 个 CPU 并行执行完成的，而并行执行时间 t_ptp​有多种定义方式。由此产生了五种不同的加速比定义，即相对加速比、实际加速比、绝对加速比、渐近实际加速比和渐近相对加速比。

并行效率（efficiency）

在实际应用中，影响并行提速的因素主要是串行计算、并行计算和并行开销。通常，并行加速比 CPU 的数量少。但是，有时会出现一种奇怪的现象，即并行程序的运行速度比串行程序快 n 倍，称为超线性加速。超线性加速的原因是CPU访问的数据驻留在自己的缓存中，缓存的容量比内存小，但读写速度却比内存高很多.

衡量并行算法的另一个主要标准是并行效率，它表示多个 CPU 进行并行计算时单个 CPU 的平均加速比。

​理想的并行效率为 1 表示所有 CPU 都在满负荷工作。通常并行效率会小于1，并且会随着CPU数量的增加而降低。

可扩展性

可扩展性是衡量并行机器高效运行能力的指标，它表示与处理器数量成正比的计算能力（执行速度）。如果问题规模和处理器数量同时增加，则不会出现性能下降。

艾哈迈达定律

Amdel 定律广泛用于处理器设计和并行算法设计。它指出程序可以实现的最大加速受到程序的串行部分的限制。 $S=1/(1-p) $ 中的 1-p1-p 指的是程序的串行部分。这意味着，例如，如果一个程序中 90% 的代码是并行的，但仍有 10% 的串行代码，那么即使系统中的处理器数量不限，也可以实现的最大加速是还是 9。

古斯塔夫森定律

考虑以下因素后推导出古斯塔夫森定律：

古斯塔夫森定律指出加速比S(P)=P-alpha (P-1)S(P)=P-α(P-1), PP是处理数处理器中，SS是加速比，αα是并行处理器的非并行部分。为了比较，阿姆德尔定律将单个处理器的执行时间作为与并行执行时间的定量比较。因此，阿姆德尔定律是基于固定的问题大小，假设程序的整体工作量不随机器的大小（即处理器的数量）而变化。古斯塔夫森定律补充了阿姆德尔定律，并没有考虑需要什么解决问题 古斯塔夫森定律解决了这个问题，该定律指出，设置并行解决方案所允许的时间的最佳方法是考虑所有计算资源并以此类信息为基础。

点击关注，第一时间了解华为云新技术~