Skip to content

Latest commit

 

History

History
executable file
·
52 lines (41 loc) · 3.9 KB

深入理解并行编程.md

File metadata and controls

executable file
·
52 lines (41 loc) · 3.9 KB

随书源码:git://git.kernel.org/pub/scm/linux/kernel/git/paulmck/perfbook.git

理解硬件

2.1.1. CPU 流水线

带有长流水线的 CPU 想要达到最佳性能,需要程序给出高度可预测的控制 流。代码主要在紧凑循环中执行的程序,可以提供恰当的控制流,比如大型矩阵 或者向量中做算术计算的程序。此时 CPU 可以正确预测在大多数情况下,代码 循环结束后的分支走向。在这种程序中,流水线可以一直保持在满状态,CPU 高速运行。 另一方面,如果程序中带有许多循环,且循环计数都比较小;或者面向对象 的程序中带有许多虚对象,每个虚对象都可以引用不同的实对象,而这些实对象 都有频繁被调用的成员函数的不同实现,此时 CPU 很难或者完全不可能预测某 个分支的走向。这样 CPU 要么等待控制流进行到足以知道分支走向的方向时, 要么干脆猜测——由于此时程序的控制流不可预测——CPU 常常猜错。在这两 种情况中,流水线都是空的,CPU 需要等待流水线被新指令填充,这将大幅降 低 CPU 的性能。

2.1.2. 内存引用

CPU比内存快太多。

2.1.4. 内存屏障

由于内存屏障的作用是防止 CPU 为了提升性能而进行的乱序执行,所以内存屏障几乎一定会降低 CPU 性能。

2.1.5. Cache Miss

现代 CPU 使用大容量的高速缓存来降低由于较低的内存访问速度带来的性能惩罚。但是,CPU 高速缓存事实上对多 CPU 间频繁访问的变量起反效果。因为当某个 CPU 想去更改变量的值时,极有可能该变量的值刚被其他 CPU 修改过。在这种情况下,变量存在于其他 CPU 而不是当前 CPU 的缓存中,这将导致代价高昂的 Cache Miss。

2.2.1. 硬件体系结构

上图是一个粗略的八核计算机系统概要图。每个管芯有两个 CPU 核,每个核带有自己高速缓存,管芯内还带有一个互联模块,使管芯内的两个核可以互相通信。在图中央的系统互联模块可以让四个管芯相互通信,并且将管芯与主存连接起来。

数据以“缓存线”为单位在系统中传输,“缓存线”对应于内存中一个 2 的幂大小的字节块,大小通常为 32 到 256 字节之间。当 CPU 从内存中读取一个变量到它的寄存器中时,必须首先将包含了该变量的缓存线读取到 CPU 高速缓存。

同样地,CPU 将寄存器中的一个值存储到内存时,不仅必须将包含了该值的缓存线读到 CPU 高速缓存,还必须确保没有其他 CPU 拥有该缓存线的拷贝。比如,如果 CPU0 在对一个变量执行“比较并交换”(CAS)操作,而该变量所在的缓存线在 CPU7 的高速缓存中,就会发生以下经过简化的事件序列:

  1. CPU0 检查本地高速缓存,没有找到缓存线。
  2. 请求被转发到CPU0和CPU1的互联模块,检查CPU1的本地高速缓存, 没有找到缓存线。
  3. 请求被转发到系统互联模块,检查其他三个管芯,得知缓存线被 CPU6 和 CPU7 所在的管芯持有。
  4. 请求被转发到CPU6和CPU7的互联模块,检查这两个CPU的高速缓存, 在 CPU7 的高速缓存中找到缓存线。
  5. CPU7 将缓存线发送给所属的互联模块,并且刷新自己高速缓存中的缓 存线。
  6. CPU6 和 CPU7 的互联模块将缓存线发送给系统互联模块。
  7. 系统互联模块将缓存线发送给 CPU0 和 CPU1 的互联模块。
  8. CPU0 和 CPU1 的互联模块将缓存线发送给 CPU0 的高速缓存。
  9. CPU0 现在可以对高速缓存中的变量执行 CAS 操作了。

并行算法必须将每个线程设计成尽可能独立运行的线 程。越少使用线程间通信手段,比如原子操作、锁或者其它消息传递方法,应用程序的性能和可扩展性就会更好。