并发维度

并发维度

线程级并发

从 20 世纪 60 年代初期出现时间共享以来,计算机系统中就开始有了对并发执行的支持;传统意义上,这种并发执行只是模拟出来的,是通过使一台计算机在它正在执行的进程间快速切换的方式实现的,这种配置称为单处理器系统。从 20 世纪 80 年代开始,多处理器系统,即由单操作系统内核控制的多处理器组成的系统采用了多核处理器与超线程(HyperThreading)等技术允许我们实现真正的并行。多核处理器是将多个 CPU 集成到一个集成电路芯片上:

image

超线程,有时称为同时多线程(simultaneous multi-threading),是一项允许一个 CPU 执行多个控制流的技术。它涉及 CPU 某些硬件有多个备份,比如程序计数器和寄存器文件;而其他的硬件部分只有一份,比如执行浮点算术运算的单元。常规的处理器需要大约 20 000 个时钟周期做不同线程间的转换,而超线程的处理器可以在单个周期的基础上决定要执行哪一个线程。这使得 CPU 能够更好地利用它的处理资源。例如,假设一个线程必须等到某些数据被装载到高速缓存中,那 CPU 就可以继续去执行另一个线程。

指令级并发

在较低的抽象层次上,现代处理器可以同时执行多条指令的属性称为指令级并行。实每条指令从开始到结束需要长得多的时间,大约 20 个或者更多的周期,但是处理器使用了非常多的聪明技巧来同时处理多达 100 条的指令。在流水线中,将执行一条指令所需要的活动划分成不同的步骤,将处理器的硬件组织成一系列的阶段,每个阶段执行一个步骤。这些阶段可以并行地操作,用来处理不同指令的不同部分。我们会看到一个相当简单的硬件设计,它能够达到接近于一个时钟周期一条指令的执行速率。如果处理器可以达到比一个周期一条指令更快的执行速率,就称之为超标量(Super Scalar)处理器。

单指令、多数据

在最低层次上,许多现代处理器拥有特殊的硬件,允许一条指令产生多个可以并行执行的操作,这种方式称为单指令、多数据,即 SIMD 并行。例如,较新的 Intel 和 AMD 处理器都具有并行地对 4 对单精度浮点数(C 数据类型 float)做加法的指令。

Amdahl 定律

Amdahl 定律可以用来计算处理器平行运算之后效率提升的能力,其由 Gene Amdal 在 1967 年提出;它描述了在一个系统中,基于可并行化和串行化的组件各自所占的比重,程序通过获得额外的计算资源,理论上能够加速多少。任何程序或算法可以按照是否可以被并行化分为可以被并行化的部分 1 - B 与不可以被并行化的部分 B,那么根据 Amdahl 定律,不同的并行因子的情况下程序的总执行时间的变化如下所示:

如果 F 是必须串行化执行的比重,那么 Amdahl 定律告诉我们,在一个 N 处理器的机器中,我们最多可以加速:

当 N 无限增大趋近无穷时,speedup 的最大值无限趋近 1/F,这意味着一个程序中如果 50% 的处理都需要串行进行的话,speedup 只能提升 2 倍(不考虑事实上有多少线程可用);如果程序的 10% 需要串行进行,speedup 最多能够提高近 10 倍。

Amdahl 定律同样量化了串行化的效率开销。在拥有 10 个处理器的系统中,程序如果有 10% 是串行化的,那么最多可以加速 5.3 倍(53 %的使用率),在拥有 100 个处理器的系统中,这个数字可以达到 9.2(9 %的使用率)。这使得无效的 CPU 利用永远不可能到达 10 倍。下图展示了随着串行执行和处理器数量变化,处理器最大限度的利用率的曲线。随着处理器数量的增加,我们很明显地看到,即使串行化执行的程度发 生细微的百分比变化,都会大大限制吞吐量随计算资源增加。

Amdahl 定律旨在说明,多核 CPU 对系统进行优化时,优化的效果取决于 CPU 的数量以及系统中的串行化程序的比重;如果仅关注于提高 CPU 数量而不降低程序的串行化比重,也无法提高系统性能。